论文标题
Erdős-Hajnal猜想的算法削弱
An algorithmic weakening of the Erdős-Hajnal conjecture
论文作者
论文摘要
我们研究了$ h $ free图中最大独立集（MIS）问题的近似性（也就是说，不接收$ h $作为诱导子图的图）。作为一个动机，我们调查了以下猜想：对于每个固定图$ h $，存在常数$δ> 0 $，因此MIS可以是$ n^{1-δ} $ - 近似于$ h $ free Graphs，其中$ n $表示输入图的顶点的数量。我们首先证明了著名的Erdős-Hajnal猜想意味着我们的建设性版本。然后，我们证明满足我们猜想的一组图表$ h $在所谓的图形替换下是关闭的。这是$ h $ free图中MIS的已知多项式时间算法（例如$ p_6 $ - free和无叉图），这意味着我们的猜想适用于许多图形$ h $，而Erdős-hajnal的猜想仍然开放。然后，我们专注于改善某些图类别的常数$δ$：我们证明，经典的本地搜索算法提供了$ opt^{1- \ frac {1} {1} {t}} $ - $ k_ {t，t，t，t} $中的近似值 - a $ \ \ sqrt optage and optrape and $ - $ \ sqrt {n} $ - 无三角形图中的近似，不能将其改进到$ n^{\ frac {1} {4} {4} - \ varepsilon} $，对于任何$ \ varepsilon> 0 $，除非$ \ varepsilon> 0 $，除非$ np \ subseteq bpp $。更普遍地，我们表明存在一个常数的$ c $，因此围绕$γ$的图形误差不能为$ n^{\ frac {c}γ} $ - 近似。最多达到指数的恒定因素，这匹配了Monien和Speckenmeyer和Murphy的已知近似算法的比率。据我们所知，这是对某些$δ> 0 $的第一个强（即$ω（n^δ）$）对于适当的遗传类别中的最大独立设置的不适合性结果。
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_6$-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-\frac{1}{t}}$-approximation in $K_{t,t}$-free graphs (hence a $\sqrt{OPT}$-approximation in $C_4$-free graphs), and, while there is a simple $\sqrt{n}$-approximation in triangle-free graphs, it cannot be improved to $n^{\frac{1}{4}-\varepsilon}$ for any $\varepsilon > 0$ unless $NP \subseteq BPP$. More generally, we show that there is a constant $c$ such that MIS in graphs of girth $γ$ cannot be $n^{\frac{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.
