# 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.

-