Sign inSign in

Graph isomorphism problem

The computational problem of determining whether two finite graphs are isomorphic, meaning one can be transformed into the other by permuting its vertices.
as Ryan O'Donnell defines itCarnegie Mellon UniversityThe wording closest to all 4 definitions
Watch it explained

Know first

Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.

Graph theory3Permutation2Adjacency matrix1Edge1Graph1NP1P1P and NP complexity classes1

Lecturers

3

Each in their own terms, from the easiest level.

  • Ryan O'Donnell

    Carnegie Mellon University · Undergraduate

    Given two graphs, determine if they are isomorphic, meaning one can be transformed into the other by permuting vertex labels.
    • 29:11The Hidden Subgroup Problem
  • Colva Roney-Dougal

    Gresham College · Undergraduate

    The graph isomorphism problem asks whether two graphs are the same, just with different vertex names and drawn differently.
    • 33:00How Hard is too Hard? An Introduction to Complexity
  • Michael Sipser

    MIT · Undergraduate

    Testing whether two graphs are permutations of one another, which is in NP but not known to be in P.

Connections

8

The lectures that define it or assume it, and the concepts next to it.

Concepts4

Lectures4

3 lecturers. Definitions are written by AI from each lecture’s transcript. A time with a play mark starts the lecture at the moment the lecturer says it.