2
$\begingroup$

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?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Perhaps it is not too hard to extend from the undirected case? If the undirected versions of the graphs are not isomorphic, then the directed versions also are not isomorphic. Given an isomorphism, it is simple to check if it works for the undirected graph. So, we can solve this problem unless there are too many isomorphisms of the undirected graphs. Perhaps there is a suitable bound on the number of them? $\endgroup$ – Discrete lizard♦ Apr 16 '19 at 15:30
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

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.