Combinatorial MIS algorithm for perfect graphs

Combinatorial Polynomial-Time Algorithm for MIS/MWIS in Perfect Graphs · arXiv:1903.04761

arXiv Problem medium confidence— first stated 2020-01-16

Authors: Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé

Status partial medium confidence

The open problem of finding a combinatorial polynomial-time algorithm for MIS/MWIS in perfect graphs remains largely unresolved. Abrishami and Chudnovsky (arXiv:2110.00108, 2021) made partial progress by giving a combinatorial polynomial-time algorithm for MWIS in perfect graphs of bounded degree that contain no prism and no hole of length four as induced subgraphs—directly addressing the C4-free subcase highlighted in the source paper, but under additional structural restrictions. No combinatorial poly-time algorithm is known for all perfect graphs or even for all C4-free perfect graphs without the bounded-degree and prism-free conditions.

Cited literature (1)

partial Submodular functions and perfect graphs (2021)

Tara Abrishami, Maria Chudnovsky · arXiv preprint · arXiv:2110.00108

Gives a combinatorial polynomial-time algorithm for MWIS in perfect graphs of bounded degree with no prism and no hole of length four, making partial progress on the C4-free case of the open problem.

Reviewer notes. The full open problem (combinatorial poly-time for all perfect graphs, or even all C4-free perfect graphs) remains open as of 2026. The 2110.00108 result is the closest identified partial progress, but requires both bounded degree and absence of prisms in addition to no C4. No purely combinatorial algorithm for general perfect graphs or even unbounded-degree C4-free perfect graphs has been found.

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

Problem. No combinatorial polynomial-time algorithm is known for any of MIS, MWIS, MC, and MWC in perfect graphs; finding one is a major open problem in the field. At the moment we do not even have a polynomial-time combinatorial algorithm to solve MIS in perfect graphs with no hole of length four.

Context

The Grötschel–Lovász–Schrijver algorithm solves MWIS on perfect graphs via the ellipsoid method, which the authors distinguish from combinatorial algorithms (roughly, algorithms not using division and operating directly on vertices and edges). Even the restricted case of MIS in perfect graphs with no $C_4$ (hole of length four) lacks a combinatorial polynomial-time algorithm.

Notes. A long-standing community open problem cited as motivation in the introduction; not introduced by these authors. PDF source — math may be garbled.

Source paper

On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five
Maria Chudnovsky, Marcin Pilipczuk, Michał Pilipczuk, Stéphan Thomassé · 2020-01-16
https://arxiv.org/abs/1903.04761 PDF source