Combinatorial MIS algorithm on perfect graphs
Open problem: Combinatorial algorithm for MIS on perfect graphs · arXiv:1907.01083
Status open high confidence
The problem of finding a combinatorial algorithm for maximum independent set on perfect graphs — avoiding the ellipsoid method of Grötschel-Lovász-Schrijver — has been open since the early 1980s and remains unresolved as of 2026. The source paper raises this as a side remark noting that not even a combinatorial FPT algorithm for MIS on perfect graphs is known. A wide web search covering publications through 2026 found no paper that resolves either the polynomial or FPT combinatorial question for the full class of perfect graphs; recent algorithmic progress has focused on subclasses such as even-hole-free graphs and H-free graphs, leaving the perfect-graph case open.
Reviewer notes. No follow-up paper resolving this open problem was found. The problem is long-standing (open since Grötschel-Lovász-Schrijver 1981) and is mentioned only as a motivating side remark in the source paper. Recent work (e.g., quasi-polynomial-time algorithms for H-free graphs, polynomial algorithms for graphs excluding subdivided claws) addresses related but strictly different questions. The conjecture is closely related to the broader open question of de-linearizing the Lovász theta function machinery for graph optimization.
Context
The maximum independent set problem on perfect graphs is solvable in polynomial time via the ellipsoid method, but a combinatorial algorithm (i.e., one not relying on the ellipsoid method) is unknown. This is mentioned as a side remark motivating the study of related graph classes.
Notes. Stated as a known open problem in the community without a specific attribution cite; no labeled theorem environment.
Source paper
The independent set problem is FPT for even-hole-free graphs
Edin Husic, Stephan Thomasse, Nicolas Trotignon · 2019-10-06
https://arxiv.org/abs/1907.01083
PDF source