5
$\begingroup$

Does the graph isomorphism problem for directed graphs($GI_{di}$) reduce to the graph isomorphism problem for directed graphs($GI_{un}$)?

It is clear $$GI_{un}\leq GI_{di}$$ since the set of undirected graphs is subset of set of directed graphs. Does the converse hold true? That is, can an algorithm for undirected graphs used to test for problems in $GI_{di}$ with polynomial increase in complexity? Is $$GI_{di}\leq GI_{un}?$$

|cite|improve this question
$\endgroup$
6
$\begingroup$

The Wikipedia page mentions that digraph isomorphism is GI-complete, and gives a reference. For the proof, something along the following lines should work. Replace each $u\to v$ edges with a path $u\to x\to y\to v$, and attack a clique of size $A$ to $x$, and a clique of size $B \neq A$ to $y$. Choose $A,B > n$ to ensure to these are the only cliques of that size. Instead of a clique you can have a long path or a large star.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ You don't need to make the cliques nearly that big. Thought experiment: taking $A=B=0$ obviously doesn't work but the resulting graph contains no cliques bigger than $K_2$ (in fact, it has girth at least $6$). So, if you take $A=3,B=0$, anything adjacent to a 3-cycle is an "$x$" vertex and you can decode from there (the coding of an oriented $k$-cycle can be decoded in two isomorphic ways; everything else is unique, I think). Actually, I think you can even get away with $A=1$, $B=0$. $\endgroup$ – David Richerby Nov 10 '14 at 11:22
  • $\begingroup$ @DavidRicherby You can do even better than that by redirecting all nodes to the same clique: make every edge $u\rightarrow v$ into $u\rightarrow x \rightarrow y \rightarrow y \rightarrow v$, as Yuval says, and connect $x$ to a new node $z$ and use this same node $z$ in all edges. That gives you a reduction with $2|V|+1$ nodes and $4|E|$ edges, instead of $3|V|$ nodes and $4|E|$ edges. This only fails to find the right isomorphism in a graph where all edges originate from a single node, but it will still decide the problem correctly and you can check for that exception anyway. $\endgroup$ – Lieuwe Vinkhuijzen May 19 '16 at 10:26

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.