Stable set for bounded ocp, unbounded genus
Open question on stable set for bounded ocp and arbitrary Euler genus · arXiv:1908.06300
Status open high confidence
The source paper (arXiv:1908.06300, SODA 2020) establishes a polynomial-time algorithm for the stable set problem when both ocp(G) \leq k and the Euler genus are fixed constants, but leaves open whether the genus restriction can be dropped for k \geq 2. A closely related follow-up by the same authors (arXiv:1911.12179, Mathematical Programming 2022) gives polynomial-size extended formulations for the case ocp(G) \leq 1 without any genus constraint, but that case was already polynomial-time via the bimodular algorithm before the source paper. No paper resolving the general question (bounded ocp, arbitrary Euler genus, k \geq 2) was found in the literature through May 2026.
Reviewer notes. The open question for arbitrary Euler genus with ocp(G) \leq k (k \geq 2) remains unresolved as of May 2026. The k=1 case (no two disjoint odd cycles) was already tractable before the source paper via the bimodular algorithm; arXiv:1911.12179 (Conforti, Fiorini, Huynh, Weltge, Math. Programming 2022) further gives an O(n^2)-size extended formulation for k=1 without genus restriction, but this does not directly resolve the open question for larger k. No counterexample or general algorithm dropping the genus constraint was found.
Context
The paper's main result (Theorem 2) gives a polynomial-time algorithm when both the odd cycle packing number and the Euler genus are fixed constants. Immediately after stating this result the authors note they do not know whether the genus bound can be dropped while retaining polynomial-time solvability.
Notes. Stated as 'we do not know whether'; no labelled theorem environment.
Source paper
The stable set problem in graphs with bounded genus and bounded odd cycle packing number
Michele Conforti, Samuel Fiorin, Tony Huynh, Gwenaël Joret, Stefan Weltge · 2019-08-17
https://arxiv.org/abs/1908.06300
PDF source