patternMinor
Is complexity of $GI_{di}$ same as $GI_{un}$?
Viewed 0 times
samegi_complexity
Problem
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}?$$
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}?$$
Solution
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.
Context
StackExchange Computer Science Q#32904, answer score: 6
Revisions (0)
No revisions yet.