pith. the verified trust layer for science. sign in

arxiv: 2605.11407 · v1 · submitted 2026-05-12 · 💻 cs.CC

Feedback Set Problems on Bounded-Degree (Planar) Graphs

Tian Bai , Yixin Cao , Mingyu Xiao This is my paper

Pith reviewed 2026-05-13 01:15 UTC · model grok-4.3

classification 💻 cs.CC
keywords feedback vertex setfeedback arc setNP-completenessplanar digraphsbounded degreeconnected feedback vertex setcomplexity classificationdigraphs
0
0 comments X p. Extension

The pith

Feedback vertex and arc set problems are NP-complete on digraphs of maximum degree three, but admit a polynomial-time case on certain planar digraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper maps the exact complexity boundary for minimum feedback vertex set and feedback arc set on digraphs whose vertices have small degrees, including the planar case. It proves that both problems stay NP-complete once the maximum degree reaches three. For planar digraphs it identifies a clean tractable island: feedback vertex set can be solved efficiently precisely when every vertex has indegree at most one or outdegree at most one; any other combination of degree restrictions leaves the problem NP-complete. The authors also locate the precise degree thresholds separating the polynomial-time and NP-complete regimes for the connected version of feedback vertex set on both planar and general undirected graphs. These thresholds tell practitioners exactly when exact cycle-hitting algorithms become unavailable and approximations or heuristics must be used instead.

Core claim

Both the feedback vertex set problem and the feedback arc set problem are NP-complete on digraphs with maximum degree three. On planar digraphs, feedback vertex set admits a polynomial-time algorithm exactly when every vertex has either indegree at most one or outdegree at most one; the problem is NP-complete in every other planar case. For the connected feedback vertex set problem on undirected graphs the paper supplies tight degree bounds that separate its polynomial-time and NP-complete regimes, both for planar and non-planar instances.

What carries the argument

Polynomial-time reductions that embed known NP-complete instances into maximum-degree-three digraphs while preserving the cycle-hitting requirement, together with a specialized algorithm that exploits the global indegree or outdegree restriction to compute a minimum feedback vertex set on the restricted planar graphs.

Load-bearing premise

The reductions from known NP-complete problems correctly produce only instances of maximum degree three, and the algorithm for the restricted planar case always returns an optimal feedback vertex set.

What would settle it

Either a polynomial-time algorithm that correctly solves feedback arc set on an infinite family of degree-three digraphs, or a single planar digraph in which every vertex has indegree and outdegree at least two yet the claimed algorithm returns a non-minimal feedback vertex set.

Figures

Figures reproduced from arXiv: 2605.11407 by Mingyu Xiao, Tian Bai, Yixin Cao.

