5
$\begingroup$

Given two directed acyclic graphs, how hard is the problem of checking whether the partial orders they represent are isomorphic? Is this problem GI-complete?

I believe this problem is equivalent to asking whether their transitive closures (or their transitive reductions) are isomorphic.

$\endgroup$
6
$\begingroup$

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 bipartite graph into a DAG, that is, either directing all edges from partition 1 to partition 2 or directing all edges from partition 2 to partition 1.

$\endgroup$

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.