Abstract
We study the approximability of the Maximum Independent Set (MIS) problem in Hfree 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 Hfree graphs, where n denotes the number of vertices of the input graph. We first prove that a constructive version of the celebrated ErdősHajnal conjecture implies ours. We then prove that the set of graphs H satisfying our conjecture is closed under the socalled graph substitution. This, together with the known polynomialtime algorithms for MIS in Hfree graphs (e.g. P₆free and forkfree graphs), implies that our conjecture holds for many graphs H for which the ErdősHajnal 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^{11/t}approximation in K_{t, t}free graphs (hence a √{OPT}approximation in C₄free graphs), and, while there is a simple √napproximation in trianglefree 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.
BibTeX  Entry
@InProceedings{bonnet_et_al:LIPIcs:2020:12889,
author = {{\'E}douard Bonnet and St{\'e}phan Thomass{\'e} and Xuan Thang Tran and R{\'e}mi Watrigant},
title = {{An Algorithmic Weakening of the ErdősHajnal Conjecture}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {23:123:18},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12889},
URN = {urn:nbn:de:0030drops128894},
doi = {10.4230/LIPIcs.ESA.2020.23},
annote = {Keywords: Approximation, Maximum Independent Set, Hfree Graphs, ErdősHajnal conjecture}
}
Keywords: 

Approximation, Maximum Independent Set, Hfree Graphs, ErdősHajnal conjecture 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 