# Separation of Anti-Hole Inequality

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.

-

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:

-
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