Independent Feedback Vertex Set linear forest complexity

Complexity of Independent Feedback Vertex Set for H-free graphs (linear forest cases) · arXiv:1707.09402

arXiv Informal medium confidence— first stated 2017-07-28

Authors: Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniel Paulusma

Status open medium confidence

No follow-up paper resolving the complexity of Independent Feedback Vertex Set for P_h-free graphs (h ≥ 6) or for general linear forests has been identified. Related problems—standard Feedback Vertex Set and Even Cycle Transversal on linear-forest-free graphs—have seen progress (polynomial time for sP₃-free and (sP₁+P₅)-free graphs, arXiv:2105.02736), but those results do not carry over to the independent variant. The classification for linear-forest cases of Independent Feedback Vertex Set therefore appears to remain open as of 2026.

Reviewer notes. The conjecture is from 2017; no resolution found after ~9 years in the indexed literature, which warrants medium rather than high confidence. The related (non-independent) Feedback Vertex Set and Even Cycle Transversal problems have been extended to broader linear-forest classes (arXiv:2105.02736), but techniques there rely on block-graph structure and do not obviously extend to the independent setting. Absence of visible progress over this timescale may indicate the problem is genuinely hard.

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

Informal. Only the cases where $H$ is a linear forest, that is, a disjoint union of paths, remain open for the complexity classification of \textsc{Independent Feedback Vertex Set} on $H$-free graphs. In particular, the case where $H$ is a single path $P_h$ with $h \geq 6$ has not yet been resolved.

Context

The authors prove NP-completeness when $H$ contains a claw or cycle, and polynomial-time solvability for $P_4$-free and $P_5$-free graphs, completing those cases. This leaves all linear-forest cases open toward a full complexity dichotomy for $H$-free graphs.

Notes. PDF source — stated in prose without a labelled environment. The provided text is truncated after Section 3; Section 6 is described in the introduction as explicitly surveying related open problems but its content was not included in the extraction, so additional formal conjectures/questions from that section may be missing.

Source paper

Independent Feedback Vertex Set for $P_5$-free Graphs
Marthe Bonamy, Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Daniel Paulusma · 2017-07-28
https://arxiv.org/abs/1707.09402 PDF source