MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I believe correctness about clique in even-hole-free graphs of 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|cite|improve this question
up vote 13 down vote accepted

On, 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 is called even-cycle-free.

Hence, P=NP is still open.

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

Your Answer


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.