Figure 1
Figure 1. Figure 1: Speckenmeyer’s gadgets (a) for a degree-six vertex and (b) for a degree-five vertex [ [PITH_FULL_IMAGE:figures/full_fig_p003_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: A vertex v in (a) is replaced by a directed path on d(v) new vertices in (b). Theorem 2. Both feedback set problems remain NP-complete for digraphs of maximum degree at most three. Proof. Let D be a digraph. We transform D into another digraph D′ by performing the following operations on each vertex v of D. We introduce a directed path, denoted as P(v), on d(v) new vertices: v − 1 v − 2 · · · v − d−(v) v +… view at source ↗
Figure 3
Figure 3. Figure 3: (a) An undirected planar cubic graph G, where the edges in F are represented as thick lines, and (b) an irregular embedding of the digraph obtained from G by the doubling opera￾tion. Note that the two shadowed vertices have (−, −, +, +, −, +) embedding, while all the others (+, +, −, −, +, −). Lemma 7. Let G be an undirected planar cubic graph. The digraph D obtained by the doubling operation admits an irr… view at source ↗
Figure 4
Figure 4. Figure 4: (a) A vertex v with (−, −, +, +, −, +) embedding, and (b) the gadget for v. An irregular embedding allows us to group the pair of consecutive incoming arcs and the pair of outgoing arcs for the gadget. In [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: (a) Two adjacent vertices of G and edges incident to them, where the numbers on edges denote their cyclic order. For example, the edge uv is the fourth of u and the second of v. (b) The gadgets P(u), P(uv), and P(v), which comprise 8, 16n, and 8 vertices, respectively. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_5.png] view at source ↗
read the original 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 $\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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper presents a complete complexity classification for the feedback vertex set (FVS) and feedback arc set (FAS) problems on digraphs of maximum degree three, including the planar case. It proves NP-completeness for both problems on max-degree-3 digraphs. For planar digraphs, FVS is polynomial-time solvable when every vertex has indegree at most 1 or outdegree at most 1, and NP-complete otherwise. The manuscript also establishes tight degree bounds for the connected FVS problem on undirected graphs (both planar and non-planar) and concludes with a historical account of FVS results on bounded-degree undirected graphs.

Significance. If the results hold, this work completes an important classification for fundamental feedback set problems on bounded-degree and planar graphs, which are widely studied in algorithmic graph theory and complexity. The planar FVS dichotomy under per-vertex degree restrictions is a notable contribution that clarifies tractability boundaries. The tight bounds for connected FVS close open questions in the undirected setting, and the historical survey provides valuable context and credits prior contributions appropriately.

minor comments (2)
  1. The abstract summarizes the main results effectively but could explicitly state the specific tight degree bounds obtained for connected FVS to provide immediate insight without requiring readers to consult the body of the paper.
  2. In the historical account section, ensure that all referenced prior results are clearly distinguished from the new contributions and that any open questions mentioned are precisely articulated.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive evaluation of the manuscript, the accurate summary of our contributions, and the recommendation to accept. No major comments were raised that require a point-by-point response.

Circularity Check

0 steps flagged

No significant circularity in complexity classification

full rationale

The paper establishes NP-completeness for feedback vertex/arc set on maximum-degree-3 digraphs via polynomial reductions from known NP-complete problems, and provides a polynomial-time algorithm for the restricted planar FVS case (indegree ≤1 or outdegree ≤1 per vertex). These are standard proof techniques relying on external reductions and algorithmic correctness, with no self-definitional steps, fitted parameters renamed as predictions, or load-bearing self-citations that reduce the central claims to their own inputs. The derivation chain is self-contained against external benchmarks and does not exhibit any of the enumerated circularity patterns.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The results depend on the standard axioms of computational complexity theory, such as the definition of NP-completeness via polynomial reductions, and basic properties of graphs. No free parameters or invented entities are introduced.

axioms (1)
  • standard math Standard definitions of NP-completeness via polynomial-time reductions and basic graph theory concepts such as directed graphs, planarity, and degree bounds.
    These are foundational assumptions from prior literature invoked to state the classification results.

pith-pipeline@v0.9.0 · 5442 in / 1351 out tokens · 47540 ms · 2026-05-13T01:15:44.775848+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

19 extracted references · 19 canonical work pages

  1. [1]

    2022.101900

    Hans L. Bodlaender, Corinne Feremans, Alexander Grigoriev, Eelko Penninkx, Ren´ e Sitters, and Thomas Wolle. On the minimum corridor connection problem and other generalized geometric problems.Computational Geometry, 42(9):939–951, 2009.doi:10.1016/j.comgeo. 2009.05.001

    work page doi:10.1016/j.comgeo 2009

  2. [2]

    Cycle transversals in perfect graphs and cographs.Theoretical Computer Science, 469:15–23,

    Andreas Brandst¨ adt, Synara Brito, Sulamita Klein, Loana Tito Nogueira, and F´ abio Protti. Cycle transversals in perfect graphs and cographs.Theoretical Computer Science, 469:15–23,

    work page

  3. [3]

    With Corrigendum in the same journal, 487:103-105, 2013.doi:10.1016/j.tcs.2012. 10.030

    work page doi:10.1016/j.tcs.2012 2013

  4. [4]

    DX.2024.7

    Yixin Cao. A naive algorithm for feedback vertex set. In Raimund Seidel, editor,Proceedings of the 1st SIAM Symposium on Simplicity in Algorithms (SOSA), volume 61 ofOASICS, pages 3For the reader’s convenience, two remarks on [17] are in order. It [17, Theorem 4] mistakenly referred to [15] for the proof of (1). In [17, Paragraph 3], the complement of a n...

    work page doi:10.4230/oasics 2018

  5. [5]

    Kanj, and Ge Xia

    Jianer Chen, Iyad A. Kanj, and Ge Xia. On parameterized exponential time complexity. Theoretical Computer Science, 410:2641–2648, 2009.doi:10.1016/j.tcs.2009.03.006

    work page doi:10.1016/j.tcs.2009.03.006 2009

  6. [6]

    Duncan, David Eppstein, and Stephen G

    Christian A. Duncan, David Eppstein, and Stephen G. Kobourov. The geometric thickness of low degree graphs. InProceedings of the 20th ACM Symposium on Computational Geometry, 2004, pages 340–346. ACM, 2004.doi:10.1145/997817.997868

    work page doi:10.1145/997817.997868 2004

  7. [7]

    Furst, Jonathan L

    Merrick L. Furst, Jonathan L. Gross, and Lyle A. McGeoch. Finding a maximum-genus graph imbedding.Journal of the ACM, 35(3):523–534, 1988.doi:10.1145/44483.44485

    work page doi:10.1145/44483.44485 1988

  8. [8]

    Michael Garey and David S. Johnson. The rectilinear steiner tree problem is NP-complete. SIAM Journal on Applied Mathematics, 32(4):826–834, 1977.doi:10.1137/0132071

    work page doi:10.1137/0132071 1977

  9. [9]

    Garey and David S

    Michael R. Garey and David S. Johnson.Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco, 1979

    work page 1979

  10. [10]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller and James W. Thatcher, editors,Complexity of Computer Computations, The IBM Research Sym- posia Series, pages 85–103. Plenum Press, New York, 1972

    work page 1972

  11. [11]

    On two minimax theorems in graph.Journal of Combinatorial Theory, Series B, 21(2):96–103, 1976.doi:10.1016/0095-8956(76)90049-6

    L´ aszl´ o Lov´ asz. On two minimax theorems in graph.Journal of Combinatorial Theory, Series B, 21(2):96–103, 1976.doi:10.1016/0095-8956(76)90049-6

    work page doi:10.1016/0095-8956(76)90049-6 1976

  12. [12]

    Lucchesi.A Minimax Equality for Directed Graphs

    Cl´ audio L. Lucchesi.A Minimax Equality for Directed Graphs. PhD thesis, University of Waterloo, Waterloo, Ontario, 1976

    work page 1976

  13. [13]

    Lucchesi and Daniel H

    Cl´ audio L. Lucchesi and Daniel H. Younger. A minimax theorem for directed graphs.Journal of the London Mathematical Society, s2-17(3):369–374, 1978.doi:10.1112/jlms/s2-17.3.369

    work page doi:10.1112/jlms/s2-17.3.369 1978

  14. [14]

    Minimum weakly fundamental cycle bases are hard to find.Algorithmica, 53(3):402–424, 2009.doi:10.1007/s00453-007-9112-8

    Romeo Rizzi. Minimum weakly fundamental cycle bases are hard to find.Algorithmica, 53(3):402–424, 2009.doi:10.1007/s00453-007-9112-8

    work page doi:10.1007/s00453-007-9112-8 2009

  15. [15]

    PhD thesis, Universit¨ at Paderborn, Paderborn, West Germany, 1983

    Ewald Speckenmeyer.Untersuchungen zum Feedback Vertex Set Problem in ungerichteten Graphen. PhD thesis, Universit¨ at Paderborn, Paderborn, West Germany, 1983

    work page 1983

  16. [16]

    Bounds on feedback vertex sets of undirected cubic graphs

    Ewald Speckenmeyer. Bounds on feedback vertex sets of undirected cubic graphs. InAlgebra, combinatorics and logic in computer science, volume 42 ofColloquia Mathematica Societatis J´ anos Bolyai, pages 719–729. North-Holland, 1986

    work page 1986

  17. [17]

    On feedback vertex sets and nonseparating independent sets in cubic graphs.Journal of Graph Theory, 12(3):405–412, 1988.doi:10.1002/jgt.3190120311

    Ewald Speckenmeyer. On feedback vertex sets and nonseparating independent sets in cubic graphs.Journal of Graph Theory, 12(3):405–412, 1988.doi:10.1002/jgt.3190120311

    work page doi:10.1002/jgt.3190120311 1988

  18. [18]

    Shuichi Ueno, Yoji Kajitani, and Shin’ya Gotoh. On the nonseparating independent set prob- lem and feedback set problem for graphs with no vertex degree exceeding three.Discrete Mathematics, 72(1-3):355–360, 1988.doi:10.1016/0012-365X(88)90226-9

    work page doi:10.1016/0012-365x(88)90226-9 1988

  19. [19]

    Younger.Feedback in a Directed Graph

    Daniel H. Younger.Feedback in a Directed Graph. PhD thesis, Columbia University, New York City, New York, 1963. 13

    work page 1963