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?


1 Answer 1


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.


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.