3 The bipartition may not be unique.

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 the 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?

2 copy edit

# Combining DAGs into an AcyclicTournamentacyclictournament

Hi all,

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 the bipartition $\alpha \cup \beta$, given that one exists, other that enumerating all possible bipartitions and checking if the resulting $G'$ is acyclic?

1

# Combining DAGs into an Acyclic Tournament

Hi all,

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 the bipartition $\alpha \cup \beta$, given that one exists, other that enumerating all possible bipartitions and checking if the resulting $G'$ is acyclic?