Feedback set problems on bounded-degree (Planar) graphs

Abstract

The feedback set problems are about removing the minimum number of vertices or edges from a graph to break all its cycles. As fundamental problems in algorithmic graph theory, their complexity on planar and bounded-degree graphs has been extensively studied. While the exact degree thresholds for undirected graphs were conclusively settled in the 1980s, the analogous question for directed graphs, particularly for planar digraphs, has persisted as a fundamental open problem for nearly half a century, primarily due to the directional nature of arcs and stringent planar embedding constraints that obstruct classical degree-reduction techniques. In this paper, we completely settle this historical question. We also establish tight degree bounds for the connected feedback vertex set problem on undirected (planar) graphs.