Document Open Access Logo

Exploration of Graphs with Excluded Minors

Authors Júlia Baligács , Yann Disser , Irene Heinrich , Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2023.11.pdf
  • Filesize: 0.8 MB
  • 15 pages

Document Identifiers

Author Details

Júlia Baligács
  • Technische Universität Darmstadt, Germany
Yann Disser
  • Technische Universität Darmstadt, Germany
Irene Heinrich
  • Technische Universität Darmstadt, Germany
Pascal Schweitzer
  • Technische Universität Darmstadt, Germany

Cite AsGet BibTex

Júlia Baligács, Yann Disser, Irene Heinrich, and Pascal Schweitzer. Exploration of Graphs with Excluded Minors. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
https://doi.org/10.4230/LIPIcs.ESA.2023.11

Abstract

We study the online graph exploration problem proposed by Kalyanasundaram and Pruhs (1994) and prove a constant competitive ratio on minor-free graphs. This result encompasses and significantly extends the graph classes that were previously known to admit a constant competitive ratio. The main ingredient of our proof is that we find a connection between the performance of the particular exploration algorithm Blocking and the existence of light spanners. Conversely, we exploit this connection to construct light spanners of bounded genus graphs. In particular, we achieve a lightness that improves on the best known upper bound for genus g ≥ 1 and recovers the known tight bound for the planar case (g = 0).

Subject Classification

ACM Subject Classification
  • Theory of computation → Online algorithms
  • Theory of computation → Sparsification and spanners
  • Mathematics of computing → Graphs and surfaces
Keywords
  • online algorithms
  • competitive analysis
  • graph exploration
  • graph spanners
  • minor-free graphs
  • bounded genus graphs

Metrics

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

Related Versions

