Combinatorial MWIS algorithm for perfect graphs

Combinatorial polynomial-time algorithm for MWIS in perfect graphs · arXiv:2003.05185

arXiv Problem medium confidence— first stated 2020-03-11

Authors: Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour

Status partial high confidence

The problem of designing a combinatorial polynomial-time algorithm for MWIS in perfect graphs (bypassing the ellipsoid-method-based algorithm of Grötschel, Lovász, and Schrijver) remains open in full generality. A verified partial result was published in 2024: Abrishami, Chudnovsky, Dibek, and Vušković give a combinatorial polynomial-time algorithm for perfect graphs of bounded degree that exclude a prism or a hole of length four as an induced subgraph, using even-set balanced separators and submodular function minimization. No paper resolving the full problem for all perfect graphs was found.

Cited literature (1)

partial Submodular Functions and Perfect Graphs (2024)

Tara Abrishami, Maria Chudnovsky, Cemil Dibek, Kristina Vušković · Mathematics of Operations Research · arXiv:2110.00108 · doi:10.1287/moor.2021.0302

Gives a combinatorial polynomial-time algorithm for MWIS in perfect graphs of bounded degree that do not contain a prism or a hole of length four as an induced subgraph, by showing such graphs admit a balanced separator that is a union of boundedly many even sets.

Reviewer notes. The full problem for all perfect graphs is open; the partial result (arXiv:2110.00108) handles only the bounded-degree prism-free C4-free case. The approach reduces to submodular function minimization, which the authors classify as combinatorial. No resolution of the general case was found in indexed literature up to May 2026.

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

Problem. Design a combinatorial polynomial-time algorithm for the Maximum Weight Independent Set problem in perfect graphs.

Context

The polynomial-time algorithm of Grötschel, Lovász, and Schrijver for MWIS in perfect graphs relies on the ellipsoid method. The authors explicitly note that designing a combinatorial polynomial-time algorithm for this problem remains an important open problem.

Notes. Stated in prose without a labelled environment: 'Designing a combinatorial polynomial-time algorithm for MWIS in perfect graphs remains an important open problem.' A classical community-wide open problem acknowledged by the authors as ongoing context.

Source paper

Induced subgraphs of bounded treewidth and the container method
Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Paweł Rzążewski, Paul Seymour · 2020-03-11
https://arxiv.org/abs/2003.05185 PDF source