Feedback vertex sets of digraphs with bounded maximum degree
Jiangdong Ai Gregory Gutin Xiangzhou Liu Anders Yeo Yacong Zhou · 2025
Read Feedback vertex sets of digraphs with bounded maximum degree by Jiangdong Ai Gregory Gutin Xiangzhou Liu Anders Yeo Yacong Zhou (2025) 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-2512-01676.txt.
Introduction
Jiangdong Ai and co-authors study feedback vertex sets in directed graphs with bounded degree. A feedback set hits every directed cycle. Removing it leaves the graph acyclic. In oriented graphs, with no opposite arc pairs, the task has set traits.
Degree here sums in-arcs and out-arcs at each vertex. Bounded degree caps how linked each node can be. The team proves bounds for feedback sets under that cap. Such sets help break deadlocks in networks and find orderings in dependency graphs. Bounded degree mirrors real networks, where each router or person links to few peers, so the bounds stay tight for practical cases.
Catalog record
| CREATOR | Jiangdong Ai Gregory Gutin Xiangzhou Liu Anders Yeo Yacong Zhou |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 60 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-01676
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Feedback vertex sets of digraphs with bounded maximum degree Jiangdong Ai Gregory Gutin Xiangzhou Liu Anders Yeo Yacong Zhou Abstract A digraph D D is an oriented graph if D D does not have a pair of opposite arcs. The degree of a vertex v v of D D is the sum of the in-degree and out-degree of v . v. Let fvs ( D ) {\rm fvs}(D) be the minimum number of vertices whose deletion from D D makes it acyclic. Let D D be a digraph with n n vertices and maximum degree Δ \Delta . We prove the following bounds. If D D is an oriented graph, then fvs ( D ) ≤ 3 n 7 {\rm fvs}(D)\leq\frac{3n}{7} when Δ ≤ 4 \Delta\leq 4 and fvs ( D ) ≤ n 2 {\rm fvs}(D)\leq\frac{n}{2} when Δ ≤ 5 \Delta\leq 5 . If D D is a connected digraph, Δ ≤ 4 \Delta\leq 4 and D D is not obtained from an odd undirected cycle by replacing every edge with the pair of opposite arcs with the same endvertices, then fvs ( D ) ≤ n 2 {\rm fvs}(D)\leq\frac{n}{2} . If D D is an arbitrary digraph with Δ ≤ 5 \Delta\leq 5 then fvs ( D ) ≤ 2 n 3 . {\rm fvs}(D)\leq\frac{2n}{3}. Note that all the above bounds are tight. 1 Introduction In this paper, the standard terminology and notation in digraph theory are used, following [ 3 ] . Some important terminology and notation are given at the end of this section. A set F\subseteq V(D) of a digraph D , is a feedback vertex set if D-F is acyclic. Similarly, one defines a feedback arc set . Deciding whether a graph has a feedback vertex set of a given size is among the 21 original NP-complete problems of Karp [ 17 ] . Cavallaro and Fluschnik [ 7 ] proved that the problem remains NP-hard even on subclasses of Hamiltonian graphs. Thus, finding the minimum size of a feedback vertex set of a digraph D , denoted by {\rm fvs}(D) is a challenging algorithmic problem and was extensively studied in the literature. In particular, some scholars studied the upper bounds on {\rm fvs}(D) for arbitrary digraphs D . Akbari, Ghodrati, Jabalameli and Saghafian [ 1 ] obtained a lower bound on |V(D)|-{\rm fvs}(D) inspired by the well-known Caro-Wei lower bound for the maximum size of an independent set in an undirected graph. This bound was improved in two different ways by Asgarli, Falkenhagen and Hoshi [ 2 ] . To obtain tight or close-to-tight lower bounds on {\rm fvs}(D) , many researchers studied such bounds for special classes of oriented graphs (or, orgraphs ), i.e., digraphs without opposite arcs. We will first discuss new results obtained in this paper and then we will overview numerous results obtained by other researchers. Several scholars carried out research on tight upper bounds for the minimum size of a feedback arc set in orgraphs with small maximum degree, see, e.g. [ 4 , 5 , 8 , 14 , 13 , 12 ] . In particular, the authors of [ 12 ] obtained tight upper bounds when the maximum degree \Delta\leq 4 and when \Delta\leq 5. The authors of [ 12 ] proved a conjecture in [ 14 ] and disproved another one in [ 14 ] , both for \Delta\leq 5. In this paper, similarly, we study tight upper bounds for the minimum size of a feedback vertex set in orgraphs with small bounded maximum degree \Delta . Clearly, the case of \Delta\leq 2 is trivial. In the case of \Delta\leq 3 , the tight bound {\rm fvs}(D)\leq\frac{n}{3} for oriented graphs was proved in [ 14 ] , and for digraphs the bound {\rm fvs}(D)\leq\frac{n}{2} follows by induction: delete both vertices of a 2-cycle and use the induction hypothesis, but use only one vertex of the 2-cycle in feedback vertex set (due to possible existence of 2-cycles the bound is tight). We establish new tight upper bounds on the minimum feedback vertex set size in directed and oriented graphs with \Delta\leq 4 and \Delta\leq 5 . Specifically, we prove for \Delta\leq 4 that any orgraph D on n vertices satisfies {\rm fvs}(D)\leq\frac{3n}{7} , and if D is a connected digraph not obtained from an odd undirected cycle by replacing every edge with the pair of opposite arcs with the same endvertices, then {\rm fvs}(D)\leq\frac{n}{2} . For \Delta\leq 5 , we show {\rm fvs}(D)\leq\frac{n}{2} for an orgraph D , and {\rm fvs}(D)\leq\frac{2n}{3} for a digraph D . Moreover, we provide explicit constructions that demonstrate that all of these bounds are tight. Tournaments form a well-known class of orgraphs. Already Stearns [ 27 ] and Erdős and Moser [ 9 ] have shown that for any tournament T on n vertices, we have {\rm fvs}(T)\leq n-\lfloor\log_{2}n\rfloor-1 , while there are tournaments where there is no feedback vertex set with less than n-2\lfloor\log_{2}n\rfloor-1 vertices. More precise bounds for small values of n have been obtained by Sanchez-Flores [ 25 , 26 ] and recently more work has been done in that direction by Neiman, Mackey and Heule [ 23 ] and by Lidický and Pfender [ 21 ] . Improving the asymptotic upper and lower bounds remains an open problem. Another class that has received a lot of attention is planar orgraphs. Let D_{g}^{n} denote a planar digraph with n vertices and directed girth g . Harutyunyan [ 16 , 15 ] conjectured that {\rm fvs}(D_{3}^{n})\leq\frac{2n}{5} . This conjecture was refuted by Knauer, Valicov and Wenger [ 18 ] , who showed that {\rm fvs}(D_{g}^{n})\geq\frac{n-1}{g-1} for all g\geq 3 . On the other hand, Golowich and Rolnick [ 11 ] established the upper bounds {\rm fvs}(D_{4}^{n})\leq\frac{7n}{12} , {\rm fvs}(D_{5}^{n})\leq\frac{8n}{15} , and {\rm fvs}(D_{g}^{n})\leq\frac{3n-6}{g} for all g\geq 6 . Harutyunyan and Mohar [ 15 ] proved that the vertex set of every planar orgraph of girth at least 5 can be partitioned into two acyclic subgraphs. This result was extended to planar orgraphs of girth 4 by Li and Mohar [ 20 ] , and therefore {\rm fvs}(D_{4}^{n})\leq\frac{n}{2} . Further improvements were obtained by Esperet, Lemoine, and Maffray [ 10 ] , who showed {\rm fvs}(D_{4}^{n})\leq\tfrac{5n-5}{9} , {\rm fvs}(D_{5}^{n})\leq\tfrac{2n-5}{4} , and {\rm fvs}(D_{g}^{n})\leq\tfrac{2n-6}{g} if g\geq 6 . These improved results of Golowich and Rolnick. However, a question of Albertson [ 28 , 22 ] asking whether any planar orgraph has a feedback vertex set on at most half its vertices, remains open. Note that this question is a weakening of the undirected setting as well as of the famous Neumann-Lara conjecture [ 24 ] . Further, it is known that if true this bound is best-possible [ 18 ] . Moreover, note that the best known upper bound coincides with the above mentioned \frac{3}{5}n from the undirected setting [ 6 ] . Knauer, La and Valicov [ 19 ] studied the minimum size of a feedback vertex set in oriented and undirected n -vertex graphs of given degeneracy or treewidth (for orgraphs, both parameters are undirected, i.e. they are of the underlying graphs of orgraphs). Since in this paper we only study digraphs,