License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2014.187
URN: urn:nbn:de:0030-drops-48422
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2014/4842/
Bock, Adrian ;
Faenza, Yuri ;
Moldenhauer, Carsten ;
Ruiz-Vargas, Andres Jacinto
Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number
Abstract
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 Györi et al. [Györi 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.
BibTeX - Entry
@InProceedings{bock_et_al:LIPIcs:2014:4842,
author = {Adrian Bock and Yuri Faenza and Carsten Moldenhauer and Andres Jacinto Ruiz-Vargas},
title = {{Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number}},
booktitle = {34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)},
pages = {187--198},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-939897-77-4},
ISSN = {1868-8969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4842},
URN = {urn:nbn:de:0030-drops-48422},
doi = {10.4230/LIPIcs.FSTTCS.2014.187},
annote = {Keywords: stable set problem, independent set problem, approximation algorithms, odd cycle packing number, maximum subdeterminants}
}
|
Keywords: |
|
stable set problem, independent set problem, approximation algorithms, odd cycle packing number, maximum subdeterminants |
|
Collection: |
|
34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014) |
|
Issue Date: |
|
2014 |
|
Date of publication: |
|
12.12.2014 |
