Hanauer's feedback arc set conjecture for degree-five oriented multigraphs

Let DD be an oriented multigraph, and write Δ\Delta for its maximum degree. A feedback arc set is a set of arcs whose deletion makes DD acyclic; let fas(D){\rm fas}(D) denote its minimum size. Let nn be the number of vertices.

Hanauer's conjecture. If Δ5\Delta\leq 5, then

fas(D)2.5n3.{\rm fas}(D)\leq \frac{2.5n}{3}.

Hanauer posed this as a bounded-degree upper bound for the minimum feedback arc set. The conjecture is solved by the paper's main theorem, which establishes the stronger estimate fas(D)m/3{\rm fas}(D)\leq m/3; since Δ5\Delta\leq 5 implies m2.5nm\leq 2.5n, the conjectured bound follows.

Sources & referencesView supporting material

Primary source

Gregory Gutin, Hui Lei, Anders Yeo and Yacong Zhou, “Upper bounds on minimum size of feedback arc set of directed multigraphs with bounded degree”, arXiv:2409.07680 (2024).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.