HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Is complexity of $GI_{di}$ same as $GI_{un}$?

Submitted by: @import:stackexchange-cs··
0
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}?$$

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.