Document Open Access Logo

Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs

Authors Reut Levi , Nadav Shoshan

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.61.pdf
  • Filesize: 0.84 MB
  • 23 pages

Document Identifiers

Author Details

Reut Levi
  • Efi Arazi School of Computer Science, The Interdisciplinary Center Herzliya, Israel
Nadav Shoshan
  • Efi Arazi School of Computer Science, The Interdisciplinary Center Herzliya, Israel

Funding

  • Levi, Reut: This research was supported by the Israel Science Foundation grant No. 1867/20.

Acknowledgements

We would like to thank Dana Ron and Oded Goldreich for helpful comments.

Cite As Get BibTex

Reut Levi and Nadav Shoshan. Testing Hamiltonicity (And Other Problems) in Minor-Free Graphs. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.61

Abstract

In this paper we provide sub-linear algorithms for several fundamental problems in the setting in which the input graph excludes a fixed minor, i.e., is a minor-free graph. In particular, we provide the following algorithms for minor-free unbounded degree graphs.  
1) A tester for Hamiltonicity with two-sided error with poly(1/ε)-query complexity, where ε is the proximity parameter. 
2) A local algorithm, as defined by Rubinfeld et al. (ICS 2011), for constructing a spanning subgraph with almost minimum weight, specifically, at most a factor (1+ε) of the optimum, with poly(1/ε)-query complexity.  Both our algorithms use partition oracles, a tool introduced by Hassidim et al. (FOCS 2009), which are oracles that provide access to a partition of the graph such that the number of cut-edges is small and each part of the partition is small. The polynomial dependence in 1/ε of our algorithms is achieved by combining the recent poly(d/ε)-query partition oracle of Kumar-Seshadhri-Stolman (ECCC 2021) for minor-free graphs with degree bounded by d.
For bounded degree minor-free graphs we introduce the notion of covering partition oracles which is a relaxed version of partition oracles and design a poly(d/ε)-time covering partition oracle for this family of graphs. Using our covering partition oracle we provide the same results as above (except that the tester for Hamiltonicity has one-sided error) for minor-free bounded degree graphs, as well as showing that any property which is monotone and additive (e.g. bipartiteness) can be tested in minor-free graphs by making poly(d/ε)-queries.
The benefit of using the covering partition oracle rather than the partition oracle in our algorithms is its simplicity and an improved polynomial dependence in 1/ε in the obtained query complexity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Streaming, sublinear and near linear time algorithms
Keywords
  • Property Testing
  • Hamiltonian path
  • minor free graphs
  • sparse spanning sub-graphs

Metrics

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

Related Versions

