Solving the Stable Set Problem in Terms of the Odd Cycle Packing Number

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



PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2014.187.pdf
  • Filesize: 399 kB
  • 12 pages

Document Identifiers

Author Details

Adrian Bock
Yuri Faenza
Carsten Moldenhauer
Andres Jacinto Ruiz-Vargas

Cite AsGet BibTex

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)
https://doi.org/10.4230/LIPIcs.FSTTCS.2014.187

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.
Keywords
  • stable set problem
  • independent set problem
  • approximation algorithms
  • odd cycle packing number
  • maximum subdeterminants

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. Agarwal, M. Charikar, K. Makarychev, and Y. Makarychev. O(√log n) Approximation Algorithms for Min UnCut, Min 2CNF Deletion, and Directed Cut Problems. In Proceedings of the Thirty-seventh Annual ACM Symposium on Theory of Computing, STOC'05, pages 573-581, New York, NY, USA, 2005. Google Scholar
  2. B. S. Baker. Approximation algorithms for NP-complete problems on planar graphs. Journal of the ACM, 41(1):153-180, January 1994. Google Scholar
  3. M. Di Summa, F. Eisenbrand, Y. Faenza, and C. Moldenhauer. On largest volume simplices and sub-determinants. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, California, USA, January 04-06, 2015, 2015. Google Scholar
  4. R. G. Downey and M. R. Fellows. Parametrized Complexity. Springer-Verlag New York, Inc., New York, NY, USA, 1999. Google Scholar
  5. Y. Faenza, G. Oriolo, and G. Stauffer. Solving the weighted stable set problem in claw-free graphs via decomposition. Journal of the ACM, 61(4), 2014. Google Scholar
  6. S. Fiorini, N. Hardy, B. Reed, and A. Vetta. Approximate min-max relations for odd cycles in planar graphs. Mathematical Programming, 110(1, Ser. B):71-91, 2007. Google Scholar
  7. J. W. Grossman, D. M. Kulkarni, and I. E. Schochetman. On the minors of an incidence matrix and its smith normal form. Linear Algebra and its Applications, 218:213 - 224, 1995. Google Scholar
  8. M. Grötschel, L. Lovász, and A. Schrijver. Stable sets in graphs. In Geometric Algorithms and Combinatorial Optimization, volume 2 of Algorithms and Combinatorics, pages 272-303. Springer Berlin Heidelberg, 1988. Google Scholar
  9. E. Györi, A. V. Kostochka, and T. Luczak. Graphs without short odd cycles are nearly bipartite. Discrete Mathematics, 163(1-3):279-284, 1997. Google Scholar
  10. J. Håstad. Clique is hard to approximate within n^(1-ε). In Acta Mathematica, pages 627-636, 1996. Google Scholar
  11. M. M. Halldórsson. Approximations of independent sets in graphs. In Klaus Jansen and José Rolim, editors, Approximation Algorithms for Combinatiorial Optimization, volume 1444 of Lecture Notes in Computer Science, pages 1-13. Springer Berlin Heidelberg, 1998. Google Scholar
  12. A. J. Hoffman and J. B. Kruskal. Integral boundary points of convex polyhedra. In Linear inequalities and related systems, Annals of Mathematics Studies, no. 38, pages 223-246. Princeton University Press, Princeton, N. J., 1956. Google Scholar
  13. R. Impagliazzo, R. Paturi, and F. Zane. Which problems have strongly exponential complexity? Journal of Computer and System Sciences, 63(4):512 - 530, 2001. Google Scholar
  14. R. M. Karp. Reducibility Among Combinatorial Problems. In Complexity of Computer Computations, pages 85-103. Plenum Press, 1972. Google Scholar
  15. K.-I. Kawarabayashi and B. Reed. Odd cycle packing. In Proceedings of the 42nd ACM symposium on Theory of computing, STOC'10, pages 695-704. ACM, 2010. Google Scholar
  16. D. Král, J.-S. Sereni, and L. Stacho. Min-max relations for odd cycles in planar graphs. SIAM Journal on Discrete Mathematics, 26(3):884-895, 2012. Google Scholar
  17. B. Monien. The complexity of embedding graphs into binary trees. In Fundamentals of Computation Theory, FCT'85, Cottbus, GDR, September 9-13, 1985, pages 300-309, 1985. Google Scholar
  18. B. Reed. Mangoes and blueberries. Combinatorica, 19:267-296, 1999. Google Scholar
  19. N. Sbihi. Algorithme de recherche d'un stable de cardinalite maximum dans un graphe sans etoile. Discrete Mathematics, 29(1):53 - 76, 1980. Google Scholar
  20. A. Schrijver. Theory of Linear and Integer Programming. Wiley, 1998. Google Scholar
  21. A. Schrijver. Combinatorial Optimization: Polyhedra and Efficiency, volume A. Springer, 2003. Google Scholar
  22. J. B. Shearer. The independence number of dense graphs with large odd girth. The Electronic Journal of Combinatorics, 2, 1995. Google Scholar
  23. D.B. West. Introduction to Graph Theory. Prentice Hall, 2000. Google Scholar
  24. D. Zuckerman. Linear degree extractors and the inapproximability of max clique and chromatic number. In Proceedings of the Thirty-eighth Annual ACM Symposium on Theory of Computing, STOC'06, pages 681-690, New York, NY, USA, 2006. ACM. Google Scholar
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