The Graph Isomorphism Problem - NDMI122

• Title: The Graph Isomorphism Problem
• Guaranteed by: Computer Science Institute of Charles University (32-IUUK)
• Faculty: Faculty of Mathematics and Physics
• Actual: from 2025
• Semester: winter
• E-Credits: 5
• Hours per week, examination: winter s.:2/1, C+Ex [HT]
• Capacity: unlimited
• Min. number of students: unlimited
• 4EU+: no
• Virtual mobility / capacity: no
• State of the course: taught
• Language: English
• Teaching methods: full-time
• Guarantor: doc. Mgr. Robert Šámal, Ph.D.
• Teacher(s): Anna Margarethe Limbach, Dr. rer. nat.

Annotation

English

One of the most important open problems in Computer Science is the question whether two given graphs are isomorphic. This course covers the milestones in graph isomorphism testing from the 1970s until now. We study several algorithms that solve isomorphism-testing for restricted graph classes like the class of trees and forests or bounded degree graphs and we finish by studying the theoretical foundations of Babai's famous quasi-polynomial algorithm.

Last update: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)

Literature

English

Martin Grohe and Pascal Schweitzer. 2020. The graph isomorphism problem. Commun. ACM 63, 11

(November 2020), 128-134. https://doi.org/10.1145/3372123

Last update: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)

Syllabus

English

Most decision problems encountered in computer science are either solvable

by a polynomial algorithm or they are hard to a degree that there is no hope

that a practically useful algorithm is ever found. A curious exception to

this is the question whether two given graphs are isomorphic. While there is

no polynomial algorithm to decide the question, there is also no proof that

it is NP-hard. Recently, Babai has found a decision algorithm, which runs in

quasi-polynomial time using group theoretical reasoning.

This course covers the milestones in graph isomorphism testing from the

1970s until now. We study several algorithms that solve isomorphism-testing

for restricted graph classes like the class of trees and forests or bounded

degree graphs and we finish by studying the theoretical foundations of

Babai's algorithm.

Last update: Pangrác Ondřej, RNDr., Ph.D. (16.05.2025)