FPT Algorithm for MWIS in (Long-Hole, k-Prism)-Free Graphs
Status open low confidence
The source paper provides a polynomial-time n^{O(k)} algorithm for MWIS in (long-hole, k-prism)-free graphs and remarks that the authors do not see how to upgrade this to an FPT algorithm parameterized by k without invoking a structural result of Abrishami et al. Targeted searches across arXiv and related literature through 2026 found no follow-up paper that resolves this FPT question either positively or negatively. The problem is 6 years old, so absence of evidence may be indicative of genuine difficulty.
Reviewer notes. No follow-up found. The open question is whether the n^{O(k)} algorithm of Theorem 1.1 can be made FPT in k for MWIS in (long-hole, k-prism)-free graphs. The authors note that invoking Abrishami et al. [1] (likely the series on induced subgraphs and tree decompositions of even-hole-free graphs) might be a path forward, but no paper appears to have completed this. Related progress exists on adjacent classes (no long claws, even-hole-free) but not on this specific class.
Context
Theorem 1.1 gives a polynomial-time algorithm running in time $n^{O(k)}$ for MWIS in (long-hole, $k$-prism)-free $n$-vertex graphs for any fixed integer $k > 0$. Immediately after stating the theorem the authors remark that extending this to a fixed-parameter tractable algorithm parameterized by $k$ appears to be out of reach with their techniques, unless the result of Abrishami et al. [1] is invoked.
Notes. Implicit open question stated in prose without a labelled environment. 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