Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number
Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number
复制标题
用奇环填充数求解稳定集问题
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Andres J. Ruiz
中科院分区：
文献类型：
--
作者：
Adrian Bock;Yuri Faenza;Carsten Moldenhauer;Andres J. Ruiz
经典的稳定集问题要求在无向图G中找到两两不相邻顶点的最大基数集。这个问题是NP-难的近似因子n ^{1-n}对于任何常数n> 0 [Hastad/Acta Mathematica/1996; Zuckerman/STOC/2006]，其中n是顶点的数量，因此在一般情况下没有希望得到好的近似。本文研究了图的稳定集问题，当图的奇圈填充数ocp（G）有界时，可能是n的函数。这是G中顶点不相交的奇圈的最大数目。等价地，它是G的边结点关联矩阵A_G的子行列式的最大绝对值的对数。因此，如果A_G是全幺模的，则ocp（G）= 0。因此，ocp（G）是A_G到1~n/3尺度上的全幺模矩阵集合的自然距离测度.
当ocp（G）= 0时，图是二部图，并且已知稳定集可以在多项式时间内求解。我们的结果表明，奇圈填充数确实强烈影响稳定集的可逼近性。更准确地说，我们得到了一个多项式时间的逼近方案的图ocp（G）= o（n/log（n）），和任何图的α-近似算法，其中α从一个常数光滑地增加到n，ocp（G）从O（n/log（n））增长到n/3。在困难方面，我们证明了，假设指数时间假设，稳定集不能在多项式时间内解决，如果ocp（G）= Ω（log ^{1 + Ω}（n））的某些ω> 0。最后，我们推广了Gyori等人[Gyori et al./离散数学/1997]，并表明没有小重量的奇数圈的图可以通过删除少量的顶点而成为二部图。这使我们能够扩展我们的一些上述结果的加权稳定集问题。
The classic stable set problem asks to find a maximum cardinality set of pairwise non-adjacent vertices in an undirected graph G. This problem is NP-hard to approximate with factor n^{1-epsilon} for any constant epsilon>0 [Hastad/Acta Mathematica/1996; Zuckerman/STOC/2006], where n is the number of vertices, and therefore there is no hope for good approximations in the general case. We study the stable set problem when restricted to graphs with bounded odd cycle packing number ocp(G), possibly by a function of n. This is the largest number of vertex-disjoint odd cycles in G. Equivalently, it is the logarithm of the largest absolute value of a sub-determinant of the edge-node incidence matrix A_G of G. Hence, if A_G is totally unimodular, then ocp(G)=0. Therefore, ocp(G) is a natural distance measure of A_G to the set of totally unimodular matrices on a scale from 1 to n/3.
When ocp(G)=0, the graph is bipartite and it is well known that stable set can be solved in polynomial time. Our results imply that the odd cycle packing number indeed strongly influences the approximability of stable set. More precisely, we obtain a polynomial-time approximation scheme for graphs with ocp(G)=o(n/log(n)), and an alpha-approximation algorithm for any graph where alpha smoothly increases from a constant to n as ocp(G) grows from O(n/log(n)) to n/3. On the hardness side, we show that, assuming the exponential-time hypothesis, stable set cannot be solved in polynomial time if ocp(G)=Omega(log^{1+epsilon}(n)) for some epsilon>0. Finally, we generalize a theorem by Gyori et al. [Gyori et al./Discrete Mathematics/1997] and show that graphs without odd cycles of small weight can be made bipartite by removing a small number of vertices. This allows us to extend some of our above results to the weighted stable set problem.