Antiweb-wheel inequalities and their separation problems over the stable set polytopes (Q1600099): Difference between revisions

The problem of finding a maximum weight stable set problem of a graph \(G\) can be formulated as the problem of optimizing a linear function over the convex hull \(\text{STAB}(G)\) of incidence vectors of stable sets. It is impossible (unless \(\mathcal {NP}=co\;\mathcal {NP}\)) to obtain a ``concise'' characterization of \(\text{STAB}(G)\) as the solution set of a system of linear inequalities, and one of the approaches is to find large classes of valid inequalities with the property that the corresponding separation problem (given a point \(x^*\), find, if possible, an inequality in the class that \(x^*\) violates) is efficiently solvable. The authors give a polynomial time separation algorithm for the \((t)\)-antiweb inequalities of \textit{L. E. Trotter jun.} [Discrete Math. 12, 373--388 (1975; Zbl 0314.05111)] and for some larger classes of valid inequalities.