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.SEA.2017.29
URN: urn:nbn:de:0030-drops-76266
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7626/
Go to the corresponding LIPIcs Volume Portal

Coniglio, Stefano ; Gualandi, Stefano

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

pdf-format:
LIPIcs-SEA-2017-29.pdf (1 MB)

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.

BibTeX - Entry

@InProceedings{coniglio_et_al:LIPIcs:2017:7626,
  author =	{Stefano Coniglio and Stefano Gualandi},
  title =	{{On the Separation of Topology-Free Rank Inequalities for the Max Stable Set Problem}},
  booktitle =	{16th International Symposium on Experimental Algorithms (SEA 2017)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-036-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{75},
  editor =	{Costas S. Iliopoulos and Solon P. Pissis and Simon J. Puglisi and Rajeev Raman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2017/7626},
  URN =		{urn:nbn:de:0030-drops-76266},
  doi =		{10.4230/LIPIcs.SEA.2017.29},
  annote =	{Keywords: Maximum stable set problem, rank inequalities, cutting planes, integer programming, combinatorial optimization}
}

Keywords: Maximum stable set problem, rank inequalities, cutting planes, integer programming, combinatorial optimization
Collection: 16th International Symposium on Experimental Algorithms (SEA 2017)
Issue Date: 2017
Date of publication: 07.08.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI