Problem: Graph isomorphism

Definition:
Input: Graphs G and H in this class
Output: True iff G and H are isomorphic.

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI