Kiefer, Sandra ;
Neuen, Daniel
The Power of the WeisfeilerLeman Algorithm to Decompose Graphs
Abstract
The WeisfeilerLeman procedure is a widelyused approach for graph isomorphism testing that works by iteratively computing an isomorphisminvariant coloring of vertex tuples. Meanwhile, a fundamental tool in structural graph theory, which is often exploited in approaches to tackle the graph isomorphism problem, is the decomposition into bi and triconnected components.
We prove that the 2dimensional WeisfeilerLeman algorithm implicitly computes the decomposition of a graph into its triconnected components. Thus, the dimension of the algorithm needed to distinguish two given graphs is at most the dimension required to distinguish the corresponding decompositions into 3connected components (assuming dimension at least 2).
This result implies that for k >= 2, the kdimensional algorithm distinguishes kseparators, i.e., ktuples of vertices that separate the graph, from other vertex ktuples. As a byproduct, we also obtain insights about the connectivity of constituent graphs of association schemes.
In an application of the results, we show the new upper bound of k on the WeisfeilerLeman dimension of graphs of treewidth at most k. Using a construction by Cai, Fürer, and Immerman, we also provide a new lower bound that is asymptotically tight up to a factor of 2.
BibTeX  Entry
@InProceedings{kiefer_et_al:LIPIcs:2019:10989,
author = {Sandra Kiefer and Daniel Neuen},
title = {{The Power of the WeisfeilerLeman Algorithm to Decompose Graphs}},
booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)},
pages = {45:145:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771177},
ISSN = {18688969},
year = {2019},
volume = {138},
editor = {Peter Rossmanith and Pinar Heggernes and JoostPieter Katoen},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10989},
URN = {urn:nbn:de:0030drops109893},
doi = {10.4230/LIPIcs.MFCS.2019.45},
annote = {Keywords: WeisfeilerLeman, separators, firstorder logic, counting quantifiers}
}
20.08.2019
Keywords: 

WeisfeilerLeman, separators, firstorder logic, counting quantifiers 
Seminar: 

44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)

Issue date: 

2019 
Date of publication: 

20.08.2019 