Problem: Hamiltonian path

Definition:
Input: A graph G in this class.
Output: True iff G has a simple path that goes through every vertex of the graph.

Linear

Polynomial

GI-complete

NP-hard

NP-complete

coNP-complete

Open

Unknown to ISGCI