Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908723109167104 |
|---|---|
| author | Gutin, Gregory Nielsen, Mads Anker Yeo, Anders Zhou, Yacong |
| author_facet | Gutin, Gregory Nielsen, Mads Anker Yeo, Anders Zhou, Yacong |
| contents | Let $D=(V(D),A(D))$ be a digraph with at least one directed cycle. A set $F$ of arcs is a feedback arc set (FAS) if $D-F$ has no directed cycle. The FAS decomposition number ${\rm fasd}(D)$ of $D$ is the maximum number of pairwise disjoint FASs whose union is $A(D)$. The directed girth $g(D)$ of $D$ is the minimum length of a directed cycle of $D$. Note that ${\rm fasd}(D)\le g(D).$ The FAS decomposition number appears in the well-known and far-from-solved conjecture of Woodall (1978) stating that for every planar digraph $D$ with at least one directed cycle, ${\rm fasd}(D)=g(D).$ The degree of a vertex of $D$ is the sum of its in-degree and out-degree.
Let $D$ be an arc-weighted digraph and let ${\rm fas}_w(D)$ denote the minimum weight of its FAS. In this paper, we study bounds on ${\rm fasd}(D)$, ${\rm fas}_w(D)$ and ${\rm fas}(D)$ for arc-weighted oriented graphs $D$ (i.e., digraphs without opposite arcs) with upper-bounded maximum degree $Δ(D)$ and lower-bounded $g(D)$. Note that these parameters are related: ${\rm fas}_w(D)\le w(D)/{\rm fasd}(D)$, where $w(D)$ is the total weight of $D$, and ${\rm fas}(D)\le |A(D)|/{\rm fasd}(D).$ In particular, we prove the following: (i) If $Δ(D)\leq~4$ and $g(D)\geq 3$, then ${\rm fasd}(D) \geq 3$ and therefore ${\rm fas}_w(D)\leq \frac{w(D)}{3}$ which generalizes a known tight bound for an unweighted oriented graph with maximum degree at most 4; (ii) If $Δ(D)\leq 3$ and $g(D)\in \{3,4,5\}$, then ${\rm fasd}(D)=g(D)$; (iii) If $Δ(D)\leq 3$ and $g(D)\ge 8$ then ${\rm fasd}(D)<g(D).$ We also give some bounds for the cases when $Δ$ or $g$ are large and state several open problems and a conjecture. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_06935 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs Gutin, Gregory Nielsen, Mads Anker Yeo, Anders Zhou, Yacong Combinatorics Discrete Mathematics Let $D=(V(D),A(D))$ be a digraph with at least one directed cycle. A set $F$ of arcs is a feedback arc set (FAS) if $D-F$ has no directed cycle. The FAS decomposition number ${\rm fasd}(D)$ of $D$ is the maximum number of pairwise disjoint FASs whose union is $A(D)$. The directed girth $g(D)$ of $D$ is the minimum length of a directed cycle of $D$. Note that ${\rm fasd}(D)\le g(D).$ The FAS decomposition number appears in the well-known and far-from-solved conjecture of Woodall (1978) stating that for every planar digraph $D$ with at least one directed cycle, ${\rm fasd}(D)=g(D).$ The degree of a vertex of $D$ is the sum of its in-degree and out-degree. Let $D$ be an arc-weighted digraph and let ${\rm fas}_w(D)$ denote the minimum weight of its FAS. In this paper, we study bounds on ${\rm fasd}(D)$, ${\rm fas}_w(D)$ and ${\rm fas}(D)$ for arc-weighted oriented graphs $D$ (i.e., digraphs without opposite arcs) with upper-bounded maximum degree $Δ(D)$ and lower-bounded $g(D)$. Note that these parameters are related: ${\rm fas}_w(D)\le w(D)/{\rm fasd}(D)$, where $w(D)$ is the total weight of $D$, and ${\rm fas}(D)\le |A(D)|/{\rm fasd}(D).$ In particular, we prove the following: (i) If $Δ(D)\leq~4$ and $g(D)\geq 3$, then ${\rm fasd}(D) \geq 3$ and therefore ${\rm fas}_w(D)\leq \frac{w(D)}{3}$ which generalizes a known tight bound for an unweighted oriented graph with maximum degree at most 4; (ii) If $Δ(D)\leq 3$ and $g(D)\in \{3,4,5\}$, then ${\rm fasd}(D)=g(D)$; (iii) If $Δ(D)\leq 3$ and $g(D)\ge 8$ then ${\rm fasd}(D)<g(D).$ We also give some bounds for the cases when $Δ$ or $g$ are large and state several open problems and a conjecture. |
| title | Feedback Arc Sets and Feedback Arc Set Decompositions in Weighted and Unweighted Oriented Graphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2501.06935 |