Parameterized Inapproximability of Independent Set in H-Free Graphs
Parameterized Inapproximability of Independent Set in H-Free Graphs
复制标题
H自由图中独立集的参数化不逼近性
DOI：
10.1007/s00453-022-01052-5
复制
发表时间：
2020
期刊：
影响因子：
1.1
通讯作者：
Paweł Rzaͅżewski
中科院分区：
文献类型：
--
作者：
P. Dvořák;A. Feldmann;Ashutosh Rai;Paweł Rzaͅżewski
我们研究无 H 图中的独立集问题，即排除某些固定图 H 作为诱导子图的图。我们证明了多项式时间算法和参数化算法的几个不可逼近性结果。 Halldórsson [SODA 1995] 表明，对于每个 $$\delta >0$$ δ > 0，独立集问题在 $$K_{1,d}$$ K 1 , d 无图中具有多项式时间 $$(\frac{d-1}{2}+\delta )$$ ( d - 1 2 + δ ) 近似算法。我们通过证明 $$K_{a,b}$$ Ka , b 无图承认多项式时间 $${\mathcal {O}}(\alpha (G)^{1-1/a})$$ O ( α ( G ) 1 - 1 / a ) - 近似来扩展此结果，其中 $$\alpha (G)$$ α ( G ) 是 G 中最大独立集的大小。此外，我们补充了 Halldórsson 的结果，表明对于某些 $$\gamma =\Theta (d/\log d),$$ γ = θ ( d / log d ) ，这些图没有多项式时间 $$\gamma $$ γ 近似算法，除非 NP = ZPP 。邦内特等人。 [Algorithmica 2020] 表明，由独立集大小 k 参数化的独立集在不包含 (1) 恒定长度至少 4 的循环、(2) 星 $$K_{1,4}$$ K 1 、 4 和 (3) 任何在恒定距离处具有两个度数至少为 3 的顶点的树的图上是 W[1] -hard。我们通过证明几乎同一类图的不同复杂度假设下的三个不可逼近性结果来加强这一结果（我们弱化了条件（1）和（2），即 G 不包含至少为 5 或 $$K_{1,5}$$ K 1 , 5 的恒定长度环）。首先，在 ETH 下，任何可计算函数 f 都没有 $$f(k) \cdot n^{o(k/\log k)}$$ f ( k ) · n o ( k / log k ) 算法。然后，在确定性 Gap-ETH 下，存在一个常数 $$\delta >0$$ δ > 0，使得在 $$f(k) \cdot n^{O(1)}$$ f ( k ) · n O ( 1 ) 时间内无法计算 $$\delta $$ δ 近似值。此外，在更强的随机 Gap-ETH 下，不存在运行时间 $$f(k) \cdot n^{o(\sqrt{k})}$$ f ( k ) · n o ( k ) 的近似算法。最后，我们考虑排除图 H 的参数化，并表明在 ETH 下，独立集在 H 无图中没有 $$n^{o(\alpha (H))}$$ n o ( α ( H ) ) 算法。此外，我们还证明，在确定性条件下，运行时 $$f(d,k) \cdot n^{{\mathcal {O}}(1)}$$ f ( d , k ) · n O ( 1 ) 的 $$K_{1,d}$$ K 1 , d 无图不存在 $$d/k^{o(1)}$$ d / k o ( 1 ) 近似算法缺口-ETH。
We study the Independent Set 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 $$\delta >0$$ δ > 0 the Independent Set problem has a polynomial-time $$(\frac{d-1}{2}+\delta )$$ ( d - 1 2 + δ ) -approximation algorithm in $$K_{1,d}$$ K 1 , d -free graphs. We extend this result by showing that $$K_{a,b}$$ K a , b -free graphs admit a polynomial-time $${\mathcal {O}}(\alpha (G)^{1-1/a})$$ O ( α ( G ) 1 - 1 / a ) -approximation, where $$\alpha (G)$$ α ( G ) is the size of a maximum independent set in G . Furthermore, we complement the result of Halldórsson by showing that for some $$\gamma =\Theta (d/\log d),$$ γ = Θ ( d / log d ) , there is no polynomial-time $$\gamma $$ γ -approximation algorithm for these graphs, unless NP = ZPP . Bonnet et al. [Algorithmica 2020] showed that Independent Set 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}$$ 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 conditions (1) and (2) that G does not contain a cycle of constant length at least 5 or $$K_{1,5}$$ K 1 , 5 ). First, under the ETH, there is no $$f(k) \cdot n^{o(k/\log k)}$$ f ( k ) · n o ( k / log k ) algorithm for any computable function f . Then, under the deterministic Gap-ETH, there is a constant $$\delta >0$$ δ > 0 such that no $$\delta $$ δ -approximation can be computed in $$f(k) \cdot n^{O(1)}$$ f ( k ) · 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})}$$ f ( k ) · n o ( k ) . Finally, we consider the parameterization by the excluded graph H , and show that under the ETH, Independent Set has no $$n^{o(\alpha (H))}$$ n o ( α ( H ) ) algorithm in H -free graphs. Also, we prove that there is no $$d/k^{o(1)}$$ d / k o ( 1 ) -approximation algorithm for $$K_{1,d}$$ K 1 , d -free graphs with runtime $$f(d,k) \cdot n^{{\mathcal {O}}(1)}$$ f ( d , k ) · n O ( 1 ) , under the deterministic Gap-ETH.
DOI：
10.1137/18m1166869
发表时间：
2020-01
期刊：
SIAM J. Comput.
影响因子：
--
作者：
Parinya Chalermsook;Marek Cygan;G. Kortsarz;Bundit Laekhanukit;Pasin Manurangsi;Danupon Nanongkai;L. Trevisan
通讯作者：
Parinya Chalermsook;Marek Cygan;G. Kortsarz;Bundit Laekhanukit;Pasin Manurangsi;Danupon Nanongkai;L. Trevisan
无H图中最大权独立集问题的拟多项式时间逼近方案
DOI：
10.1137/1.9781611975994.139
发表时间：
2020
期刊：
Proceedings of the annual ACMSIAM symposium on discrete algorithms
影响因子：
--
作者：
Chudnovsky, Maria.;Pillipczuk, Marcin.;Pillipczuk, Mihal;and Thomasse, Stephan.
通讯作者：
and Thomasse, Stephan.