一句话：证明(3k+4)维Weisfeiler-Leman算法完全判定秩宽≤k图的同构，并得到多项式时间典范化与计数固定点逻辑刻画。
本文研究有界秩宽图上的同构测试与典范化问题。秩宽与团宽等价，此类图的同构虽已知多项式可判定，但此前最好算法运行时间为 n^{f(k)}，其中 f 为非初等函数。作者证明维数为 3k+4 的组合 Weisfeiler-Leman 算法对所有秩宽不超过 k 的图都是完全同构测试。由此得到运行时间为 n^{O(k)} 的同构测试，并首次给出有界秩宽图的多项式时间典范化算法。第二个主要结果是：带计数的固定点逻辑在所有有界秩宽图类上捕获多项式时间。
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. Rank width is a graph invariant that, similarly to tree width, measures the width of a certain style of hierarchical decomposition of graphs; it is equivalent to clique width. It was known that isomorphism of graphs of rank width k is decidable in polynomial time (Grohe and Schweitzer, FOCS 2015), but the best previously known algorithm has a running time nf(k)for a non-elementary function f. Our result yields an isomorphism test for graphs of rank width k running in time nO(k). Another consequence of our result is the first polynomial time canonisation algorithm for graphs of bounded rank width. Our second main result is that fixed-point logic with counting captures polynomial time on all graph classes of bounded rank width.
DOI 原文 ·
@inproceedings{paperbot4986,
title = {Canonisation and Definability for Graphs of Bounded Rank Width},
author = {Martin Grohe and Daniel Neuen},
booktitle = {LICS},
year = {2019},
doi = {10.1109/lics.2019.8785682}
}