1 Search Results for "Bock, Adrian"

Document
DOI: 10.4230/LIPIcs.FSTTCS.2014.187
Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number

Authors: Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres Jacinto Ruiz-Vargas

Published in: LIPIcs, Volume 29, 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014)

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.
Cite as

Adrian Bock, Yuri Faenza, Carsten Moldenhauer, and Andres Jacinto Ruiz-Vargas. Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number. In 34th International Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 29, pp. 187-198, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{bock_et_al:LIPIcs.FSTTCS.2014.187,
  author =	{Bock, Adrian and Faenza, Yuri and Moldenhauer, Carsten and Ruiz-Vargas, Andres Jacinto},
  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 =	{Raman, Venkatesh and Suresh, S. P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2014.187},
  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}
}
  • Refine by Author
  • 1 Bock, Adrian
  • 1 Faenza, Yuri
  • 1 Moldenhauer, Carsten
  • 1 Ruiz-Vargas, Andres Jacinto

  • Refine by Classification

  • Refine by Keyword
  • 1 approximation algorithms
  • 1 independent set problem
  • 1 maximum subdeterminants
  • 1 odd cycle packing number
  • 1 stable set problem

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2014

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact