MWIS polynomial-time on even-hole-free graphs
Open Problem: Polynomial-time MWIS on even-hole-free graphs · arXiv:2407.08927
Status open high confidence
The source paper (arXiv:2407.08927, published at SODA 2025) establishes a quasi-polynomial-time algorithm for MWIS on even-hole-free graphs by proving that every n-vertex even-hole-free graph has a tree decomposition with each bag having independence number at most c log^{10} n; the polynomial-time question is explicitly left open. A 2026 preprint (arXiv:2604.01816) proves bounded treewidth (≤ 4) for the more restricted class of (even-hole, triangle)-free graphs, implying polynomial-time MWIS for that proper subclass, but the general even-hole-free case remains unresolved. No paper has been found that settles the polynomial-time question for all even-hole-free graphs.
Cited literature (1)
-
Proves treewidth ≤ 4 for (theta, triangle, wac)-free graphs (a proper subclass of even-hole-free graphs also excluding triangles), implying polynomial-time MWIS for that restricted subclass but not for general even-hole-free graphs.
Reviewer notes. The source paper itself (SODA 2025) is the strongest known positive result: quasi-polynomial time via tree independence number O(log^10 n). The paper explicitly notes that the quasi-polynomial bound is consistent with NP-hardness, so the complexity of MWIS on even-hole-free graphs remains open. The 2026 paper arXiv:2604.01816 about (even hole, triangle)-free graphs achieves treewidth ≤ 4 for a more restricted subclass; authors were not extractable from the abstract page within the 5-call cap.
Context
On even-hole-free graphs, Maximum Weight Clique is known to be polynomial-time solvable, but the question of whether a polynomial-time algorithm exists for Maximum Weight Independent Set remains open. This is in stark contrast to perfect graphs, for which polynomial-time algorithms have been known since 1981. The present paper gives a quasi-polynomial-time algorithm via a polylogarithmic tree independence number bound, but the polynomial-time question is not resolved.
Notes. Stated in prose in the introduction without a labelled theorem environment; the paper provides quasi-polynomial-time progress but leaves polynomial-time open.
Source paper
Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov, Sophie Spirkl · 2024-07-12
https://arxiv.org/abs/2407.08927