Abstract
How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? Let \(G = (V,E)\) be a connected, undirected, and unweighted graph of bounded degree. The edge set E is initially unknown, and the graph can be accessed using a distance oracle, which receives a pair of vertices (u, v) and returns the distance between u and v. In the verification problem, we are given a hypothetical graph \(\hat{G} = (V,\hat{E})\) and want to check whether G is equal to \(\hat{G}\). We analyze a natural greedy algorithm and prove that it uses \(n^{1+o(1)}\) distance queries. In the more difficult reconstruction problem, \(\hat{G}\) is not given, and the goal is to find the graph G. If the graph can be accessed using a shortest path oracle, which returns not just the distance but an actual shortest path between u and v, we show that extending the idea of greedy gives a reconstruction algorithm that uses \(n^{1+o(1)}\) shortest path queries. When the graph has bounded treewidth, we further bound the query complexity of the greedy algorithms for both problems by \(\tilde{O}(n)\). When the graph is chordal, we provide a randomized algorithm for reconstruction using \(\tilde{O}(n)\) distance queries.
The full version of the paper is available on the authors’ websites.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Achlioptas, D., Clauset, A., Kempe, D., Moore, C.: On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. Journal of the ACM (JACM) 56(4), 21 (2009)
Beerliova, Z., Eberhard, F., Erlebach, T., Hall, A., Hoffmann, M., Mihaľák, M., Shankar Ram, L.: Network discovery and verification. In: Kratsch, D. (ed.) WG 2005. LNCS, vol. 3787, pp. 127–138. Springer, Heidelberg (2005)
Castro, R., Coates, M., Liang, G., Nowak, R., Yu, B.: Network tomography: recent developments. Statistical Science 19, 499–517 (2004)
Chung, F., Garrett, M., Graham, R., Shallcross, D.: Distance realization problems with applications to internet tomography. Journal of Computer and System Sciences 63, 432–448 (2001)
Dall’Asta, L., Alvarez-Hamelin, I., Barrat, A., Vázquez, A., Vespignani, A.: Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science 355(1), 6–24 (2006)
Erlebach, T., Hall, A., Hoffmann, M., Mihaľák, M.: Network discovery and verification with distance queries. In: Calamoneri, T., Finocchi, I., Italiano, G.F. (eds.) CIAC 2006. LNCS, vol. 3998, pp. 69–80. Springer, Heidelberg (2006)
Hein, J.J.: An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology 51(5), 597–603 (1989)
Johnson, D.S.: Approximation algorithms for combinatorial problems. Journal of computer and system sciences 9(3), 256–278 (1974)
King, V., Zhang, L., Zhou, Y.: On the complexity of distance-based evolutionary tree reconstruction. In: SODA, pp. 444–453. SIAM (2003)
Mathieu, C., Zhou, H.: Graph reconstruction via distance oracles. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 733–744. Springer, Heidelberg (2013)
Reyzin, L., Srivastava, N.: On the longest path algorithm for reconstructing trees from distance matrices. Information processing letters 101(3), 98–100 (2007)
Tarissan, F., Latapy, M., Prieur, C.: Efficient measurement of complex networks using link queries. In: INFOCOM Workshops, pp. 254–259. IEEE (2009)
Thorup, M., Zwick, U.: Compact routing schemes. In: Symposium on Parallel Algorithms and Architectures, pp. 1–10. ACM (2001)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kannan, S., Mathieu, C., Zhou, H. (2015). Near-Linear Query Complexity for Graph Inference. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science(), vol 9134. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-47672-7_63
Download citation
DOI: https://doi.org/10.1007/978-3-662-47672-7_63
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-47671-0
Online ISBN: 978-3-662-47672-7
eBook Packages: Computer ScienceComputer Science (R0)