Bock, Adrian ;
Faenza, Yuri ;
Moldenhauer, Carsten ;
RuizVargas, 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 nonadjacent vertices in an undirected graph G. This problem is NPhard to approximate with factor n^{1epsilon} 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 vertexdisjoint odd cycles in G. Equivalently, it is the logarithm of the largest absolute value of a subdeterminant of the edgenode 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 polynomialtime approximation scheme for graphs with ocp(G)=o(n/log(n)), and an alphaapproximation 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 exponentialtime 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 RuizVargas},
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 = {187198},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897774},
ISSN = {18688969},
year = {2014},
volume = {29},
editor = {Venkatesh Raman and S. P. Suresh},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2014/4842},
URN = {urn:nbn:de:0030drops48422},
doi = {10.4230/LIPIcs.FSTTCS.2014.187},
annote = {Keywords: stable set problem, independent set problem, approximation algorithms, odd cycle packing number, maximum subdeterminants}
}
2014
Keywords: 

stable set problem, independent set problem, approximation algorithms, odd cycle packing number, maximum subdeterminants 
Seminar: 

34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

Issue date: 

2014 
Date of publication: 

2014 