Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
It's GI-complete 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.
