5
$\begingroup$

I'm interesting in generating directed acyclic graphs (see here, for example). As part of this search, I'm curious if there are any efficient algorithms for determining a canonization of a directed acyclic graph. Or, are there any tricks that allow the canonization of a dag to be computed more efficiently than a general graph?

Determining the canonical form in general is GI-complete, but there are many specialized graphs for which it can be calculated in polynomial time. I didn't have any luck determining whether acyclic digraphs were among those specialized types, however.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
5
$\begingroup$

According to Wikipedia (which references lecture notes of Zemlyachenko, Korneenko and Tyshkevic), isomorphism of directed acyclic graphs is GI-complete. Therefore any polynomial time canonicalization algorithm for directed acyclic graphs would result in a polynomial time algorithm for graph isomorphism. Since no such algorithm is known, one concludes that no polynomial time canonicalization algorithm for directed acyclic graphs is known, and it is conjectured that none exists.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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