academic year 2024/25

Academic Coordinator: Alberto Policriti

Period: Second semester

Duration: 28 hours

Program:

The search for algorithms to solve the graph isomorphism problem is one of the most intriguing open challenges in graph theory. The Weisfeiler-Lehman test is a parametric collection of algorithms introduced in 1968, which has garnered and continues to attract significant attention from the scientific community.

Even in cases where the test is not complete (i.e., non-isomorphic graphs may pass the test for a fixed parameter value), the Weisfeiler-Lehman test with relatively low parameter values has proven to be highly useful and interesting. It has found applications in:

• Neural network research,
• Computational chemistry,
• Circuit design.

From a theoretical perspective, the test is particularly compelling, offering elegant and natural algebraic and logical characterizations.

The course will offer both theoretical insights and practical applications, fostering a comprehensive understanding of the Weisfeiler-Lehman test and its role in addressing the graph isomorphism problem.