文章基本信息

标题：Combinatorics of Local Search: An Optimal 4-Local Hall's Theorem for Planar Graphs
本地全文：下载
作者：Daniel Antunes ; Claire Mathieu ; Nabil H. Mustafa 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：87
页码：8:1-8:13
DOI：10.4230/LIPIcs.ESA.2017.8
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Planar graphs; Local search; Hall's theorem; Combinatorial optimization; Expansion