Feedback Set Problems on Bounded-Degree (Planar) Graphs
This resolves open complexity questions for feedback set problems on bounded-degree and planar digraphs, providing a clear boundary between tractable and intractable cases.
The paper provides a complete complexity classification for feedback set problems on bounded-degree digraphs, including planar cases. It shows NP-completeness on digraphs of maximum degree three, and a dichotomy for planar digraphs based on degree constraints.
The feedback set problems are about removing the minimum number of vertices or edges from a graph to break all its cycles. Much effort has gone into understanding their complexity on planar graphs as well as on graphs of bounded degree. We obtain a complete complexity classification for these problems on bounded-degree digraphs, including the planar case. In particular, we show that both problems are $\NP$-complete on digraphs of maximum degree three, while on planar digraphs the feedback vertex set problem is polynomial-time solvable when each vertex has either indegree at most one or outdegree at most one, and $\NP$-complete otherwise. We also give tight degree bounds for the connected feedback vertex set problem on undirected graphs, both planar and non-planar. We close the paper with a historical account of results for feedback vertex set on undirected graphs of bounded degree.