文章基本信息
- 标题：An Algorithmic Weakening of the ErdÅ's-Hajnal Conjecture
- 本地全文：下载
- 作者：douard Bonnet ; Stphan Thomass ; Xuan Thang Tran 等
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2020
- 卷号：173
- 页码：23:1-23:18
- DOI：10.4230/LIPIcs.ESA.2020.23
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：We study the approximability of the Maximum Independent Set (MIS) problem in H-free graphs (that is, graphs which do not admit H as an induced subgraph). As one motivation we investigate the following conjecture: for every fixed graph H, there exists a constant δ > 0 such that MIS can be n^{1-δ}-approximated in H-free graphs, where n denotes the number of vertices of the input graph. We first prove that a constructive version of the celebrated ErdÅ's-Hajnal conjecture implies ours. We then prove that the set of graphs H satisfying our conjecture is closed under the so-called graph substitution. This, together with the known polynomial-time algorithms for MIS in H-free graphs (e.g. Pâ,-free and fork-free graphs), implies that our conjecture holds for many graphs H for which the ErdÅ's-Hajnal conjecture is still open. We then focus on improving the constant δ for some graph classes: we prove that the classical Local Search algorithm provides an OPT^{1-1/t}-approximation in K_{t, t}-free graphs (hence a â^S{OPT}-approximation in Câ,"-free graphs), and, while there is a simple â^Sn-approximation in triangle-free graphs, it cannot be improved to n^{1/4-ε} for any ε > 0 unless NP âS BPP. More generally, we show that there is a constant c such that MIS in graphs of girth γ cannot be n^{c/(γ)}-approximated. Up to a constant factor in the exponent, this matches the ratio of a known approximation algorithm by Monien and Speckenmeyer, and by Murphy. To the best of our knowledge, this is the first strong (i.e., Ω(n^δ) for some δ > 0) inapproximability result for Maximum Independent Set in a proper hereditary class.
- 关键词：Approximation; Maximum Independent Set; H-free Graphs; ErdÅ's-Hajnal conjecture
