Upper Bounds on the Minimum Size of Feedback Arc Set of Directed Multigraphs With Bounded Degree

An oriented multigraph is a directed multigraph without directed 2-cycles. Let (Formula presented.) denote the minimum size of a feedback arc set in an oriented multigraph (Formula presented.). In several papers, upper bounds for (Formula presented.) were obtained for oriented multigraphs (Formula presented.) with maximum degree upper-bounded by a constant. Hanauer conjectured that (Formula presented.) for every oriented multigraph (Formula presented.) with (Formula presented.) vertices and maximum degree at most 5. We prove a strengthening of the conjecture: (Formula presented.) holds for every oriented multigraph (Formula presented.) with (Formula presented.) arcs and maximum degree at most 5. This bound is tight and improves a bound of Berger and Shor. It would be interesting to determine (Formula presented.) such that (Formula presented.) for every oriented multigraph (Formula presented.) with (Formula presented.) vertices and maximum degree at most 5 such that the bound is tight. We show that (Formula presented.).