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

I believe correctness about clique in even-hole-free graphs of graphclasses.org and the paper Vertex elimination orderings for hereditary graph classes, Pierre Aboulker, Pierre Charbit, Nicolas Trotignon, Kristina Vuskovic would imply $P=NP$.

Accordinth to graphclasses:

Clique: NP-complete by IS on complement,

the comeplement is related to IS on 2-subdivision citing S. Poljak, A note on the stable sets and coloring of graphs Comment. Math. Univ. Carolin. 15 (1974) 307-309 ZMath 0284.05105

According to the paper, p. 4:

(Improve) Maximum weighted clique in even-hole-free graphs in time $O(nm)$.

Related paper is LexBFS, structure and algorithms, Pierre Aboulker, Pierre Charbit, Maria Chudnovsky, Nicolas Trotignon, Kristina Vuskovic which claims the same.

The sources appear credible to me, though an error is certainly possible.

Added Third paper gives $O(n^2m)$ algorithm for MWC.

On graph classes, to get an explanation about complexity click on [+]Details.

What went wrong?

share|improve this question
add comment

1 Answer

up vote 13 down vote accepted

On http://www.graphclasses.org, an even hole means at least 6 vertices. If you open the details of the forbidden subgraphs list of the page for even-hole-free graphs and click on the link for even-hole, you'll see the definition.

In the articles you refer to, an even hole means at least 4 vertices. The even-hole-free of the articles is what on graphclasses.org is called even-cycle-free.

Hence, P=NP is still open.

share|improve this answer
    
Thank you, I should have read the fine print. –  joro Feb 18 at 15:16
add comment

Your Answer

 
discard

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.