Isomorphism problem on bounded degree digraphs

Question

By Babai & Luks (1983), it was proved that graph isomorphism problem is tractable on bounded degree graphs. However, I could not find any result when the graph is edge directed.

Is isomorphism problem tractable (or GI-complete) on edge-directed graphs with bounded degree?

Answer 1

You can reduce graph isomorphism on directed graphs to graph isomorphism on undirected graphs. I think it's possible to build a reduction that preserves the bounded-degree property.

For instance, I think the following should work. Replace each directed edge u --> v with the following gadget:

u --- a --- c --- v
      |
      b

where a, b, and c are fresh new vertices (different ones for each edge).

Next, we'll add some edges to make sure that the isomorphism makes original vertices like u, v map to other original vertices (not to the new vertices). Add a new vertex A (just one), and connect A to each of the a's; to do this in a way that preserves bounded edge degree, use a binary tree. Finally, add a long path A --- A' --- A" --- A"' --- ... with n+3 new vertices, where n is the number of vertices in the original graph. Add a new vertex B, connected to a path of n+2 new vertices, and connect it to the b-type vertices as above; and add a C, connected to a path of n+1 new vertices, connected to the c-type vertices.

Apply this transformation to both directed graphs, to get two undirected graphs. Now I think any isomorphism of the resulting undirected graphs corresponds to an isomorphism of the original directed graphs. In particular, the isomorphism must map the two n+1 paths to each other; so it must map the two A-type vertices to each other; so it must map a-type vertices to other a-type vertices; and similarly, b-type to b-type and c-type to c-type. Thus vertices of the original directed graph must be mapped to vertices of the other original directed graph. The mapping must preserve the direction of the edges, due to the asymmetry in the gadget above.