<p>If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph <span class="math-container">$D$</span> make a new one <span class="math-container">$D’$</span> as follows: Make a vertex in <span class="math-container">$D’$</span> for every vertex of <span class="math-container">$D$</span> and every arc of <span class="math-container">$D$</span>. For every arc <span class="math-container">$u \rightarrow v$</span> of <span class="math-container">$D$</span>, add the arcs: <span class="math-container">$uv \rightarrow u$</span> and <span class="math-container">$uv \rightarrow v$</span> in <span class="math-container">$D’$</span> (in this order). Clearly <span class="math-container">$D’$</span> is an (ordered) DAG and two digraphs <span class="math-container">$D_1$</span> and <span class="math-container">$D_2$</span> are isomorphic iff their corresponding ordered dags <span class="math-container">$D_1’$</span> and <span class="math-container">$D_2’$</span> are (ordered) isomorphic.</p>
<p>If you need to order both outgoing and incoming edges there is a simple polynomial time algorithm: if <span class="math-container">$D_1$</span> and <span class="math-container">$D_2$</span> are connected then fixing <span class="math-container">$f(u) = v$</span> (for <span class="math-container">$u \in V(D_1)$</span> and <span class="math-container">$v \in V(D_2)$</span>) uniquely determines <span class="math-container">$f$</span>.</p>

CC BY-SA 4.0
2020-09-12T22:34:22.940Z
Indeed only the outgoing edges need to be ordered. That's unfortunate! I'll think about your GI-completeness proof some more, but it seems convincing at first glance. I need this for solving a more applied problem and will probably write a paper about that; how do you want me to credit you when I mention that this is GI-complete?
Manuel Eberl
CC BY-SA 4.0
2020-09-12T22:44:08.067Z
Maybe an acknowledgement or a citation of this answer, as discussed here https://academia.stackexchange.com/questions/84965/how-to-cite-an-answer-in-stackexchange
daniello
CC BY-SA 4.0
2020-09-12T22:51:59.103Z
I feel this is likely to be already known in the literature, perhaps you will be able to find a citation... if not then proceed as above.
daniello
CC BY-SA 4.0
2020-09-12T23:09:07.780Z
I googled for ages before asking this question and found nothing. The main problem might be that I think ‘ordered graph’/‘ordered DAG’ usually means something different. I'm not sure what the commonly accepted term for ‘my’ ordered DAG is (if there is any).
Manuel Eberl
CC BY-SA 4.0
2020-09-12T22:27:13.827Z
2020-09-12T22:39:20.467Z
2020-09-12T22:39:20.467Z
daniello
<p>I am wondering what is known about the isomorphism problem on <em>ordered</em> DAGs, in particular how to find a canonical representative modulo isomorphism.</p>
<p>By <em>ordered</em> I mean that each vertex has a list of outgoing edges in fixed order and that order must be respected by the isomorphism. I don't know if there is a widely used name for such structures.</p>
<p>An equivalent problem is probably isomorphism of acyclic deterministic semiautomata (the ordering of the edges can be recovered by just fixing an order on the alphabet and listing the transitions for a state in that order).</p>
<p>If the DAG is restricted to have only one root, it is trivial (just order by left-to-right DFS). Or, for the automaton, if the automaton has a designated initial state and all other states must be reachable. But if that's not the case, I'm at a loss.</p>
<p>I don't see any obvious polynomial reductions from GI-complete problems that I am familiar with. My intuition tells me this looks like it should be in P.</p>
<p>The best algorithm I came up with so far tries to successively label the nodes with numbers from 1 to n in a canonical way by picking the ‘smallest’ root w.r.t. some suitable partial ordering (e.g. based on the number of children and the ordering numbers that have already been assigned), but when there are still several minimal roots, I don't see how to get around trying all permutations of them.</p>
<p>There is a paper on <a href="https://link.springer.com/article/10.1007/BF02684448" rel="noreferrer">isomorphism of ‘ordered graphs’</a> that seems to be similar to my problem except that their graphs are undirected and their ‘ordering’ is not a list, but a cyclic list. My intuition would tell me that my problem can be reduced to this (e.g. by adding some conspicuous ‘list beginning marker’ to recover the list from the cyclic list) but I am not quite sure. I am also not sure if there is not something more direct than their approach for my case.</p>
<p>EDIT: I thought about it a bit more and I think their approach doesn't work for my case at all. In my setting, there is an ordering on the outgoing edges of each node, but not on the ingoing ones. That makes a huge difference.</p>
<p>For illustration, here are two instances of the problem: <a href="https://i.sstatic.net/weo1y.png" rel="noreferrer"><img src="https://i.sstatic.net/weo1y.png" alt="two instances of the ordered DAG isomorphism problem, one isomorphic and one non-isomorphic" /></a></p>

