论文标题
$ h $ free Graphs中独立集的参数化不Xibibibibibibibibibility
Parameterized Inapproximability of Independent Set in $H$-Free Graphs
论文作者
论文摘要
我们研究了$ h $ free图中的独立集（IS）问题，即，图形不包括一些固定图$ h $作为诱导子图。我们证明了多项式时间和参数化算法的几种不Xibimibility的结果。 Halldórsson[Soda 1995]表明，每$δ> 0 $都具有多项式时间$（\ frac {d-1} {2} {2}+δ）$ - $ k_ {1，d} $中的近似值 - 免费图形。我们通过证明$ k_ {a，b} $ - 免费图形来扩展此结果，接纳一个多项式时间$ o（α（g）^{1-1/a}）$ - 近似值，其中$α（g）$是$ g $中最大独立集的大小。此外，我们通过证明某些$γ=θ（d/\ log d）来补充Halldórsson的结果，除非NP = Zpp，否则$对于这些图形没有多项式时$γ$ -Approximation。 Bonnet等。 [IPEC 2018]表明，由独立集的尺寸$ k $参数化为w [1] - hard在图上不包含（1）恒定长度至少$ 4 $，（2）恒星$ k_ {1,4} $的恒定周期，以及（3）在恒定距离下至少有两个$ 3 $的顶点。 我们通过在不同的复杂性假设下证明几乎相同类别的图表（我们削弱条件（2）$ g $不包含$ k_ {1,5} $），从而增强了这一结果。首先，在ETH下，没有任何可计算函数$ f $的$ f（k）\ cdot n^{o（k/\ log k）} $算法。然后，在确定性的GAP-ETH下，有一个常数$δ> 0 $，因此可以在$ f（k）\ cdot n^{o（1）} $ time中计算$δ$ - approximation。另外，在更强的随机gap-eth下，没有使用运行时$ f（k）\ cdot n^{o（\ sqrt {k}}} $的近似算法。 最后，我们考虑由排除的图$ h $的参数化，并表明在eth下，没有$ n^{o（α（h）} $算法，$ h $ - free图中的算法，在gap-eth下，没有$ d/k^{o（1）} $ a $ k^{o k^yimatima n^{o（1）} $。
We study the Independent Set (IS) problem in $H$-free graphs, i.e., graphs excluding some fixed graph $H$ as an induced subgraph. We prove several inapproximability results both for polynomial-time and parameterized algorithms. Halldórsson [SODA 1995] showed that for every $δ>0$ IS has a polynomial-time $(\frac{d-1}{2}+δ)$-approximation in $K_{1,d}$-free graphs. We extend this result by showing that $K_{a,b}$-free graphs admit a polynomial-time $O(α(G)^{1-1/a})$-approximation, where $α(G)$ is the size of a maximum independent set in $G$. Furthermore, we complement the result of Halldórsson by showing that for some $γ=Θ(d/\log d),$ there is no polynomial-time $γ$-approximation for these graphs, unless NP = ZPP. Bonnet et al. [IPEC 2018] showed that IS parameterized by the size $k$ of the independent set is W[1]-hard on graphs which do not contain (1) a cycle of constant length at least $4$, (2) the star $K_{1,4}$, and (3) any tree with two vertices of degree at least $3$ at constant distance. We strengthen this result by proving three inapproximability results under different complexity assumptions for almost the same class of graphs (we weaken condition (2) that $G$ does not contain $K_{1,5}$). First, under the ETH, there is no $f(k)\cdot n^{o(k/\log k)}$ algorithm for any computable function $f$. Then, under the deterministic Gap-ETH, there is a constant $δ>0$ such that no $δ$-approximation can be computed in $f(k) \cdot n^{O(1)}$ time. Also, under the stronger randomized Gap-ETH there is no such approximation algorithm with runtime $f(k)\cdot n^{o(\sqrt{k})}$. Finally, we consider the parameterization by the excluded graph $H$, and show that under the ETH, IS has no $n^{o(α(H))}$ algorithm in $H$-free graphs and under Gap-ETH there is no $d/k^{o(1)}$-approximation for $K_{1,d}$-free graphs with runtime $f(d,k) n^{O(1)}$.
