<p>It's <a href="https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI" rel="noreferrer">GI-complete</a> which means it's probably not NP-complete.</p>

<p>Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges)</p>

<p>Reduction from DAG isomorphism to undirected graph isomorphism: replace each arc $x\rightarrow y$ in the DAG with a four-edge subgraph consisting of a triangle having $x$ as one endpoint, and a dangling edge on the triangle connected to $y$. The reduction is only ambiguous in the case of a component that's a directed cycle, and that's not a DAG.</p>

CC BY-SA 3.0
2014-10-06T23:23:36.793Z
2017-12-24T06:57:24.213Z
2017-12-24T06:57:24.213Z
David Eppstein
<p>Given two directed acyclic graphs $G_1$ and $G_2$, is it NP-Complete to find a one-to-one mapping $f:V(G_1) \rightarrow V(G_2)$ such that $(v_i,v_j) \in D(G_1)$ if and only if $(f(v_i),f(v_j)) \in D(G_2)$?</p>

<p>$D(G)$ is defined as the set of arcs in $G$. </p>

<cc.complexity-theory><graph-theory><graph-isomorphism>
Is DAG isomorphism NP-C
Peng Zhang
# Is DAG isomorphism NP-C

(Asked by: username_0 on 2014-10-06)

Given two directed acyclic graphs $G\_1$ and $G\_2$, is it NP-Complete to find a one-to-one mapping $f:V(G\_1) \rightarrow V(G\_2)$ such that $(v\_i,v\_j) \in D(G\_1)$ if and only if $(f(v\_i),f(v\_j)) \in D(G\_2)$?

$D(G)$ is defined as the set of arcs in $G$.

**Tags:** cc.complexity-theory, graph-theory, graph-isomorphism


---

## 1 answers

### Answer by username_1 on 2014-10-06. Score: 29 | Accepted answer

It's [GI-complete](https://en.wikipedia.org/wiki/Graph_isomorphism_problem#Complexity_class_GI) which means it's probably not NP-complete.

Reduction from undirected graph isomorphism to DAG isomorphism: given an undirected graph $(V,E)$, make a DAG whose vertices are $V\cup E$, with an edge from $x$ to $y$ whenever $x\in V$, $y\in E$, and $x$ is an endpoint of $y$. (i.e. replace every undirected edge with a node and two ingoing edges)

Reduction from DAG isomorphism to undirected graph isomorphism: replace each arc $x\rightarrow y$ in the DAG with a four-edge subgraph consisting of a triangle having $x$ as one endpoint, and a dangling edge on the triangle connected to $y$. The reduction is only ambiguous in the case of a component that's a directed cycle, and that's not a DAG.


---

