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

About 2 years old · traced to

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 m≤2.5nm\leq 2.5n, the conjectured bound follows.

References

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.