<cc.complexity-theory><graph-algorithms><automata-theory><graph-isomorphism><directed-acyclic-graph>
Isomorphism of ‘ordered’ DAGs / acyclic semiautomata
Manuel Eberl
# Isomorphism of ‘ordered’ DAGs / acyclic semiautomata

(Asked by: username_0 on 2020-09-12)

I am wondering what is known about the isomorphism problem on *ordered* DAGs, in particular how to find a canonical representative modulo isomorphism.

By *ordered* I mean that each vertex has a list of outgoing edges in fixed order and that order must be respected by the isomorphism. I don't know if there is a widely used name for such structures.

An equivalent problem is probably isomorphism of acyclic deterministic semiautomata (the ordering of the edges can be recovered by just fixing an order on the alphabet and listing the transitions for a state in that order).

If the DAG is restricted to have only one root, it is trivial (just order by left-to-right DFS). Or, for the automaton, if the automaton has a designated initial state and all other states must be reachable. But if that's not the case, I'm at a loss.

I don't see any obvious polynomial reductions from GI-complete problems that I am familiar with. My intuition tells me this looks like it should be in P.

The best algorithm I came up with so far tries to successively label the nodes with numbers from 1 to n in a canonical way by picking the ‘smallest’ root w.r.t. some suitable partial ordering (e.g. based on the number of children and the ordering numbers that have already been assigned), but when there are still several minimal roots, I don't see how to get around trying all permutations of them.

There is a paper on [isomorphism of ‘ordered graphs’](https://link.springer.com/article/10.1007/BF02684448) that seems to be similar to my problem except that their graphs are undirected and their ‘ordering’ is not a list, but a cyclic list. My intuition would tell me that my problem can be reduced to this (e.g. by adding some conspicuous ‘list beginning marker’ to recover the list from the cyclic list) but I am not quite sure. I am also not sure if there is not something more direct than their approach for my case.

EDIT: I thought about it a bit more and I think their approach doesn't work for my case at all. In my setting, there is an ordering on the outgoing edges of each node, but not on the ingoing ones. That makes a huge difference.

For illustration, here are two instances of the problem: [![two instances of the ordered DAG isomorphism problem, one isomorphic and one non-isomorphic](https://i.sstatic.net/weo1y.png)](https://i.sstatic.net/weo1y.png)

**Tags:** cc.complexity-theory, graph-algorithms, automata-theory, graph-isomorphism, directed-acyclic-graph


---

## 1 answers

### Answer by username_1 on 2020-09-12. Score: 8 | Accepted answer

If you only need to order the outgoing edges the problem is GI complete. Reduce from GI of directed graphs. Given a digraph $D$ make a new one $D’$ as follows: Make a vertex in $D’$ for every vertex of $D$ and every arc of $D$. For every arc $u \rightarrow v$ of $D$, add the arcs: $uv \rightarrow u$ and $uv \rightarrow v$ in $D’$ (in this order). Clearly $D’$ is an (ordered) DAG and two digraphs $D\_1$ and $D\_2$ are isomorphic iff their corresponding ordered dags $D\_1’$ and $D\_2’$ are (ordered) isomorphic.

If you need to order both outgoing and incoming edges there is a simple polynomial time algorithm: if $D\_1$ and $D\_2$ are connected then fixing $f(u) = v$ (for $u \in V(D\_1)$ and $v \in V(D\_2)$) uniquely determines $f$.

> **Comments:**
> **username_0**: Indeed only the outgoing edges need to be ordered. That's unfortunate! I'll think about your GI-completeness proof some more, but it seems convincing at first glance. I need this for solving a more applied problem and will probably write a paper about that; how do you want me to credit you when I mention that this is GI-complete?  
> **username_1**: Maybe an acknowledgement or a citation of this answer, as discussed here https://academia.stackexchange.com/questions/84965/how-to-cite-an-answer-in-stackexchange  
> **username_1**: I feel this is likely to be already known in the literature, perhaps you will be able to find a citation... if not then proceed as above.  
> **username_0**: I googled for ages before asking this question and found nothing. The main problem might be that I think ‘ordered graph’/‘ordered DAG’ usually means something different. I'm not sure what the commonly accepted term for ‘my’ ordered DAG is (if there is any).  

---

