Graph Isomorphism of directed acyclic graphs (DAGs) is known to be GI-complete. So a polynomial time algorithm to canonize DAGs is not known.
What are some special classes of DAGs that can be canonized in polynomial time ?
6
$\begingroup$
$\endgroup$
6
$\begingroup$
$\endgroup$
To start with the obvious: DAGs containing a Hamiltonian path, using the uniqueness of their topological orderings, and polytrees, as an orientation-labeled variant of trees.
On the other hand, it's tempting to list multitrees (as I did in an earlier incorrect version of this answer), using canonization of trees to prioritize their topological orderings, but they're GI-complete (subdivide each edge of an undirected graph into two directed edges oriented outwards from the subdivision point), so that doesn't work.
answered Mar 29 '13 at 17:27
-
$\begingroup$ Thanks David. Hamiltonian-DAGs and orientations of trees are two classes that occurred to me. Is this the state-of-the art ? What about planar DAGs, DAGs with limited number of source/sinks ? Are they GI-complete ? $\endgroup$ – Shiva Kintali Mar 30 '13 at 16:25
-
$\begingroup$ I imagine planar DAGs are not any harder than other kinds of planar graphs to solve isomorphism for (logspace, and therefore P). The limited number of sources and sinks doesn't help, though, because you could just add a new source or sink to your graph connecting to all the vertices that were previously sources or sinks, reducing the number of sources or sinks to one without making the problem easier. $\endgroup$ – David Eppstein Mar 30 '13 at 22:52
