23.05.2019
13:00 - 14:00
The Weisfeiler-Leman Dimension of Graphs of Bounded Treedepth
Luca Oeljeklaus
In this talk we discuss the dimension of the Weisfeiler-Leman (WL) algorithm, which is a combinatorial algorithm used as a subroutine for graph isomorphism testing, in terms of treedepth, a graph invariant also referred to as minimum elimination tree height or vertex ranking number. More precisely, we prove upper and lower bounds on the WL-dimension of graphs of bounded treedepth by using two results from Cai, Fürer, and Immerman. In our proof to show that every graph of treedepth at most k is identified by the (k-1)-dimensional WL-algorithm, we use the fact that the (k-1)-dimensional WL-algorithm identifying a graph is equivalent to Spoiler having a winning strategy for the C_k-pebble game between a graph of treedepth at most k and any other non-isomorphic graph. From there we develop an inductive winning strategy for Spoiler over the treedepth of the graph. In our proof to show that there exists a family of pairs of graphs of treedepth k for arbitrarily large k such that the (k/25)-dimensional WL-algorithm does not distinguish them, we apply the CFI-graph construction to a family of graphs with large separators and then prove an upper bound on the treedepth of the resulting pairs of graphs.