Sampath Kannan
Claire Mathieu
Abstract
How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G. In the verification problem, we are given a hypothetical graph Ĝ and want to check whether G is equal to Ĝ.
We provide a randomized algorithm for reconstruction using Õ(n3/2) distance queries, based on Voronoi cell decomposition. Next, we analyze natural greedy algorithms for reconstruction using a shortest path oracle and also for verification using either oracle, and show that their query complexity is n1+o(1). We further improve the query complexity when the graph is chordal or outerplanar. Finally, we show some lower bounds, and consider an approximate version of the reconstruction problem.
- Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. 2016. Graph reconstruction with a betweenness oracle. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS'16), Nicolas Ollinger and Heribert Vollmer (Eds.). Vol. 47. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik.Google Scholar
- Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. 2009. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. J. ACM 56, 4, Article 21 (2009), 21:1--21:28. Google ScholarDigital Library
- Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihal’ak, and L. Shankar Ram. 2006. Network discovery and verification. IEEE J. Sel. Areas Commun. 24, 12 (2006), 2168--2181. Google ScholarCross Ref
- Jean R. S. Blair and Barry Peyton. 1993. An introduction to chordal graphs and clique trees. In Graph Theory and Sparse Matrix Computation. Springer, 1--29.Google Scholar
- Rui Castro, Mark Coates, Gang Liang, Robert Nowak, and Bin Yu. 2004. Network tomography: Recent developments. Statist. Sci. 19 (2004), 499--517.Google ScholarCross Ref
- Gary Chartrand and Frank Harary. 1967. Planar permutation graphs. Ann. l’Institut Henri Poincaré (B) Prob. Statist. 3, 4 (1967), 433--438.Google Scholar
- F. Chung, M. Garrett, R. Graham, and D. Shallcross. 2001. Distance realization problems with applications to internet tomography. J. Comput. Syst. Sci. 63 (2001), 432--448. Google ScholarDigital Library
- Luca Dall’Asta, Ignacio Alvarez-Hamelin, Alain Barrat, Alexei Vázquez, and Alessandro Vespignani. 2006. Exploring networks with traceroute-like probes: Theory and simulations. Theor. Comput. Sci. 355, 1 (2006), 6--24. Google ScholarDigital Library
- Jotun J. Hein. 1989. An optimal algorithm to reconstruct trees from additive distance data. Bull. Math. Biol. 51, 5 (1989), 597--603.Google ScholarCross Ref
- Shinichi Honiden, Michael E. Houle, and Christian Sommer. 2009. Balancing graph voronoi diagrams. In International Symposium on Voronoi Diagrams. IEEE, 183--191. Google ScholarDigital Library
- David S. Johnson. 1974. Approximation algorithms for combinatorial problems. J. Comput. Syst. Sci. 9, 3 (1974), 256--278. Google ScholarDigital Library
- Sampath Kannan, Claire Mathieu, and Hang Zhou. 2015. Near-linear query complexity for graph inference. In International Colloquium on Automata, Languages and Programming. Springer, 773--784.Google Scholar
- Valerie King, Li Zhang, and Yunhong Zhou. 2003. On the complexity of distance-based evolutionary tree reconstruction. In Symposium on Discrete Algorithms. SIAM, 444--453. Google ScholarDigital Library
- Claire Mathieu and Hang Zhou. 2013. Graph reconstruction via distance oracles. In International Colloquium on Automata, Languages and Programming. Springer, 733--744. Google ScholarDigital Library
- Brendan D. McKay and Nicholas C. Wormald. 1991. Asymptotic enumeration by degree sequence of graphs with degrees . Combinatorica 11, 4 (1991), 369--382.Google ScholarCross Ref
- Bruce A. Reed. 2003. Algorithmic aspects of tree width. In Recent Advances in Algorithms and Combinatorics. Springer, 85--107.Google Scholar
- Lev Reyzin and Nikhil Srivastava. 2007. Learning and verifying graphs using queries with a focus on edge counting. In Algorithmic Learning Theory. Springer, 285--297. Google ScholarDigital Library
- Sandeep Sen and V. N. Muralidhara. 2010. The covert set-cover problem with application to network discovery. In International Workshop on Algorithms and Computation. Springer, 228--239. Google ScholarDigital Library
- Fabien Tarissan, Matthieu Latapy, and Christophe Prieur. 2009. Efficient measurement of complex networks using link queries. In INFOCOM Workshops. IEEE, 254--259. Google ScholarDigital Library
- Mikkel Thorup and Uri Zwick. 2001. Compact routing schemes. In Symposium on Parallel Algorithms and Architectures. ACM, 1--10. Google ScholarDigital Library
- Michael S. Waterman, Temple F. Smith, M. Singh, and W. A. Beyer. 1977. Additive evolutionary trees. J. Theor. Biol. 64, 2 (1977), 199--213.Google ScholarCross Ref
Index Terms
- Graph Reconstruction and Verification
Recommendations
Reconstruction number of graphs with unique pendant vertex
AbstractA vertex-deleted subgraph of a graph G is called a card of G . The reconstruction number of G is the minimum number of cards of G that suffices to determine G uniquely. A P-graph (Yongzhi, 1988) is a connected graph of order p with ...
A conjecture on the reconstruction of graphs from metric balls of their vertices
In this paper we investigate a new graph reconstruction problem which was introduced in a paper by Levenshtein, Konstantinova, Konstantinov and Molodtsov [Reconstruction of a graph from 2-vicinities of its vertices, Discrete Appl. Math., accepted for ...
On the reconstruction of planar graphs
We show that the planarity of a graph can be recognized from its vertex deleted subgraphs, which answers a question posed by Bondy and Hemminger in 1979. We also state some useful counting lemmas and use them to reconstruct certain planar graphs.
Comments