A feedback arc set is a set of edges which, when removed from the graph, leaves an acyclic graph. So it is a set containing at least one edge of every cycle in the graph. Let FAS denote the problem of finding the minimum feedback arc set. A tournament graph is a oriented complete graph. An eulerian graph is a graph that each vertice has the same number of in-edges and out-edges, or equivalently there exists a path that starts and ends in a same vertice and walks every edge in the graph exactly once. An eulerian tournament is defined on an odd number of vertices and is called a regular tournament.
I have learned that FAS on tournaments is NP-hard and FAS on general eulerian graphs is also NP-hard. The proof for tournaments can be found in this paper. However, to the best of my knowledge, the two reductions do not work for eulerian tournaments or so-called regular tournaments. I wonder if FAS on eulerian tournaments is still NP-hard or it is in fact in P.
Best Answer
The feedback arc set problem is still NP-hard for regular tournaments. We can prove this by combining the reductions to Eulerian digraphs and to tournaments, with only a few modifications.
Start with any simple digraph, and begin by reducing it to an Eulerian digraph $D$, as in the paper by Perrot and Pham. If necessary, add a vertex so that $D$ has an odd number of vertices. Then, let $D'$ be an Eulerian orientation of the graph complement of $D$.
Theorem 1 in the tournament reduction by Charbit, Thomassé, and Yeo gives us a bipartite tournament $G_k$ with $k = 2^z$ vertices in each part, and $\operatorname{mfas}(G_k) \ge \frac{k^2}{2} - 2 k^{5/3}$. We modify this construction slightly: in the matrix of Lemma 1, delete the row and column indexed by the empty set. This gives us a bipartite tournament I'll call $G'_{k-1}$ with $k-1$ vertices in each part, still nearly the same feedback arc set bound, and nearly regular. On one side, each vertex has out-degree $\frac k2$ and in-degree $\frac k2-1$; on the other side, each vertex has out-degree $\frac k2-1$ and in-degree $\frac k2$.
Also, pick your favorite regular tournament $T_{k-1}$ on $k-1$ vertices.
We proceed as in the tournament reduction, except that we blow up each vertex of $D$ to only $k-1$ vertices, and connect those by a copy of $T_{k-1}$. For every edge of $D$, we add a transitive bipartite tournament in the blow-up, oriented as in $D$. For every non-edge, we add a copy of $G'_{k-1}$, oriented as in $D'$. The result is regular.
The proof that this reduction is the same, except that we add $n \cdot \operatorname{mfas}(T_{k-1})$ both to the lower bound (because each copy of $T_{k-1}$ has at least $\operatorname{mfas}(T_{k-1})$ backward arcs in any permutation) and to the upper bound (because we make sure that we order the vertices in each copy of $T_{k-1}$ to achieve exactly $\operatorname{mfas}(T_{k-1})$ backward arcs).
So we've constructed (still in polynomial time) a regular tournament $T$ such that computing $\operatorname{mfas}(T)$ tells us $\operatorname{mfas}(D)$.