# Is finding the minimum feedback arc set problem on eulerian tournaments in P or NP-hard?

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.

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)$$.