Math 2.0

Computer science Computational complexity: resources and classes Problem

Graph isomorphism problem

Builds on GraphGraph isomorphismNPPNP-completenessLadner's theorem

Problem

An input is a pair (G,H)(G, H) of finite graphs, given by adjacency matrices. The graph isomorphism problem asks whether GG and HH are isomorphic. That is, it asks for a bijection π\pi from the vertices of GG to the vertices of HH with the following property. For all vertices u,vu, v of GG, they are adjacent in GG exactly when π(u),π(v)\pi(u), \pi(v) are adjacent in HH.

Remarks

The problem lies in NP, since an isomorphism π\pi is a certificate checkable in polynomial time. It is not known to lie in P, and it is not known to be NP-complete. If it were NP-complete, the polynomial hierarchy would collapse to its second level, so most researchers expect that it is not. It is thus a main candidate for a natural NP-intermediate problem, a kind of problem that exists by Ladner's theorem if P≠NP\mathrm{P} \ne \mathrm{NP}. In 2015 László Babai announced an algorithm in quasi-polynomial time exp⁡((log⁡n)O(1))\exp((\log n)^{O(1)}) for graphs with nn vertices. Polynomial-time algorithms are known for special classes, such as trees, planar graphs and graphs of bounded degree.

Reading path

To understand this page from the ground up, read these 8 pages in order. The foundations come first.

Show the path as a graph
Graph, concept, no evidence levelGraphconceptGraph isomorphism, concept, no evidence levelGraph isomorphismconceptNP, concept, no evidence levelNPconceptNP-completeness, concept, no evidence levelNP-completenessconceptP, concept, no evidence levelPconceptPolynomial-time reduction, concept, no evidence levelPolynomial-time reduc…conceptLadner's theorem, statement, no evidence levelLadner's theoremstatementGraph isomorphism problem, problem, no evidence levelGraph isomorphism pro…problem
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Graph concept
  2. Graph isomorphism concept
  3. NP concept
  4. NP-completeness concept
  5. P concept
  6. Polynomial-time reduction concept
  7. Ladner's theorem statement
  8. Graph isomorphism problem problem

Further reading

  1. Web https://en.wikipedia.org/wiki/Graph_isomorphism_problem
About this page
Tag45DQMP5980
URIm2://45DQMP5980
Kindproblem
WritingW0 stub
MSC68Q17, 05C60, 68R10
StatusThis copy of the site has no build data. Run m2 status 45DQMP5980.
AboutGraph isomorphism
UsesGraph, Graph isomorphism, NP, P, NP-completeness, Ladner's theorem
Same as
Changed3 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.