Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree
<|reference_start|>Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree: An oriented multigraph is a directed multigraph without directed 2-cycles. Let ${\rm fas}(D)$ denote the minimum size of a feedback arc set in an oriented multigraph $D$. The degree of a vertex is the sum of its out- and in-degrees. In several papers, upper bounds for ${\rm fas}(D)$ were obtained for oriented multigraphs $D$ with maximum degree upper-bounded by a constant. Hanauer (2017) conjectured that ${\rm fas}(D)\le 2.5n/3$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5. We prove a strengthening of the conjecture: ${\rm fas}(D)\le m/3$ holds for every oriented multigraph $D$ with $m$ arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor (1990,1997). It would be interesting to determine $c$ such that ${\rm fas}(D)\le cn$ for every oriented multigraph $D$ with $n$ vertices and maximum degree at most 5 such that the bound is tight. We show that $\frac{5}{7}\le c \le \frac{24}{29} < \frac{2.5}{3}$.<|reference_end|>
@article{gutin2024upper,
    title={Upper bounds on minimum size of feedback arc set of directed multigraphs
  with bounded degree},
    author={Gregory Gutin, Hui Lei, Anders Yeo, Yacong Zhou},
    journal={arXiv preprint arXiv:2409.07680},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07680},
    primaryClass={math.CO cs.DM}
}