MIS complexity in even-hole-free graphs

Status partial high confidence

The complexity of maximum independent set in even-hole-free graphs (polynomial-time vs. NP-hard) remains open. Significant partial progress has been made: Abrishami et al. (arXiv:2005.05042, 2020) give a polynomial-time MWIS algorithm for (theta, pyramid, prism, turtle)-free graphs, subsuming the (pyramid, even hole)-free result. More decisively, Chudnovsky, Gartland, Hajebi, Lokshtanov, and Spirkl (arXiv:2407.08927, 2024) prove that every n-vertex even-hole-free graph has tree independence number at most c·log^{10}(n), yielding a quasi-polynomial time algorithm for MWIS across the full even-hole-free class—a major advance that nonetheless leaves the polynomial vs. NP-hard question unresolved.

Cited literature (2)

• partial Graphs with polynomially many minimal separators (2020)
  Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Stéphan Thomassé, Nicolas Trotignon · arXiv preprint · arXiv:2005.05042

  Proves that (theta, pyramid, prism, turtle)-free graphs have at most |V(G)|^{18} minimal separators, yielding a polynomial-time MWIS algorithm for this class (which implies polynomial time for (pyramid, even hole)-free graphs, a proper subclass of even-hole-free graphs).

• partial Tree Independence Number IV. Even-hole-free Graphs (2024)
  Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl · arXiv preprint · arXiv:2407.08927

  Proves that every n-vertex even-hole-free graph has tree independence number at most c·log^{10}(n), implying MWIS is solvable in quasi-polynomial time for the entire even-hole-free class.

Reviewer notes. The open problem (polynomial vs. NP-hard for MIS in even-hole-free graphs) is still open as of May 2026. The quasi-polynomial algorithm of arXiv:2407.08927 is the strongest known result for the full class. Both since_posted URLs were verified via WebFetch.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).