<p>Graph isomorphism is GI-complete for DAGs: <a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI" rel="noreferrer">https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI</a>. </p>

<p>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.</p>

CC BY-SA 4.0
2019-11-06T21:17:52.003Z
2019-11-07T06:47:06.087Z
2019-11-07T06:47:06.087Z
Laakeri
<p>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?</p>

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

<cc.complexity-theory><graph-isomorphism><directed-acyclic-graph><partial-order>
Is the isomorphism problem between posets represented by DAGs GI-complete?
Stephane Bersier
# Is the isomorphism problem between posets represented by DAGs GI-complete?

(Asked by: username_0 on 2019-11-06)

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.

**Tags:** cc.complexity-theory, graph-isomorphism, directed-acyclic-graph, partial-order


---

## 1 answers

### Answer by username_1 on 2019-11-06. Score: 8 | Accepted answer

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.


---

