Algorithms for rooted directed acyclic graph isomorphism

Question

Given two directed acyclic graphs $G_1$ and $G_2$, and their roots $r_1$ and $r_2$, is there a polynomial algorithm to determine if $G_1$ and $G_2$ are isomorphic?

Answer 1

For arbitrary graphs, no there is no known polytime algorithm, proving that DAGI (Directed Acyclic Graph Isomorphism) is GI-complete is rather straightforward.

First, let us consider that GI isomorphism restricted to non-trivial connected undirected graph is GI-complete Then, given $G = (V, E)$ a non-trivial connected undirected graph, we can convert it in polytime into a DAG $D = (V\uplus E, F)$ and $F = \{(\{u, v\}, v)\mid\{u, v\}\in E\}$.

If one explicitly needs a rooted DAG, then, $D_{\texttt{rooted}} = (V\uplus E\uplus\{r\}, F_{\texttt{rooted}}, r)$ where $r$ is a fresh vertex, and $F_{\texttt{rooted}} = F \uplus \{(r, \{u, v\}) \mid\{u, v\}\in E\}$

(Note that $D$ has the edges of $G$ points toward its vertices, the other construction is perfectly legit as well)

Note that the hard part of the proof is then to prove that there exists an isomorphism in $D$ iff there exists an isomorphism in $G$. Note that if $G$ is simple, then $D$ is simple. Then, assuming $\sigma$ an isomorphism between $G_1$ and $G_2$, one can easily prove that there exist an isomorphism $\sigma'$ between $D_1$ and $D_2$. Conversely, assuming an isomorphism $\sigma'$ between $D_1$ and $D_2$, one can easily prove that there exist an isomorphism between $G_1$ and $G_2$ by (i) proving that nodes and edges in $G_1$ are respectively mapped to nodes and edges in $G_2$ through $\sigma'$. Then define $\sigma$ as $\sigma'$ while simply ignoring edges.

Hence, given an instance of GI (that is, a pair of graphs $G_1$ and $G_2$ to be tested for isomorphism) we can reduce it an instance of DAGI.