2026-07-24T09:35:44Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:12889 2024-03-06T10:51:00Z ddc:004 open_access

An Algorithmic Weakening of the Erdős-Hajnal Conjecture Bonnet, Édouard Thomassé, Stéphan Tran, Xuan Thang Watrigant, Rémi Approximation Maximum Independent Set H-free Graphs Erdős-Hajnal conjecture 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 √{OPT}-approximation in C₄-free graphs), and, while there is a simple √n-approximation in triangle-free graphs, it cannot be improved to n^{1/4-ε} for any ε > 0 unless NP ⊆ 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Édouard Bonnet and Stéphan Thomassé and Xuan Thang Tran and Rémi Watrigant 2020 Is Part Of LIPIcs, Volume 173, 28th Annual European Symposium on Algorithms (ESA 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ESA.2020.23 urn:nbn:de:0030-drops-128894 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2020.23 eng https://creativecommons.org/licenses/by/3.0/legalcode