References

  1. Susanne Albers and Monika R. Henzinger. Exploring unknown environments. SIAM Journal on Computing, 29(4):1164-1188, 2000. Google Scholar
  2. Ingo Althöfer, Gautam Das, David P. Dobkin, Deborah Joseph, and José Soares. On sparse spanners of weighted graphs. Discrete & Computational Geometry, 9:81-100, 1993. Google Scholar
  3. Sanjeev Arora, Michelangelo Grigni, David R. Karger, Philip N. Klein, and Andrzej Woloszyn. A polynomial-time approximation scheme for weighted planar graph TSP. In Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 33-41, 1998. Google Scholar
  4. Baruch Awerbuch, Alan Baratz, and David Peleg. Cost-sensitive analysis of communication protocols. In Proceedings of the 9th Annual ACM Symposium on Principles of Distributed Computing (PODC), pages 177-187, 1990. Google Scholar
  5. Alexander Birx, Yann Disser, Alexander V. Hopp, and Christina Karousatou. An improved lower bound for competitive graph exploration. Theoretical Computer Science, 868:65-86, 2021. Google Scholar
  6. Antje Bjelde, Jan Hackfeld, Yann Disser, Christoph Hansknecht, Maarten Lipmann, Julie Meißner, Miriam Schlöter, Kevin Schewior, and Leen Stougie. Tight bounds for online TSP on the line. ACM Transactions on Algorithms, 17(1):3:1-3:58, 2021. Google Scholar
  7. Vincenzo Bonifaci and Leen Stougie. Online k-server routing problems. Theory of Computing Systems, 45(3):470-485, 2009. Google Scholar
  8. Glencora Borradaile, Erik D. Demaine, and Siamak Tazari. Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs. Algorithmica, 68(2):287-311, 2014. Google Scholar
  9. Glencora Borradaile, Hung Le, and Christian Wulff-Nilsen. Minor-free graphs have light spanners. In Proceedings of the 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 767-778, 2017. Google Scholar
  10. Sebastian Brandt, Klaus-Tycho Foerster, Jonathan Maurer, and Roger Wattenhofer. Online graph exploration on a restricted graph class: Optimal solutions for tadpole graphs. Theoretical Computer Science, 839:176-185, 2020. Google Scholar
  11. Shiri Chechik and Christian Wulff-Nilsen. Near-optimal light spanners. ACM Transactions on Algorithms, 14(3):1-15, 2018. Google Scholar
  12. Erik D. Demaine, MohammadTaghi HajiAghayi, and Bojan Mohar. Approximation algorithms via contraction decomposition. Combinatorica, 30(5):533-552, 2010. Google Scholar
  13. Xiaotie Deng and Christos H. Papadimitriou. Exploring an unknown graph. Journal of Graph Theory, 32(3):265-297, 1999. Google Scholar
  14. Dariusz Dereniowski, Yann Disser, Adrian Kosowski, Dominik Paj, and Przemysław Uznański. Fast collaborative graph exploration. Information and Computation, 243:37-49, 2015. Google Scholar
  15. Yann Disser, Jan Hackfeld, and Max Klimm. Tight bounds for undirected graph exploration with pebbles and multiple agents. Journal of the ACM, 66(6):40(41), 2019. Google Scholar
  16. Yann Disser, Frank Mousset, Andreas Noever, Nemanja Skoric, and Angelika Steger. A general lower bound for collaborative tree exploration. Theoretical Computer Science, 811:70-78, 2020. Google Scholar
  17. Stefan Dobrev, Rastislav Královič, and Euripides Markou. Online graph exploration with advice. In Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity (SIROCCO), pages 267-278, 2012. Google Scholar
  18. Franziska Eberle, Alexander Lindermayr, Nicole Megow, Lukas Nölke, and Jens Schlöter. Robustification of online graph exploration methods. In Proceedings of the 36th Conference on Artificial Intelligence (AAAI), pages 9732-9740, 2022. Google Scholar
  19. Paul Erdős. Extremal problems in graph theory. In Proceedings of the Symposium on Theory of Graphs and its Applications, pages 29-36, 1963. Google Scholar
  20. Arnold Filtser and Shay Solomon. The greedy spanner is existentially optimal. SIAM Journal on Computing, 49(2):429-447, 2020. Google Scholar
  21. Rudolf Fleischer and Gerhard Trippen. Exploring an unknown graph efficiently. In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), pages 11-22, 2005. Google Scholar
  22. Klaus-Tycho Foerster and Roger Wattenhofer. Lower and upper competitive bounds for online directed graph exploration. Theoretical Computer Science, 655:15-29, 2016. Google Scholar
  23. Robin Fritsch. Online graph exploration on trees, unicyclic graphs and cactus graphs. Information Processing Letters, 168:106096, 2021. Google Scholar
  24. Michelangelo Grigni. Approximate TSP in graphs with forbidden minors. In Proceedings of the 27th International Colloquium on Automata, Languages, and Programming (ICALP), volume 1853, pages 869-877, 2000. Google Scholar
  25. Michelangelo Grigni and Hao-Hsiang Hung. Light spanners in bounded pathwidth graphs. In Proceedings of the 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), pages 467-477, 2012. Google Scholar
  26. Michelangelo Grigni and Papa Sissokho. Light spanners and approximate TSP in weighted graphs with forbidden minors. In Proceedings of the 13th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 852-857, 2002. Google Scholar
  27. Allen Hatcher. Algebraic topology. Cambridge University Press, 2000. URL: https://cds.cern.ch/record/478079.
  28. Cor A.J. Hurkens and Gerhard J. Woeginger. On the nearest neighbor rule for the traveling salesman problem. Operations Research Letters, 32(1):1-4, 2004. Google Scholar
  29. Bala Kalyanasundaram and Kirk R. Pruhs. Constructing competitive tours from local information. Theoretical Computer Science, 130(1):125-138, 1994. Google Scholar
  30. Michael Krivelevich and Benjamin Sudakov. Minors in expanding graphs. Geometric and Functional Analysis, 19(1):294-331, 2009. Google Scholar
  31. Nicole Megow, Kurt Mehlhorn, and Pascal Schweitzer. Online graph exploration: New results on old and new algorithms. Theoretical Computer Science, 463:62-72, 2012. Google Scholar
  32. Michael Mitzenmacher and Eli Upfal. Probability and computing: Randomization and probabilistic techniques in algorithms and data analysis. Cambridge University Press, 2017. Google Scholar
  33. Shuichi Miyazaki, Naoyuki Morimoto, and Yasuo Okabe. The online graph exploration problem on restricted graphs. IEICE transactions on information and systems, 92(9):1620-1627, 2009. Google Scholar
  34. Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001. Google Scholar
  35. David Peleg and Alejandro A. Schäffer. Graph spanners. Journal of graph theory, 13(1):99-116, 1989. Google Scholar
  36. Daniel J. Rosenkrantz, Richard E. Stearns, and Philip M. Lewis, II. An analysis of several heuristics for the traveling salesman problem. SIAM journal on computing, 6(3):563-581, 1977. Google Scholar
  37. Daniel Russel and Leonidas J. Guibas. Exploring protein folding trajectories using geometric spanners. In Pacific Symposium on Biocomputing (PSB), pages 42-53. World Scientific, 2005. Google Scholar
  38. Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang. Light graphs with small routing cost. Networks, 39(3):130-138, 2002. Google Scholar
  39. John William Theodore Youngs. Minimal imbeddings and the genus of a graph. Journal of Mathematics and Mechanics, pages 303-315, 1963. 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