I have a vertex set $V$ and a collection of disjoint arc sets $E\_1, \ldots, E\_t$ such that $$G\_i = (V, E\_i),\quad\forall i = 1, \ldots t,$$ are directed acyclic graphs (DAGs) and $$G = (V, E\_1 \cup \ldots \cup E\_t)$$ is a tournament. We note that the individual DAGs may be disconnected and that $G$ may not be acyclic. However, suppose there exists a bipartition of the arc set indices $\alpha \cup \beta$ such that $$G' = (V, E\_\alpha\cup E\_\beta^T)$$ is an **acyclic** tournament where $$E\_\alpha = E\_{\alpha\_1} \cup \ldots \cup E\_{\alpha\_p}$$ and $$E\_\beta = E\_{\beta\_1} \cup \ldots \cup E\_{\beta\_q}$$ and $E^T$ is the transpose of $E$ (all the arcs are reversed).


Does anybody know of any results relating to the above? In particular, does anybody know of a method of determining a bipartition $\alpha \cup \beta$, given that at least one exists, other that enumerating all possible bipartitions and checking if the resulting $G'$ is acyclic?



Combining DAGs into an acyclic tournament
The problem you pose, of finding a bipartition if one exists, is of polynomially equivalent difficulty to the decision problem of determining whether a bipartition exists. The decision problem in turn is NP-complete, by reduction from 3-SAT (and the fact that a solution is easily checked.)


Given an instance of 3-SAT with $n$ clauses, we construct a family of DAGs on $4n$ vertices. All edges in the complement of $n$ disjoint $4$-cycles will be singleton DAGs. One "universal" DAG consists of a single edge in each $4$-cycle, and establishes a potential (forbidden) orientation on each $4$-cycle. Then for every variable in the 3-SAT instance we define a DAG consisting of an edge in each of the $4$-cycles corresponding to the clauses in which that variable appears, with the direction depending on whether the variable appears negated in the clause, in such a way that the forbidden orientation imposed by the universal DAG is achieved in a given $4$-cycle if and only if no literal in the corresponding clause is true, where a variable is considered true when its DAG lies on the same side of the bipartition as the universal DAG and is considered false otherwise. Then an acyclic bipartition of the DAGs exists if and only if the instance of 3-SAT has a satisfying assignment. 


