7
$\begingroup$

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’ 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

$\endgroup$
8
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Manuel Eberl Sep 12 at 22:34
  • $\begingroup$ Maybe an acknowledgement or a citation of this answer, as discussed here academia.stackexchange.com/questions/84965/… $\endgroup$ – daniello Sep 12 at 22:44
  • $\begingroup$ 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. $\endgroup$ – daniello Sep 12 at 22:51
  • $\begingroup$ 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). $\endgroup$ – Manuel Eberl Sep 12 at 23:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.