HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Efficient algorithm for graph canonization for directed acyclic graphs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
graphacyclicefficientcanonizationdirectedgraphsalgorithmfor

Problem

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.

Solution

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.

Context

StackExchange Computer Science Q#60577, answer score: 5

Revisions (0)

No revisions yet.