Informatics Seminar (Perspective in Informatics 4B) 2010 - 2011
June 11 (Fri), 16:30 - 18:00
- Place:
Lecture Hall 1, Faculty of Engineering Bldg. No.10, Main Campus
- Title:
Combinatorial Methods for the Graph Isomorphism Problem
- Speaker:
Martin Fürer (Pennsylvania State University)
- Abstract:
The strongest successes towards polynomial time isomorphism tests for
significant classes of graphs come from group theory. Given the combinatorial
flavor of the graph isomorphism problem, we are concerned here with the
question of how much can be achieved in this area with combinatorial
methods. Positive and negative results are reviewed.
The k-dimensional Weisfeiler-Lehman algorithm (k-dim W-L) has established
itself as an ultimate combinatorial approach to the graph isomorphism
problem. Many properties based on the neighborhood of vertices have
provided useful invariants distinguishing typical non-isomorphic graphs.
Usually k-dim W-L can be shown to easily provide at least the same benefits.
Yet on the negative side, k-dim W-L is strictly weaker than the group theoretic
approach. Nevertheless, from a practical point of view, k-dim W-L can speed
up the group theoretic method significantly for typical graphs.
On the positive side, the 2-dimensional Weisfeiler-Lehman algorithm is able to
replace the somewhat unnatural numerical approximations that come with a
linear algebra approach to the graph isomorphism problem for graphs of
bounded eigenvalue multiplicity. 2-dim W-L also provides invariants which are
at least as strong as any spectral invariants based not just on eigenvalues,
but also on angles among projections of standard basis vectors into
eigenspaces.
Kyoto University
> Graduate School of Informatics
> International Courses
> Informatics Seminar