Document Open Access Logo

On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem

Authors Stefano Coniglio, Stefano Gualandi

PDF
Thumbnail PDF

File

LIPIcs.SEA.2017.29.pdf
  • Filesize: 1.14 MB
  • 13 pages

Document Identifiers

Author Details

Stefano Coniglio
Stefano Gualandi

Cite As Get BibTex

Stefano Coniglio and Stefano Gualandi. On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem. In 16th International Symposium on Experimental Algorithms (SEA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 75, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.SEA.2017.29

Abstract

In the context of finding the largest stable set of a graph, rank inequalities prescribe that a stable set can contain, from any induced subgraph of the original graph, at most as many vertices as the stability number of the former. Although these inequalities subsume many of the valid inequalities known for the problem, their exact separation has only been investigated in few special cases obtained by restricting the induced subgraph to a specific topology.

In this work, we propose a different approach in which, rather than imposing topological restrictions on the induced subgraph, we assume the right-hand side of the inequality to be fixed to a given (but arbitrary) constant. We then study the arising separation problem, which corresponds to the problem of finding a maximum weight subgraph with a bounded stability number. After proving its hardness and giving some insights on its polyhedral structure, we propose an exact branch-and-cut method for its solution. Computational results show that the separation of topology-free rank inequalities with a fixed right-hand side yields a substantial improvement over the bound provided by the fractional clique polytope (which is obtained with rank inequalities where the induced subgraph is restricted to a clique), often better than that obtained with Lovász’s Theta function via semidefinite programming.

Subject Classification

Keywords
  • Maximum stable set problem
  • rank inequalities
  • cutting planes
  • integer programming
  • combinatorial optimization

Metrics

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

References

  1. Edoardo Amaldi, Stefano Coniglio, and Stefano Gualandi. Improving cutting plane generation with 0-1 inequalities by bi-criteria separation. Experimental Algorithms, pages 266-275, 2010. Google Scholar
  2. Edoardo Amaldi, Stefano Coniglio, and Stefano Gualandi. Coordinated cutting plane generation via multi-objective separation. Mathematical Programming, 143(1-2):87-110, 2014. Google Scholar
  3. Chitra Balasubramaniam and Sergiy Butenko. The maximum s-stable cluster problem. In INFORMS 2015 Annual Meeting. INFORMS, 2015. Google Scholar
  4. Chitra Balasubramaniam and Sergiy Butenko. The maximum s-stable cluster problem. Working paper, 2017. Google Scholar
  5. Václav Chvátal. The smallest triangle-free 4-chromatic 4-regular graph. Journal of Combinatorial Theory, 9(1):93-94, 1970. Google Scholar
  6. Vašek Chvátal. On certain polytopes associated with graphs. Journal of Combinatorial Theory, Series B, 18(2):138-154, 1975. Google Scholar
  7. Stefano Coniglio and Martin Tieves. On the generation of cutting planes which maximize the bound improvement. In Experimental Algorithms (14th International Symposium, SEA 2015, Paris, France, June 29 - July 1, 2015, Proceedings), volume 9125, pages 97-109. Springer International Publishing, 2015. Google Scholar
  8. Harlan Crowder, Ellis L. Johnson, and Manfred Padberg. Solving large-scale zero-one linear programming problems. Operations Research, 31(5):803-834, 1983. Google Scholar
  9. Monia Giandomenico, Adam N Letchford, Fabrizio Rossi, and Stefano Smriglio. Ellipsoidal relaxations of the stable set problem: theory and algorithms. SIAM Journal on Optimization, 25(3):1944-1963, 2015. Google Scholar
  10. Monia Giandomenico, Fabrizio Rossi, and Stefano Smriglio. Strong lift-and-project cutting planes for the stable set problem. Mathematical Programming, 141(1-2):165-192, 2013. Google Scholar
  11. Martin Grötschel, László Lovász, and Alexander Schrijver. The ellipsoid method and its consequences in combinatorial optimization. Combinatorica, 1(2):169-197, 1981. Google Scholar
  12. Martin Grötschel, Laszlo Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2 of Algorithms and Combinatorics. Springer-Verlag, 1988. Google Scholar
  13. Gerald Gruber and Franz Rendl. Computational experience with stable set relaxations. SIAM Journal on Optimization, 13(4):1014-1028, 2003. Google Scholar
  14. J. Hastad. Clique is hard to approximate within n^1-ε. Acta Mathematica, 182:105-142, 1999. Google Scholar
  15. Richard M. Karp. Reducibility among combinatorial problems. In R. Miller and J. Thatcher, editors, Proceedings of a Symposium on the Complexity of Computer Computations, The IBM Research Symposia Series. Plenum Press, 1972. Google Scholar
  16. Carlo Mannino and Antonio Sassano. Edge projection and the maximum cardinality stable set problem. DIMACS series in discrete mathematics and theoretical computer science, 26:205-219, 1996. Google Scholar
  17. Patric R. J. Östergård. A fast algorithm for the maximum clique problem. Discrete Applied Mathematics, 120(1):197-207, 2002. Google Scholar
  18. Steffen Rebennack, Marcus Oswald, Dirk Oliver Theis, Hanna Seitz, Gerhard Reinelt, and Panos M. Pardalos. A branch and cut solver for the maximum stable set problem. Journal of combinatorial optimization, 21(4):434-457, 2011. Google Scholar
  19. Fabrizio Rossi and Stefano Smriglio. A branch-and-cut algorithm for the maximum cardinality stable set problem. Operations Research Letters, 28(2):63-74, 2001. Google Scholar
  20. Yinyu Ye. Rudy random graph generator. URL: http://web.stanford.edu/~yyye/yyye/Gset.
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 About DROPS Imprint Privacy Contact