Document Open Access Logo

A Simple Algorithm for Graph Reconstruction

Authors Claire Mathieu, Hang Zhou

PDF
Thumbnail PDF

File

LIPIcs.ESA.2021.68.pdf
  • Filesize: 0.91 MB
  • 18 pages

Document Identifiers

Author Details

Claire Mathieu
  • CNRS, IRIF, Université de Paris, France
Hang Zhou
  • École Polytechnique, Institut Polytechnique de Paris, France

Funding

This work was partially funded by the grant ANR-19-CE48-0016 from the French National Research Agency (ANR).

Acknowledgements

We want to thank the anonymous reviewers for their valuable comments.

Cite AsGet BibTex

Claire Mathieu and Hang Zhou. A Simple Algorithm for Graph Reconstruction. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 68:1-68:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.ESA.2021.68

Abstract

How efficiently can we find an unknown graph using distance queries between its vertices? We assume that the unknown graph is connected, unweighted, and has bounded degree. The goal is to find every edge in the graph. This problem admits a reconstruction algorithm based on multi-phase Voronoi-cell decomposition and using Õ(n^{3/2}) distance queries [Kannan et al., 2018]. In our work, we analyze a simple reconstruction algorithm. We show that, on random Δ-regular graphs, our algorithm uses Õ(n) distance queries. As by-products, we can reconstruct those graphs using O(log² n) queries to an all-distances oracle or Õ(n) queries to a betweenness oracle, and we bound the metric dimension of those graphs by log² n. Our reconstruction algorithm has a very simple structure, and is highly parallelizable. On general graphs of bounded degree, our reconstruction algorithm has subquadratic query complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Graph algorithms analysis
  • Theory of computation → Random network models
  • Networks → Network algorithms
