3
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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:


           AntiHoles

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$
    – Fran
    Apr 11, 2013 at 13:12
  • $\begingroup$ @Fran: I don't own that book myself; sorry. It's available in Google books. $\endgroup$ Apr 11, 2013 at 14:42
  • $\begingroup$ (Apologies for the poor-quality snapshot.) $\endgroup$ May 19, 2017 at 21:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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