Document Open Access Logo

Graph Reconstruction with a Betweenness Oracle

Authors Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, Morten Stöckel

PDF
Thumbnail PDF

File

LIPIcs.STACS.2016.5.pdf
  • Filesize: 0.62 MB
  • 14 pages

Document Identifiers

Author Details

Mikkel Abrahamsen
Greg Bodwin
Eva Rotenberg
Morten Stöckel

Cite As Get BibTex

Mikkel Abrahamsen, Greg Bodwin, Eva Rotenberg, and Morten Stöckel. Graph Reconstruction with a Betweenness Oracle. In 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 47, pp. 5:1-5:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.STACS.2016.5

Abstract

Graph reconstruction algorithms seek to learn a hidden graph by repeatedly querying a black-box oracle for information about the graph structure. Perhaps the most well studied and applied version of the problem uses a distance oracle, which can report the shortest path distance between any pair of nodes.

We introduce and study the betweenness oracle, where bet(a, m, z) is true iff m lies on a shortest path between a and z. This oracle is strictly weaker than a distance oracle, in the sense that a betweenness query can be simulated by a constant number of distance queries, but not vice versa.  Despite this, we are able to develop betweenness reconstruction algorithms that match the current state of the art for distance reconstruction, and even improve it for certain types of graphs. We obtain the following algorithms: (1) Reconstruction of general graphs in O(n^2) queries, (2) Reconstruction of degree-bounded graphs in ~O(n^{3/2}) queries, (3) Reconstruction of geodetic degree-bounded graphs in ~O(n) queries

In addition to being a fundamental graph theoretic problem with some natural applications, our new results shed light on some avenues for progress in the distance reconstruction problem.

Subject Classification

Keywords
  • graph reconstruction
  • bounded degree graphs
  • query complexity

Metrics

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

References

  1. N. Alon and V. Asodi. Learning a hidden subgraph. SIAM Journal of Discrete Math, 18:697-712, 2005. Google Scholar
  2. N. Alon, R. Beigel, S. Kasif, S. Riduch, and B. Sudakov. Learning a hidden matching. SIAM Journal of Computing, 33:487-501, 2004. Google Scholar
  3. D. Angluin and J. Chen. Learning a hidden graph using o(log n) queries per edge. COLT, pages 210-223, 2004. Google Scholar
  4. D. Angluin and J. Chen. Learning a hidden hypergraph. Journal of Machine Learning Research, 7:2215-2236, 2006. Google Scholar
  5. Z. Beerliova, F. Eberhard, T. Erlebach, E. Hall, M. Hoffman, and L. S. Ram. Network discovery and verification. WG, pages 127-138, 2005. Google Scholar
  6. M. Bouvel, V. Grebinski, and G. Kucherov. Combinatorial search on graphs motivated by bioinformatics applications: A brief survey. Graph-Theoretic Concepts in Computer Science, pages 16-27, 2005. Google Scholar
  7. R. Castro, M. Coates, G. Liang, R. Nowak, and B. Yu. Network tomography: recent developments. Statistical Science, 19:499-517, 2004. Google Scholar
  8. D. Chen, L. J. Guibas, J. Hershberger, and J. Sun. Road network reconstruction for organizing paths. SODA, pages 1309-1320, 2010. Google Scholar
  9. L. Dall'Asta, I. Alvarez-Hamelin, A. Barrat, A. Vázquez, and A. Vespignani. Exploring networks with traceroute-like probes: Theory and simulations. Theoretical Computer Science, 355(1):6-24, 2006. Google Scholar
  10. T. Erlebach, A. Hall, M. Hoffmann, and M. Mihal'ák. Network discovery and verification with distance queries. Algorithms and Complexity, pages 69-80, 2006. Google Scholar
  11. V. Grebinski and G. Kucherov. Reconstring a hamiltonian cycle by querying the graph: Application to dna physical mapping. Discrete Applied Mathematics 88, pages 147-165, 1998. Google Scholar
  12. V. Grebinski and G. Kucherov. Optimal reconstruction of graphs under the additive model. Algorithmica 28, pages 104-124, 200. Google Scholar
  13. J. J. Hein. An optimal algorithm to reconstruct trees from additive distance data. Bulletin of Mathematical Biology, 51(5):597-603, 1989. Google Scholar
  14. S. Honiden, M. E. Houle, and C. Sommer. Balancing graph voronoi diagrams. ISVD, pages 183-191, 2009. Google Scholar
  15. S. Kannan, C. Mathieu, and H. Zhou. Near-linear query complexity for graph inference. Automata, Languages, and Programming, 2015. Google Scholar
  16. V. King, L. Zhang, and Y. Zhou. On the complexity of distance-based eviolutionary tree reconstruction. SODA, pages 444-453, 2003. Google Scholar
  17. C. Mathieu and H. Zhou. Graph reconstruction via distance oracles. ICALP, pages 733-744, 2013. Google Scholar
  18. H. Mazzawi. Optimally reconstructing weighted graphs using queries. SODA, pages 608-615, 2010. Google Scholar
  19. S. Micali and Z. Allen-Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 2015. Google Scholar
  20. M. Nei and J. Zhang. Evolutionary distance: Estimation. Encyclopedia of Life Sciences, 2005. Google Scholar
  21. L. Reyzin and N. Srivastava. Learning and verifying graphs using queries with a focus on edge counting. Proc. 18th Algorithmic Learning Theory, pages 285-297, 2007. Google Scholar
  22. L. Reyzin and N. Srivastava. On the longest path algorithm for reconstructing trees from distance matrices. Information processing letters, 101(3):98-100, 2007. Google Scholar
  23. F. Tarissan, M. Latapy, and C. Prieur. Efficient measurement of complex networks using link queries. INFOCOM Workshops, pages 254-259, 2009. Google Scholar
  24. M. Thorup and U. Zwick. Compact routing schemes. SPAA, pages 1-10, 2001. Google Scholar
  25. M. S. Waterman, T. F. Smith, M. Singh, and W. Beyer. Additive evolutionary trees. Journal of Theoretical Biology, 64(2):199-213, 1977. 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 About DROPS Imprint Privacy Contact