The problem of determining whether two finite graphs are structurally identical up to a relabeling of their vertices; known to be in NP, not known to be solvable in polynomial time, and not known to be NP-complete either, placing it in a rare and still unresolved complexity status of its own.
Facts
Core PrincipleDetermining whether two finite graphs are isomorphic. 1 Connections
Sources
1. Wikipedia: Graph isomorphism problem
Lead, first sentence
is the computational problem of determining whether two finite graphs are isomorphic.
In Group: Unresolved Problems in Complexity Theory, Lead
The graph isomorphism problem is the computational problem of determining whether two finite graphs are isomorphic.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.