Keywords
  • reconstruction
  • network topology
  • random regular graphs
  • metric dimension

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph Reconstruction with a Betweenness Oracle. In Symposium on Theoretical Aspects of Computer Science, pages 5:1-5:14. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  2. Dimitris Achlioptas, Aaron Clauset, David Kempe, and Cristopher Moore. On the bias of traceroute sampling: Or, power-law degree distributions in regular graphs. Journal of the ACM, 56(4):21:1-21:28, 2009. Google Scholar
  3. Ramtin Afshar, Michael T. Goodrich, Pedro Matias, and Martha C. Osegueda. Reconstructing biological and digital phylogenetic trees in parallel. In European Symposium on Algorithms, volume 173, pages 3:1-3:24. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2020. Google Scholar
  4. Animashree Anandkumar, Avinatan Hassidim, and Jonathan Kelner. Topology discovery of sparse random graphs with few participants. Random Structures & Algorithms, 43(1):16-48, 2013. Google Scholar
  5. Robert F. Bailey and Peter J. Cameron. Base size, metric dimension and other invariants of groups and graphs. Bulletin of the London Mathematical Society, 43(2):209-242, 2011. Google Scholar
  6. Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286(5439):509-512, 1999. Google Scholar
  7. Zuzana Beerliova, Felix Eberhard, Thomas Erlebach, Alexander Hall, Michael Hoffmann, Matús Mihal'ak, and L. Shankar Ram. Network discovery and verification. IEEE Journal on Selected Areas in Communications, 24(12):2168-2181, 2006. Google Scholar
  8. Vincent D. Blondel, Jean-Loup Guillaume, Julien M. Hendrickx, and Raphaël M. Jungers. Distance distribution in random graphs and application to network exploration. Physical Review E, 76(6):066101, 2007. Google Scholar
  9. Béla Bollobás. A probabilistic proof of an asymptotic formula for the number of labelled regular graphs. European Journal of Combinatorics, 1(4):311-316, 1980. Google Scholar
  10. Béla Bollobás. Distinguishing vertices of random graphs. North-Holland Mathematics Studies, 62:33-49, 1982. Google Scholar
  11. Béla Bollobás, Dieter Mitsche, and Paweł Prałat. Metric dimension for random graphs. The Electronic Journal of Combinatorics, 20(4):P1, 2013. Google Scholar
  12. Gary Chartrand, Linda Eroh, Mark A. Johnson, and Ortrud R. Oellermann. Resolvability in graphs and the metric dimension of a graph. Discrete Applied Mathematics, 105(1-3):99-113, 2000. Google Scholar
  13. José Cáceres, Carmen Hernando, Mercè Mora, Ignacio M. Pelayo, María L. Puertas, Carlos Seara, and David R. Wood. On the metric dimension of cartesian products of graphs. SIAM Journal on Discrete Mathematics, 21(2):423-441, 2007. Google Scholar
  14. Thomas Erlebach, Alexander Hall, Michael Hoffmann, and Matúš Mihal'ák. Network discovery and verification with distance queries. Algorithms and Complexity, pages 69-80, 2006. Google Scholar
  15. Thomas Erlebach, Alexander Hall, and Matúš Mihal’ák. Approximate discovery of random graphs. In International Symposium on Stochastic Algorithms, pages 82-92. Springer, 2007. Google Scholar
  16. Michalis Faloutsos, Petros Faloutsos, and Christos Faloutsos. On power-law relationships of the internet topology. ACM SIGCOMM, 29(4):251–262, 1999. Google Scholar
  17. Florent Foucaud and Guillem Perarnau. Bounds for identifying codes in terms of degree parameters. Electronic Journal of Combinatorics, 19(P32), 2012. Google Scholar
  18. Alan Frieze and Michał Karoński. Introduction to random graphs. URL: https://www.math.cmu.edu/~af1p/BOOK.pdf.
  19. Alan Frieze, Ryan Martin, Julien Moncel, Miklós Ruszinkó, and Cliff Smyth. Codes identifying sets of vertices in random networks. Discrete Mathematics, 307(9):1094-1107, 2007. Google Scholar
  20. Jean-Loup Guillaume and Matthieu Latapy. Complex network metrology. Complex systems, 16(1):83, 2005. Google Scholar
  21. Frank Harary and Robert A. Melter. On the metric dimension of a graph. Ars Combinatoria, 2(191-195), 1976. Google Scholar
  22. Jotun J. Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology, 51(5):597-603, 1989. Google Scholar
  23. Carmen Hernando, Merce Mora, Ignacio M. Pelayo, Carlos Seara, and David R. Wood. Extremal graph theory for metric dimension and diameter. Electronic Notes in Discrete Mathematics, 29:339-343, 2007. European Conference on Combinatorics, Graph Theory and Applications. Google Scholar
  24. Imran Javaid, M. Tariq Rahim, and Kashif Ali. Families of regular graphs with constant metric dimension. Utilitas mathematica, 75:21-34, 2008. Google Scholar
  25. Mihajlo Jovanović, Fred Annexstein, and Kenneth Berman. Modeling peer-to-peer network topologies through small-world models and power laws. In IX Telecommunications Forum, TELFOR, pages 1-4. Citeseer, 2001. Google Scholar
  26. Sampath Kannan, Eugene L. Lawler, and Tandy Warnow. Determining the evolutionary tree using experiments. Journal of Algorithms, 21(1):26-50, 1996. Google Scholar
  27. Sampath Kannan, Claire Mathieu, and Hang Zhou. Graph reconstruction and verification. ACM Transactions on Algorithms, 14(4):1-30, 2018. Google Scholar
  28. Mark G. Karpovsky, Krishnendu Chakrabarty, and Lev B. Levitin. On a new class of codes for identifying vertices in graphs. IEEE Transactions on Information Theory, 44(2):599-611, 1998. Google Scholar
  29. Samir Khuller, Balaji Raghavachari, and Azriel Rosenfeld. Landmarks in graphs. Discrete applied mathematics, 70(3):217-229, 1996. Google Scholar
  30. Valerie King, Li Zhang, and Yunhong Zhou. On the complexity of distance-based evolutionary tree reconstruction. In Symposium on Discrete Algorithms, pages 444-453. SIAM, 2003. Google Scholar
  31. Anukool Lakhina, John W. Byers, Mark Crovella, and Peng Xie. Sampling biases in IP topology measurements. In Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies, volume 1, pages 332-341. IEEE, 2003. Google Scholar
  32. Dieter Mitsche and Juanjo Rué. On the limiting distribution of the metric dimension for random forests. European Journal of Combinatorics, 49:68-89, 2015. Google Scholar
  33. Elchanan Mossel and Jiaming Xu. Seeded graph matching via large neighborhood statistics. Random Structures & Algorithms, 57(3):570-611, 2020. Google Scholar
  34. Mark E. J. Newman, Duncan J. Watts, and Steven H. Strogatz. Random graph models of social networks. Proceedings of the national academy of sciences, 99(suppl 1):2566-2572, 2002. Google Scholar
  35. Gergely Odor and Patrick Thiran. Sequential metric dimension for random graphs, 2020. URL: http://arxiv.org/abs/1910.10116.
  36. Ortrud R. Oellermann and Joel Peters-Fransen. The strong metric dimension of graphs and digraphs. Discrete Applied Mathematics, 155(3):356-364, 2007. Google Scholar
  37. Yunior Ramírez-Cruz, Ortrud R. Oellermann, and Juan A. Rodríguez-Velázquez. The simultaneous metric dimension of graph families. Discrete Applied Mathematics, 198:241-250, 2016. Google Scholar
  38. Lev Reyzin and Nikhil Srivastava. Learning and verifying graphs using queries with a focus on edge counting. In Algorithmic Learning Theory, pages 285-297. Springer, 2007. Google Scholar
  39. Guozhen Rong, Wenjun Li, Yongjie Yang, and Jianxin Wang. Reconstruction and verification of chordal graphs with a distance oracle. Theoretical Computer Science, 859:48-56, 2021. Google Scholar
  40. András Sebő and Eric Tannier. On metric generators of graphs. Mathematics of Operations Research, 29(2):383-393, 2004. Google Scholar
  41. Sandeep Sen and V. N. Muralidhara. The covert set-cover problem with application to network discovery. In WALCOM, pages 228-239. Springer, 2010. Google Scholar
  42. Peter J. Slater. Leaves of trees. In Southeastern Conference on Combinatorics, Graph Theory, and Computing, pages 549-559, 1975. Google Scholar
  43. Michael S. Waterman, Temple F. Smith, M. Singh, and W. A. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64(2):199-213, 1977. Google Scholar
  44. Nicholas C. Wormald. Models of random regular graphs. London Mathematical Society Lecture Note Series, pages 239-298, 1999. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact