Sandra Kiefer ; Pascal Schweitzer - Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic

lmcs:4015 - Logical Methods in Computer Science, May 30, 2019, Volume 15, Issue 2 -
Upper Bounds on the Quantifier Depth for Graph Differentiation in First-Order Logic

Authors: Sandra Kiefer ; Pascal Schweitzer

    We show that on graphs with n vertices, the 2-dimensional Weisfeiler-Leman algorithm requires at most O(n^2/log(n)) iterations to reach stabilization. This in particular shows that the previously best, trivial upper bound of O(n^2) is asymptotically not tight. In the logic setting, this translates to the statement that if two graphs of size n can be distinguished by a formula in first-order logic with counting with 3 variables (i.e., in C3), then they can also be distinguished by a C3-formula that has quantifier depth at most O(n^2/log(n)). To prove the result we define a game between two players that enables us to decouple the causal dependencies between the processes happening simultaneously over several iterations of the algorithm. This allows us to treat large color classes and small color classes separately. As part of our proof we show that for graphs with bounded color class size, the number of iterations until stabilization is at most linear in the number of vertices. This also yields a corresponding statement in first-order logic with counting. Similar results can be obtained for the respective logic without counting quantifiers, i.e., for the logic L3.

    Volume: Volume 15, Issue 2
    Published on: May 30, 2019
    Accepted on: March 11, 2019
    Submitted on: October 25, 2017
    Keywords: Computer Science - Logic in Computer Science,Computer Science - Computational Complexity,Mathematics - Combinatorics,F.4.1

    Linked publications - datasets - softwares

    Source : ScholeXplorer IsCitedBy ARXIV 2106.16218
    Source : ScholeXplorer IsCitedBy DOI 10.18154/rwth-2021-06468
    Source : ScholeXplorer IsCitedBy DOI 10.4230/lipics.icalp.2021.134
    Source : ScholeXplorer IsCitedBy DOI 10.48550/arxiv.2106.16218
    • 10.4230/lipics.icalp.2021.134
    • 10.18154/rwth-2021-06468
    • 10.48550/arxiv.2106.16218
    • 2106.16218
    Logarithmic Weisfeiler-Leman Identifies All Planar Graphs
    Grohe, Martin ; Kiefer, Sandra ;

    2 Documents citing this article

    Consultation statistics

    This page has been seen 843 times.
    This article's PDF has been downloaded 227 times.