<p>I found a previous answer that covers this, by showing that DAG isomorphism is GI-complete: <a href="https://cstheory.stackexchange.com/questions/25975/is-dag-isomorphism-np-c">Is DAG isomorphism NP-C</a></p>

CC BY-SA 4.0
2024-12-15T10:14:28.633Z
2024-12-15T10:18:30.610Z
2024-12-15T10:18:30.610Z
John P.
<p>An oriented simple graph is a graph with at most one edge between each pair of vertices and where each edge has an orientation. Equivalently, it is a directed graph with at most one edge (of either orientation) between each pair of vertices. In contrast, the definition of a simple directed graph appears to allow at most one of each orientation.</p>
<p>Is isomorphism testing for oriented simple graphs GI-hard? Is there any discussion of the problem in the literature (perhaps using a different name for this class of graphs)?</p>
<p>A tournament has exactly one edge (of either orientation); isomorphism testing for tournaments appears to be open, but has at least been studied [1].</p>
<p>[1] <a href="https://link.springer.com/chapter/10.1007/978-3-540-74456-6_51" rel="nofollow noreferrer">https://link.springer.com/chapter/10.1007/978-3-540-74456-6_51</a></p>

<graph-theory><graph-isomorphism>
Is oriented simple graph isomorphism GI-hard?
John P.
# Is oriented simple graph isomorphism GI-hard?

(Asked by: username_0 on 2024-12-15)

An oriented simple graph is a graph with at most one edge between each pair of vertices and where each edge has an orientation. Equivalently, it is a directed graph with at most one edge (of either orientation) between each pair of vertices. In contrast, the definition of a simple directed graph appears to allow at most one of each orientation.

Is isomorphism testing for oriented simple graphs GI-hard? Is there any discussion of the problem in the literature (perhaps using a different name for this class of graphs)?

A tournament has exactly one edge (of either orientation); isomorphism testing for tournaments appears to be open, but has at least been studied [1].

[1] <https://link.springer.com/chapter/10.1007/978-3-540-74456-6_51>

**Tags:** graph-theory, graph-isomorphism


---

## 1 answers

### Answer by username_0 on 2024-12-15. Score: 8 | Accepted answer

I found a previous answer that covers this, by showing that DAG isomorphism is GI-complete: [Is DAG isomorphism NP-C](https://cstheory.stackexchange.com/questions/25975/is-dag-isomorphism-np-c)


---

