MIS complexity for (even hole, K₄)-free graphs

Status open high confidence

The computational complexity of Maximum Independent Set for (even hole, $K_4$)-free graphs and for (theta, triangle)-free graphs remains open. Partial progress exists for subclasses: the source paper gives polynomial algorithms for (theta, triangle, $S_{i,j,k}$)-free and (even hole, pyramid, $K_t$, $S_{i,j,k}$)-free graphs via bounded treewidth, and arXiv:2203.06775 (2022) extends this by proving bounded treewidth for (even hole, diamond, pyramid, $K_t$)-free graphs, implying polynomial MIS for that subclass. Web searches through 2026 confirm that the full complexity question for the stated classes is unresolved.

Cited literature (1)

• partial Induced subgraphs and tree decompositions IV. (Even hole, diamond, pyramid)-free graphs (2022)
  Tara Abrishami, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl · arXiv preprint · arXiv:2203.06775

  Proves that for all $t > 0$ there exists $d_t \geq 0$ such that every (even hole, diamond, pyramid, $K_t$)-free graph has treewidth at most $d_t$ (Theorem 1.4), establishing a special case of Conjecture 1.5 from the source paper and implying polynomial-time MIS for this subclass of (even hole, $K_4$)-free graphs.

Reviewer notes. No paper resolving the full complexity question for (even hole, $K_4$)-free or (theta, triangle)-free graphs was found within the 5-call web search budget. A 2026 paper arXiv:2604.01816 '(Even hole, triangle)-free graphs revisited' appeared in search results and may be relevant (the (even hole, triangle)-free class is a proper subclass of (even hole, $K_4$)-free), but could not be verified within the call cap. The $O(\log n)$ treewidth bound for (theta, triangle)-free graphs from the source paper yields only quasi-polynomial MIS; polynomial-time complexity remains open.

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