References

  1. Isolde Adler and Noleen Köhler. An explicit construction of graphs of bounded degree that are far from being hamiltonian, 2021. URL: http://arxiv.org/abs/2008.05801.
  2. N. Alon, R. Rubinfeld, S. Vardi, and N. Xie. Space-efficient local computation algorithms. In Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1132-1139, 2012. Google Scholar
  3. Jasine Babu, Areej Khoury, and Ilan Newman. Every property of outerplanar graphs is testable. In Klaus Jansen, Claire Mathieu, José D. P. Rolim, and Chris Umans, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France, volume 60 of LIPIcs, pages 21:1-21:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.21.
  4. Itai Benjamini, Oded Schramm, and Asaf Shapira. Every minor-closed property of sparse graphs is testable. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 393-402. ACM, 2008. URL: https://doi.org/10.1145/1374376.1374433.
  5. Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, and Christian Sohler. Finding cycles and trees in sublinear time. Random Struct. Algorithms, 45(2):139-184, 2014. URL: https://doi.org/10.1002/rsa.20462.
  6. Artur Czumaj, Morteza Monemizadeh, Krzysztof Onak, and Christian Sohler. Planar graphs: Random walks and bipartiteness testing. Random Struct. Algorithms, 55(1):104-124, 2019. URL: https://doi.org/10.1002/rsa.20826.
  7. Artur Czumaj and Christian Sohler. A characterization of graph properties testable for general planar graphs with one-sided error (it’s all about forbidden subgraphs). In David Zuckerman, editor, 60th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2019, Baltimore, Maryland, USA, November 9-12, 2019, pages 1525-1548. IEEE Computer Society, 2019. URL: https://doi.org/10.1109/FOCS.2019.00089.
  8. Alan Edelman, Avinatan Hassidim, Huy N. Nguyen, and Krzysztof Onak. An efficient partitioning oracle for bounded-treewidth graphs. In Leslie Ann Goldberg, Klaus Jansen, R. Ravi, and José D. P. Rolim, editors, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 14th International Workshop, APPROX 2011, and 15th International Workshop, RANDOM 2011, Princeton, NJ, USA, August 17-19, 2011. Proceedings, volume 6845 of Lecture Notes in Computer Science, pages 530-541. Springer, 2011. URL: https://doi.org/10.1007/978-3-642-22935-0_45.
  9. Lars Engebretsen and Marek Karpinski. Approximation hardness of TSP with bounded metrics. In Fernando Orejas, Paul G. Spirakis, and Jan van Leeuwen, editors, Automata, Languages and Programming, 28th International Colloquium, ICALP 2001, Crete, Greece, July 8-12, 2001, Proceedings, volume 2076 of Lecture Notes in Computer Science, pages 201-212. Springer, 2001. URL: https://doi.org/10.1007/3-540-48224-5_17.
  10. Hendrik Fichtenberger, Reut Levi, Yadu Vasudev, and Maximilian Wötzel. A sublinear tester for outerplanarity (and other forbidden minors) with one-sided error. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 52:1-52:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.ICALP.2018.52.
  11. O. Goldreich and D. Ron. Property testing in bounded degree graphs. Algorithmica, 32(2):302-343, 2002. URL: https://doi.org/10.1007/s00453-001-0078-7.
  12. Oded Goldreich. On testing hamiltonicity in the bounded degree graph model. Electron. Colloquium Comput. Complex., 27:109, 2020. URL: https://eccc.weizmann.ac.il/report/2020/109.
  13. Oded Goldreich, Shafi Goldwasser, and Dana Ron. Property testing and its connection to learning and approximation. J. ACM, 45(4):653-750, 1998. URL: https://doi.org/10.1145/285055.285060.
  14. A. Hassidim, J. A. Kelner, H. N. Nguyen, and K. Onak. Local graph partitions for approximation and testing. In Proceedings of the Fiftieth Annual Symposium on Foundations of Computer Science (FOCS), pages 22-31, 2009. URL: https://doi.org/10.1109/FOCS.2009.77.
  15. John E. Hopcroft and Robert Endre Tarjan. Isomorphism of planar graphs. In Raymond E. Miller and James W. Thatcher, editors, Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA, The IBM Research Symposia Series, pages 131-152. Plenum Press, New York, 1972. URL: https://doi.org/10.1007/978-1-4684-2001-2_13.
  16. Bell (https://cstheory.stackexchange.com/users/48832/bell). Hardness of approximation for minimum path cover in an undirected graph? Theoretical Computer Science Stack Exchange. URL:https://cstheory.stackexchange.com/q/40344 (version: 2018-03-08). URL: http://arxiv.org/abs/https://cstheory.stackexchange.com/q/40344.
  17. Hiro Ito. Every property is testable on a natural class of scale-free multigraphs. In Piotr Sankowski and Christos D. Zaroliagis, editors, 24th Annual European Symposium on Algorithms, ESA 2016, August 22-24, 2016, Aarhus, Denmark, volume 57 of LIPIcs, pages 51:1-51:12. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016. URL: https://doi.org/10.4230/LIPIcs.ESA.2016.51.
  18. Akash Kumar, C. Seshadhri, and Andrew Stolman. Finding forbidden minors in sublinear time: A n^1/2+o(1)-query one-sided tester for minor closed properties on bounded degree graphs. In Mikkel Thorup, editor, 59th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2018, Paris, France, October 7-9, 2018, pages 509-520. IEEE Computer Society, 2018. URL: https://doi.org/10.1109/FOCS.2018.00055.
  19. Akash Kumar, C. Seshadhri, and Andrew Stolman. Random walks and forbidden minors II: a poly(d ε^-1)-query tester for minor-closed properties of bounded degree graphs. In Moses Charikar and Edith Cohen, editors, Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23-26, 2019, pages 559-567. ACM, 2019. URL: https://doi.org/10.1145/3313276.3316330.
  20. Akash Kumar, C. Seshadhri, and Andrew Stolman. Random walks and forbidden minors III: poly(d/?)-time partition oracles for minor-free graph classes. Electron. Colloquium Comput. Complex., 28:8, 2021. URL: https://eccc.weizmann.ac.il/report/2021/008.
  21. Mitsuru Kusumoto and Yuichi Yoshida. Testing forest-isomorphism in the adjacency list model. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, volume 8572 of Lecture Notes in Computer Science, pages 763-774. Springer, 2014. URL: https://doi.org/10.1007/978-3-662-43948-7_63.
  22. C. Lenzen and R. Levi. A centralized local algorithm for the sparse spanning graph problem. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, pages 87:1-87:14, 2018. Google Scholar
  23. R. Levi and M. Medina. A (centralized) local guide. Bulletin of the EATCS, 122, 2017. Google Scholar
  24. R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld, and A. Shapira. Constructing near spanning trees with few local inspections. Random Struct. Algorithms, 50(2):183-200, 2017. Google Scholar
  25. R. Levi and D. Ron. A quasi-polynomial time partition oracle for graphs with an excluded minor. ACM Trans. Algorithms, 11(3):24:1-24:13, 2015. Google Scholar
  26. R. Levi, D. Ron, and R. Rubinfeld. Local algorithms for sparse spanning graphs. In Proceedings of the Eighteenth International Workshop on Randomization and Computation (RANDOM), pages 826-842, 2014. Google Scholar
  27. R. Levi, D. Ron, and R. Rubinfeld. Local algorithms for sparse spanning graphs. CoRR, abs/1402.3609, 2014. URL: http://arxiv.org/abs/1402.3609.
  28. Reut Levi, Dana Ron, and Ronitt Rubinfeld. Local algorithms for sparse spanning graphs. Algorithmica, 82(4):747-786, 2020. URL: https://doi.org/10.1007/s00453-019-00612-6.
  29. Ilan Newman and Christian Sohler. Every property of hyperfinite graphs is testable. SIAM J. Comput., 42(3):1095-1112, 2013. URL: https://doi.org/10.1137/120890946.
  30. Michal Parnas and Dana Ron. Testing the diameter of graphs. Random Struct. Algorithms, 20(2):165-183, 2002. URL: https://doi.org/10.1002/rsa.10013.
  31. M. Parter, R. Rubinfeld, A. Vakilian, and A. Yodpinyanee. Local computation algorithms for spanners. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, pages 58:1-58:21, 2019. Google Scholar
  32. R. Rubinfeld, G. Tamir, S. Vardi, and N. Xie. Fast local computation algorithms. In Proceedings of The Second Symposium on Innovations in Computer Science (ICS), pages 223-238, 2011. Google Scholar
  33. Yuichi Yoshida and Hiro Ito. Query-number preserving reductions and linear lower bounds for testing. IEICE Trans. Inf. Syst., 93-D(2):233-240, 2010. URL: https://doi.org/10.1587/transinf.E93.D.233.
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