MIS tractability in bounded-iocp graphs

Informal conjecture: MIS tractable in bounded-iocp graphs · arXiv:2206.00594

arXiv Informal medium confidence— first stated 2024-02-16

Authors: Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek

Status open high confidence

The conjecture that Maximum Independent Set is tractable in graphs with bounded induced odd cycle packing number (iocp) remains open. The source paper (arXiv:2206.00594) itself describes this as 'a surprising and formidable generalisation' of Conjecture 1.3 (MIS polynomial in Ok-free graphs) and of the known polynomial-time result for bounded ocp; no follow-up resolving it was found in a wide web search. The related prior work by Dvořák (arXiv:2001.02411, J. Graph Theory 2023) handles approximation in bounded-iocp graphs with additional VC-dimension constraints but does not settle exact tractability.

Reviewer notes. No follow-up paper resolving or making partial progress on this conjecture was found across three targeted web searches and verification of the source paper's full HTML. The conjecture is informal and appears only in the discussion section of 2206.00594. Bounded iocp is strictly weaker than bounded icp, making this a harder graph class; even for bounded icp only quasi-polynomial time is known in general (with polynomial for sparse graphs). Dvořák's arXiv:2001.02411 (pre-dates conjecture) gives a QPTAS for independence number under bounded iocp, but exact polynomial time remains open.

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

Informal. Maximum Independent Set could be tractable in graphs with bounded $\mathrm{iocp}$ (induced odd cycle packing number).

Context

The paper establishes tractability of MIS for graphs with bounded induced cycle packing number ($\mathrm{icp}$, i.e., $\mathcal{O}_k$-free graphs) in the sparse case, and quasipolynomial time in general. The authors remark that extending this to bounded $\mathrm{iocp}$ would be a surprising and formidable generalisation of Conjecture 1.3 and of the known polynomial-time result for bounded $\mathrm{ocp}$ (odd cycle packing number).

Notes. Stated as a speculative remark in prose ('As far as we can tell, MIS could even be tractable in graphs with bounded iocp'); authors treat it seriously as a potential generalisation.

Source paper

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
Marthe Bonamy, Édouard Bonnet, Hugues Déprés, Louis Esperet, Colin Geniet, Claire Hilaire, Stéphan Thomassé, Alexandra Wesolek · 2024-02-16
https://arxiv.org/abs/2206.00594