2026-07-20T11:15:25Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7829 2024-03-06T10:41:15Z ddc:004 open_access

Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs Antunes, Daniel Mathieu, Claire Mustafa, Nabil H. Planar graphs Local search Hall's theorem Combinatorial optimization Expansion 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel Antunes and Claire Mathieu and Nabil H. Mustafa 2017 Is Part Of LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2017.8 urn:nbn:de:0030-drops-78293 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.8 eng https://creativecommons.org/licenses/by/3.0/legalcode