The Computational Complexity of Graph Isomorphism

This direction is split into other directions: graph isomorphism complexity. Its last version stays readable and citable here.

Version 1 of 121 papers24 conceptsfrozen 2026-10-04

The Graph Isomorphism (GI) problem asks a deceptively simple question: given two graphs, can we determine if they are structurally identical? Despite its intuitive nature, GI occupies a unique "twilight zone" in computational complexity. It is one of the few natural problems in NP that has neither been proven to be solvable in polynomial time nor shown to be NP-complete.

This gap between what we suspect is possible and what we can prove has sparked a diverse array of research directions, from deep group theory to continuous optimization and quantum landscapes.

The Complexity Gap and the Quasi-Polynomial Breakthrough

For decades, the primary challenge of GI has been its resistance to standard classification. As noted by Martin Grohe and Daniel Neuen in Recent Advances on the Graph Isomorphism Problem, the field was transformed by László Babai’s 2015 breakthrough, which moved the upper bound for the general case from exponential to quasi-polynomial time ($n^{\text{polylog}(n)}$).

However, the "holy grail"—a true polynomial-time algorithm ($n^{O(1)}$)—remains elusive. This unresolved status is not just a theoretical curiosity; it complicates the entire landscape of computational tractability. If GI were proven to be in P, it would resolve a major ambiguity in how we classify structural comparison problems.

Bridging Combinatorics and Optimization

To bridge this gap, researchers often look for specific graph families where the problem becomes easier. For instance, Ken-Ichi Kawarabayashi demonstrated in Graph Isomorphism for Bounded Genus Graphs In Linear Time that for graphs with a fixed genus, the problem can indeed be solved in linear time.

Beyond specific graph classes, another strategy involves reframing the discrete combinatorial problem as a continuous optimization task:

The Hardness of Subgraph Isomorphism

It is important to distinguish the Graph Isomorphism problem from its more difficult cousin: Subgraph Isomorphism (finding if one graph exists as a part of another). While the complexity of GI is still debated, Subgraph Isomorphism is known to be NP-complete.

Research by Jakub Pachocki and Arkadiusz Socała in The Hardness of Subgraph Isomorphism proves that Subgraph Isomorphism is fundamentally harder than other NP-complete problems like Clique, requiring significantly more time to solve in the worst case. This highlights that the "symmetry" of comparing two whole graphs in GI provides structural constraints that make it potentially much easier than the "needle in a haystack" problem of subgraph detection.

New Frontiers: Quantum and Trajectory Analysis

As classical methods push toward the polynomial boundary, new paradigms like quantum computing offer alternative perspectives. Turbasu Chatterjee and Shah Ishmam Mohtashim investigated Variational Quantum Algorithms in Energy Landscape Structure of Small Graph Isomorphism Under Variational Optimization. They found that while the final energy states of these algorithms might not perfectly distinguish graphs, the path or trajectory the optimization takes contains rich information that can be decoded using machine learning to identify isomorphisms.

By combining these diverse approaches—from the combinatorial Weisfeiler-Leman algorithm to modern optimization and quantum trajectories—researchers continue to narrow the gap, seeking to finally place the Graph Isomorphism problem firmly within the realm of polynomial-time tractability.

Papers in this version

History & citationVersion 1 · 2026-10-04

Split into other directions · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_the_computational_complexity_of_graph_is_f58dfa10,
  title = {The Computational Complexity of Graph Isomorphism},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-computational-complexity-of-graph-isomorphism/rdr_f58dfa10827e492abd6b566288e090a6},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_the_computational_complexity_of_graph_is_f58dfa10_v1,
  title = {The Computational Complexity of Graph Isomorphism},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/the-computational-complexity-of-graph-isomorphism/rdr_f58dfa10827e492abd6b566288e090a6/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}