New answers tagged directed-acyclic-graph
5
Graph isomorphism is GI-complete for DAGs: https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI.
The problem for partial orders is also GI-complete: We can reduce bipartite graph isomorphism (which is GI-complete) to 2 instances of DAG isomorphism where the DAG equals its transitive closure by considering two canonical ways to turn a ...
Top 50 recent answers are included
