Research output: Contribution to Journal/Magazine › Journal article › peer-review
Research output: Contribution to Journal/Magazine › Journal article › peer-review
}
TY - JOUR
T1 - Exploring the relationship between max-cut and stable set relaxations
AU - Giandomenico, M
AU - Letchford, A N
PY - 2006/3
Y1 - 2006/3
N2 - The max-cut and stable set problems are two fundamental NP-hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.
AB - The max-cut and stable set problems are two fundamental NP-hard problems in combinatorial optimization. It has been known for a long time that any instance of the stable set problem can be easily transformed into a max-cut instance. Moreover, Laurent, Poljak, Rendl and others have shown that any convex set containing the cut polytope yields, via a suitable projection, a convex set containing the stable set polytope. We review this work, and then extend it in the following ways. We show that the rounded version of certain `positive semidefinite' inequalities for the cut polytope imply, via the same projection, a surprisingly large variety of strong valid inequalities for the stable set polytope. These include the clique, odd hole, odd antihole, web and antiweb inequalities, and various inequalities obtained from these via sequential lifting. We also examine a less general class of inequalities for the cut polytope, which we call odd clique inequalities, and show that they are, in general, much less useful for generating valid inequalities for the stable set polytope. As well as being of theoretical interest, these results have algorithmic implications. In particular, we obtain as a by-product a polynomial-time separation algorithm for a class of inequalities which includes all web inequalities.
KW - max-cut problem
KW - stable set problem
KW - polyhedral combinatorics
U2 - 10.1007/s10107-005-0604-5
DO - 10.1007/s10107-005-0604-5
M3 - Journal article
VL - 106
SP - 159
EP - 175
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1
ER -