Isomorphism, Canonization, and Definability for Graphs of Bounded Rank Width

摘要

We investigate the interplay between the graph isomorphism problem, logical definability, and structural graph theory on a rich family of dense graph classes: graph classes of bounded rank width. We prove that the combinatorial Weisfeiler-Leman algorithm of dimension (3k + 4) is a complete isomorphism test for the class of all graphs of rank width at most k. A consequence of our result is the first polynomial time canonization algorithm for graphs of bounded rank width.Our second main result addresses an open problem in descriptive complexity theory: we show that fixed-point logic with counting expresses precisely the polynomial time properties of graphs of bounded rank width.