Feedback Set Problems on Bounded-Degree (Planar) Graphs
Tian Bai, Yixin Cao, Mingyu Xiao · 2026
Read Feedback Set Problems on Bounded-Degree (Planar) Graphs by Tian Bai, Yixin Cao, Mingyu Xiao (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11407.txt.
Introduction
Tian Bai, Yixin Cao and Mingyu Xiao give a complete complexity classification for feedback set problems on bounded-degree digraphs, including the planar case. Both vertex and edge versions are NP-complete on digraphs of maximum degree three. On planar digraphs, feedback vertex set is polynomial-time solvable when every vertex has in-degree at most one, or out-degree at most one, and NP-complete otherwise. They also give tight degree bounds for connected feedback vertex set on undirected graphs, planar and non-planar.
Catalog record
| CREATOR | Tian Bai, Yixin Cao, Mingyu Xiao |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38352 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11407
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Feedback Set Problems on Bounded-Degree (Planar) Graphs Tian Bai, Yixin Cao, Mingyu Xiao Abstract 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 𝖭𝖯 {\mathsf{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 𝖭𝖯 {\mathsf{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. 1 Introduction In the feedback vertex set problem, we are given a graph G and an integer k , and are asked whether there exists a set of at most k vertices whose removal from G makes the graph acyclic. The input graph may be undirected or directed. There is also an edge/arc version, in which one deletes edges in undirected graphs or arcs in digraphs. We refer to these collectively as feedback set problems, and their solutions are feedback vertex sets , feedback edge sets , and feedback arc sets . For undirected graphs, the edge version is easy, because one only needs to keep a spanning forest. All the remaining variants are {\mathsf{NP}} -complete, and both directed variations appear in Karp’s list [ 9 ] . The classic reduction for the feedback vertex set problem on digraphs, which was attributed to the Algorithms Seminar at Cornell University, was from the vertex cover problem [ 9 ] . In the vertex cover problem, we are given a graph G and an integer k , and asked whether there exists a set of at most k vertices whose removal from G makes an edgeless graph. Since parallel edges and directions do not impact the vertex cover problem, we may always assume that G is a simple undirected graph. In this reduction, we replace each edge of G with two arcs of opposite directions. Since these two arcs already form a cycle, any feedback vertex set of the resulting digraph must contain one of the two ends, hence a vertex cover of G . The second reduction, devised by Lawler and Karp, reduces the feedback vertex set problem to the feedback arc set problem on digraphs: replace each vertex v with two new vertices v^{-} and v^{+} , connected by an arc v^{-}v^{+} , and reassign all the incoming arcs toward v to v^{-} and all the outgoing arcs from v to v^{+} . In the new digraph, each new vertex has either indegree at most one or outdegree at most one. In terms of breaking directed cycles, removing the arc v^{-}v^{+} has the same effect as removing either v^{-} or v^{+} in the new digraph, which is the same as removing v from the original digraph. Throughout this paper, we will refer to these two constructions as the doubling operation and the splitting operation . We can easily adapt the doubling operation to the feedback vertex set problem on undirected graphs. Instead of two arcs, we use two parallel edges between the same pair of adjacent vertices. 1 1 1 If simple graphs are demanded, we may subdivide one of the pair of edges; or equivalently, for each edge uv , we introduce a new vertex x and make it connected to u and v only. Since feedback set problems have wide applications, a natural question is their complexity on special graph classes. Much attention has been given to planar graphs. A graph is planar if it can be drawn in the plane so that edges intersect only at common endpoints. Indeed, in the very first systematic study of the feedback set problems, Younger [ 18 ] conjectured that the feedback arc set problem can be solved in polynomial time on planar graphs. This was later confirmed by Lucchesi and Younger [ 11 , 12 ] ; see also [ 10 ] . In contrast, the feedback vertex set problem remains {\mathsf{NP}} -hard on planar graphs because the vertex cover problem is {\mathsf{NP}} -hard on planar graphs [ 7 ] , and the doubling operation preserves planarity. (The splitting operation does not generally preserve planarity; see more discussions below.) Another natural question on the feedback set problems is to identify the threshold between tractability and intractability, with respect to the maximum degree of the input graph. It has been observed that the vertex degrees are intrinsic to this problem [ 3 ] . We use d(v) to denote the degree of a vertex v , i.e., the total number of edges/arcs incident to v , and the maximum degree of the graph is \Delta(G)=\max_{v\in V(G)}d(v). On the one hand, all variants are polynomial-time solvable when the maximum degree is at most two. On the other hand, since the vertex cover problem remains {\mathsf{NP}} -complete on planar graphs of maximum degree three [ 7 ] , the reduction by the doubling operation implies that the feedback vertex set problem remains {\mathsf{NP}} -complete on planar graphs, directed or not, of maximum degree six (see Section 2 ). These simple observations left a small gap, for which the literature contains incomplete and occasionally inaccurate claims. v_{b} v_{2} v_{4} v_{a} v_{c} v_{1} v_{5} (a) v_{b} v_{2} v_{4} v_{a} v_{c} v_{1} v_{5} v_{3} (b) Figure 1 : Speckenmeyer’s gadgets (a) for a degree-six vertex and (b) for a degree-five vertex [ 14 ] . The edges incident to the original vertex are assigned to the dashed lines in cyclic order. Note that a minimum feedback vertex set contains at least two vertices from each gadget (which have to be v_{a} and v_{c} if only two), and at most three vertices (no cycle visits any remaining vertex after vertices v_{2} , v_{4} , and v_{b} removed). For undirected graphs, Speckenmeyer and two other groups [ 17 , 6 ] closed the gap in the 1980s. In his Ph.D. thesis [ 14 ] , Speckenmeyer devised two simple gadgets, reproduced in Figure 1 (with a slight modification), to replace vertices of degree six and five. As a result, the feedback vertex set problem remains {\mathsf{NP}} -complete for undirected planar graphs of maximum degree at most four. It is a nice exercise to reduce the feedback vertex set problem on undirected graphs of maximum degree three to the same problem on undirected cubic graphs , i.e., undirected graphs in which every vertex has degree three. Speckenmeyer [ 15 , 16 ] observed that the feedback vertex set problem and the connected vertex cover problem, where the solution is required to induce a connected subgraph, are equivalent on undirected cubic graphs. This completes the classification for undirected graphs since the latter problem can be solved in polynomial time on undirected cubic graphs [ 17 , 6 ] . 2 2