Acyclic partition of edges in tournaments

Question

The following question is related to a research problem I am working on. I am curious if anyone is aware of a solution, if there are similar problems which may aid me in finding a solution, or if the question is most likely difficult to answer.

---

Let $T$ be a tournament. It is well known that the arcs of a tournament (and any directed graph in fact) can have their arcs partitioned into two disjoint sets where the arc-induced subgraphs formed by these two sets is acyclic. The algorithm for this comes from an approximation algorithm for the feedback arc set problem:

1. Arbitrarily order the vertices of the tournament.
2. Place all arcs oriented the same way in one set and place the remaining arcs in the other set (from this, we can form two arc-induced subgraphs).

If $T$ has $n$ vertices, then it is clear that the number of ways to create a partition is lower bounded by $n!$. Say that we can flip the orientations of any subset of the arcs of $T$. Let $T'$ be the tournament after the flips. Before we perform these flips, we follow the algorithm above to obtain two arc-induced subgraphs, and we flip the orientation of the arcs in both subgraphs the same way as they are in $T'$. My question is the following: does there exist a partition of the arcs where at least one of the arc-induced subgraphs is still acyclic for any subset of the arcs we decide to flip?

An easier version of the problem that I am also interested in is stated here (implied by the above problem): let $T = (V, A)$ be a tournament. Let $A'$ be the same as $A$ but where some subset of the arcs have had their orientation flipped. A partition of $A$ splits it into two disjoint sets $A_1$ and $A_2$ (i.e., $A = A_1 \sqcup A_2$). Flip the arcs in $A_1$ and $A_2$ as they are in $A'$ to get disjoint sets $A_1'$ and $A_2'$. We let $T[S]$ denote the arc-induced subgraph from the set $S \subseteq A$. Given $A$ and $A'$, does there exist a partition of the arcs $A = A_1 \sqcup A_2$ such that $T[A_1]$ is acyclic and $T[A_2']$ is acyclic?

Both statements are true when either all or none of the arcs are flipped because we can use the given algorithm. If only one arc or all but one arc is flipped, then it is also true because one of the arc-induced subgraphs is still guaranteed to be acyclic. This suggests that when around half the arcs are flipped, you're more likely to have a cycle in both arc-induced subgraph.

Through some computer simulations, it appears that there are always a few partition of the arcs that have this property that I am interested in, but I suspect for larger graphs, it's more likely that a cycle will be contained in both arc-induced subgraphs. However, given how quickly the problem grows in size, it is not possible to check these extremely large graphs.

Answer 1

Edited again --- now I realized what second question was, and luckily enough the construction works in order to answer it in the negative.

Set $V=\mathbb Z/15\mathbb Z$; let the arcs be of the form $i\to i-1,i+2,i+3,i-4,i+5,i+6,i+7$. Let the arcs to be flipped be those of the form $i\to i-1,i-4,i+6, i+7$. I claim that this is a counterexample even to the second question.

Assume that there exists a partition $A=A_1\sqcup A_2$ such that $T[A_1]$ and $T[A_2']$ are both acyclic (sorry for changing the indices). There should be a vertex having zero out-degree in $A_1$, so that all its out-edges are in $A_2$; by symmetry, we may assume that this vertex is $0$, so that $0\to -1,2,3,-4,5,6,7$ are in $A_2$, so the edges $-1,-4,6,7\to 0\to 2,3,5$ are in $A_2'$.

Now: the edge $3\to 6$ is in $A_1$, because of the cycle $0\to 3\to 6\to 0$ occurring otherwise in $T[A_2']$. Similarly, $A_1$ contains $6\to 5$ (because of $0\to 5\to 6\to 0$), $5\to 7$ (because of $0\to 5\to 7\to 0$) and $7\to 3$ (because of $0\to 3\to 7\to 0$).

But then $A_1$ contains the cycle $3\to 6\to 5\to 7\to 3$.