Document Open Access Logo

Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs

Authors Daniel Antunes, Claire Mathieu, Nabil H. Mustafa

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.8.pdf
  • Filesize: 0.78 MB
  • 13 pages

Document Identifiers

Author Details

Daniel Antunes
Claire Mathieu
Nabil H. Mustafa

Cite As Get BibTex

Daniel Antunes, Claire Mathieu, and Nabil H. Mustafa. Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 8:1-8:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.8

Abstract

Local search for combinatorial optimization problems is becoming a dominant algorithmic paradigm, with several papers using it to resolve long-standing open problems. In this paper, we prove the following `4-local' version of Hall's theorem for planar graphs: given a bipartite planar graph G = (B, R, E) such that |N(B')| >= |B'| for all |B'| <= 4, there exists a matching of size at least |B|/4 in G; furthermore this bound is tight. Besides immediately implying improved  bounds for several problems studied in previous papers, we find this variant of Hall's theorem to be of independent interest in graph theory.

Subject Classification

Keywords
  • Planar graphs
  • Local search
  • Hall's theorem
  • Combinatorial optimization
  • Expansion

Metrics

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

References

  1. Pankaj K. Agarwal and Nabil H. Mustafa. Independent set of intersection graphs of convex objects in 2D. Comput. Geom., 34(2):83-95, 2006. Google Scholar
  2. Rom Aschner, Matthew J. Katz, Gila Morgenstern, and Yelena Yuditsky. Approximation schemes for covering and packing. In Proceedings of the 7th International Workshop on Algorithms and Computation (WALCOM), pages 89-100, 2013. Google Scholar
  3. Norbert Bus, Shashwat Garg, Nabil H. Mustafa, and Saurabh Ray. Limits of local search: Quality and efficiency. Discrete & Computational Geometry, 57(3):607-624, 2017. Google Scholar
  4. Norbert Bus, Nabil H. Mustafa, and Saurabh Ray. Geometric hitting sets for disks: Theory and practice. In Proceedings of the 23rd Annual European Symposium on Algorithms (ESA), pages 903-914, 2015. Google Scholar
  5. Sergio Cabello and David Gajser. Simple PTAS’s for families of graphs excluding a minor. Discrete Applied Mathematics, 189:41-48, 2015. Google Scholar
  6. Timothy M. Chan. Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms, 46(2):178-189, 2003. Google Scholar
  7. Timothy M. Chan and Elyot Grant. Exact algorithms and APX-hardness results for geometric packing and covering problems. Comput. Geom., 47(2):112-124, 2014. Google Scholar
  8. Timothy M. Chan and Sariel Har-Peled. Approximation algorithms for maximum independent set of pseudo-disks. Discrete & Computational Geometry, 48(2):373-392, 2012. Google Scholar
  9. Robert Fraser. Algorithms for Geometric Covering and Piercing Problems. PhD thesis, University of Waterloo, 2012. Google Scholar
  10. Matt Gibson, Gaurav Kanade, Erik Krohn, and Kasturi R. Varadarajan. Guarding terrains via local search. JoCG, 5(1):168-178, 2014. Google Scholar
  11. Matt Gibson and Imran A. Pirwani. Algorithms for dominating set in disk graphs: Breaking the logn barrier. In Proceedings of the 18th Annual European Symposium on Algorithms (ESA), pages 243-254, 2010. Google Scholar
  12. Sathish Govindarajan, Rajiv Raman, Saurabh Ray, and Aniket Basu Roy. Packing and covering with non-piercing regions. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), pages 47:1-47:17, 2016. Google Scholar
  13. Dániel Marx. Efficient approximation schemes for geometric problems? In Proceedings of the 13th Annual European Symposium on Algorithms (ESA), pages 448-459, 2005. Google Scholar
  14. Dániel Marx. Parameterized complexity of independence and domination on geometric graphs. In Proceedings of the 2nd International Workshop on Parameterized and Exact Computation (IWPEC), pages 154-165, 2006. Google Scholar
  15. Nabil H. Mustafa, Rajiv Raman, and Saurabh Ray. Quasi-polynomial time approximation scheme for weighted geometric set cover on pseudodisks and halfspaces. SIAM J. Comput., 44(6):1650-1669, 2015. Google Scholar
  16. Nabil H. Mustafa and Saurabh Ray. Improved results on geometric hitting set problems. Discrete & Computational Geometry, 44(4):883-895, 2010. Google Scholar
  17. Nabil H. Mustafa and K. Varadarajan. Epsilon-approximations and Epsilon-nets. In J. E. Goodman, J. O'Rourke, and C. D. Tóth, editors, Handbook of Discrete and Computational Geometry. CRC Press LLC, 2017. Google Scholar
  18. Radoš Radoičić and Géza Tóth. The discharging method in combinatorial geometry and the Pach-Sharir conjecture. In Contemporary Mathematics: Surveys on Discrete and Computational Geometry, pages 319-342. American Mathematical Society, 2008. 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