Transitive feedback arc set (TFAS): NP-complete? Some time ago, I posted a reference request for graph problems where we want to find a 2-partition of the edges where both sets fulfill a property not related to their cardinality. I was trying to prove that the following problem is NP-hard:


  Given a tournament $G = (V,E)$, is there a feedback arc set $F \subseteq E$ in $G$ that defines a transitive relation?


I do have a construction for an attempt at a proof, but it seems that that is going to run into a dead end, so I thought I might ask here to see whether I'm missing something obvious. In order to not confine your creativity to lines of thought similar to the ones I used, I won't post my attempt here.

Is this problem NP-hard? If so, how to prove it?
To add a little context, here's a construction for a graph that doesn't have a transitive feedback arc set. For this construction, I'll use the following gadget graph:



This tournament has the following properties (which I checked using a program, I didn't prove it formally):


if (2,7) is not in a given TFAS, then (1,3) is
if (5,1) is in a given TFAS, then so is (3,6)
if (7,3) is in a given TFAS, then (5,1) is not


or slightly abusing predicate logic notation:


$\neg (2,7) \rightarrow (1,3)$
$(5,1) \rightarrow (3,6)$
$(7,3) \rightarrow \neg (5,1)$


You'll notice that for each implication, the two edges are pairwise disjoint, so the following construction works:



I hope you can make out the idea of the graph: using the implication properties of the tournament above, we can construct a graph in which each transitive feedback arc set both includes and doesn't include the edge $A$, i.e. a contradiction, which means the graph doesn't have a transitive feedback arc set. Any completion of that graph cannot have one either since the same contradiction will remain in any completion. I left out a large number of vertices, all of which can be derived from substituting the tournament above for the implications.