Skip to main content
edited tags
Link
Bjørn Kjos-Hanssen
  • 24.8k
  • 3
  • 58
  • 114
Added third paper
Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

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?

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.

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

What went wrong?

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?

Source Link
joro
  • 25.4k
  • 10
  • 66
  • 121

Seeming contradiction about P vs NP between graphclasses.org and at least two papers about clique in even-hole-free graphs

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.

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

What went wrong?