Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Given an undirected graph $G=(V,E)$ with no loops or multiple edges, a stable set is a set of vertices for which no two vertices are adjacent.

An induced subgraph $H$ of $G$ is called an odd-antihole when its complement is isomorphic to a cycle with odd length $\geq 5$.

By using polyhedral approaches in order to search for a maximum stable set (which belongs to $NP$), one stumbles upon the anti-hole inequality:

Identifying any stable set with its characteristic 0/1-vector, all such vectors $x$ satisfy the anti hole inequality $x(H)\leq 2$ for each antihole $H$.

The separation of the anti-hole inequality consists of determining whether a given node weight $x\in [0,1]^{|V|}$ violates any antihole-inequalities and asks for a certificate if it does.

So far I've found that as in 2007, the question whether this separation belongs to $P$ was an open problem.

I want to know if there has been any advances with this problem or whether there are any papers related to why it is difficult to prove either way. I can't seem to find any sources on the separation, my source from 2007 mentions this only briefly and sounds like it is common knowledge that this is an open problem, which implies that someone should have investigated at least a little.

share|improve this question
add comment

1 Answer 1

Here is one reference, a 2010 book that may lead to other literature: Polyhedral and Semidefinite Programming Methods in Combinatorial Optimization, by Levent Tunçel:


share|improve this answer
Is the separation explicitly adressed in this book? I don't have access to a copy of the book within our university as it seems. I have various sources for the general theory behind the stable set problem, it's really all about the separation - I may have worded that badly in the request. Nethertheless, thanks. –  Fran Apr 11 '13 at 13:12
@Fran: I don't own that book myself; sorry. It's available in Google books. –  Joseph O'Rourke Apr 11 '13 at 14:42
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.