Abstract
We study the problem of learning a hidden graph by edge-detecting queries, each of which tells whether a set of vertices induces an edge of the hidden graph or not. We provide a new information-theoretic lower bound and give a more efficient adaptive algorithm to learn a general graph with \(n\) vertices and \(m\) edges in \(m\log n+10m+3n\) edge-detecting queries.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aigner, M.: Combinatorial Search. Wiley, New York (1988)
Alon, N., Asodi, V.: Learning a hidden subgraph. SIAM J. Discrete Math. 18, 697–712 (2005)
Alon, N., Beigel, R., Kasif, S., Rudich, S., Sudakov, B.: Learning a hidden matching. SIAM J. Comput. 33, 487–501 (2004)
Anderson, I.: Combinatorial designs: construction methods. Ellis Horwood, New York (1990)
Angluin, D., Chen, J.: Learning a hidden hypergraph. J. Mach. Learn. Res. 7, 2215–2236 (2006)
Angluin, D., Chen, J.: Learning a hidden graph using \(O(\log n)\) queries per edge. J. Comput. Syst. Sci. 74, 546–556 (2008)
Beigel, R., Alon, N., Apaydin, M.S., Fortnow, L., Kasif, S.: An optimal procedure for gap closing in whole genome shotgun sequencing. In: Proceedings of 2001 RECOMB, pp. 22–30. ACM Press, New York
Bouvel, M., Grebinski, V., Kucherov, G.: Combinatorial search on graphs motivated by bioinformatics applications: a brief survey. WG, LNCS 3787, pp. 16–27 (2005)
Chang, H., Chen, H.-B., Fu, H.L., Shih, C.H.: Reconstruction of hidden graphs and threshold group testing. J. Comb. Optim. 22, 270–281 (2011)
Damaschke, P., Sheikh Muhammad, A.: Competitive group testing and learning hidden vertex covers with minimum adaptivity. Discrete Math. Algebra Appl. 2, 291–311 (2010)
Damaschke, P., Sheikh Muhammad, A.: Bounds for nonadaptive group tests to estimate the amount of defectives. Discrete Math. Algebra Appl. 3, 517–536 (2011)
Du, D.Z., Hwang, F.K.: Combinatorial Group Testing and its Applications, 2nd edn. World Scientific, Singapore (2000)
Du, D.Z., Hwang, F.K.: Pooling Designs and Nonadaptive Group Testing: Important Tools for DNA Sequencing. World Scientific, Singapore (2006)
Grebinski, V., Kucherov, G.: Reconstructing a Hamiltonian cycle by querying the graph: application to DNA physical mapping. Discrete Appl. Math. 88, 147–165 (1998)
Grebinski, V., Kucherov, G.: Optimal reconstruction of graphs under the additive model. Algorithmica 28, 104–124 (2000)
Hwang, F.K., Liu, Y.C.: Error-tolerant pooling designs with inhibitors. J. Comput. Biol. 10, 231–236 (2003)
Nagura, J.: On the interval containing at least one prime number. In: Proceedings of the Japan Academy Series A, vol. 28, pp. 177–181 (1952)
Schlaghoff, J., Triesch, E.: Improved results for competitive group testing. Comb. Prob. Comput. 14, 191–202 (2005)
Sorokin, A., Lapidus, A., Capuano, V., Galleron, N., Pujic, P., Ehrlich, S.D.: A new approach using multiplex long accurate PCR and yeast artificial chromosomes for bacterial chromosome mapping and sequencing. Genome Res. 6, 448–453 (1996)
Tettelin, H., Radune, D., Kasif, S., Khouri, H., Salzberg, S.L.: Optimized multiplex PCR: efficiently closing a whole-genome shotgun sequencing project. Genomics 62, 500–507 (1996)
Acknowledgments
The authors would like to express their gratitude to the referees for their valuable comments and suggestions in improving the presentation of this paper. Partially supported by National Science Council, Taiwan under Grant NSC 99-2811-M-009-056 (H.-L. Fu and C.-H. Shih) and 100-2115-M-390-004-MY2 (H. Chang).
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chang, H., Fu, HL. & Shih, CH. Learning a hidden graph. Optim Lett 8, 2341–2348 (2014). https://doi.org/10.1007/s11590-014-0751-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11590-014-0751-9