Search Results

Documents authored by Raßmann, Simon

Document
DOI: 10.4230/LIPIcs.CSL.2025.13
Computational Complexity of the Weisfeiler-Leman Dimension

Authors: Moritz Lichter, Simon Raßmann, and Pascal Schweitzer

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
The Weisfeiler-Leman dimension of a graph G is the least number k such that the k-dimensional Weisfeiler-Leman algorithm distinguishes G from every other non-isomorphic graph, or equivalently, the least k such that G is definable in (k+1)-variable first-order logic with counting. The dimension is a standard measure of the descriptive or structural complexity of a graph and recently finds various applications in particular in the context of machine learning. This paper studies the complexity of computing the Weisfeiler-Leman dimension. We observe that deciding whether the Weisfeiler-Leman dimension of G is at most k is NP-hard, even if G is restricted to have 4-bounded color classes. For each fixed k ≥ 2, we give a polynomial-time algorithm that decides whether the Weisfeiler-Leman dimension of a given graph with 5-bounded color classes is at most k. Moreover, we show that for these bounds on the color classes, this is optimal because the problem is PTIME-hard under logspace-uniform AC_0-reductions. Furthermore, for each larger bound c on the color classes and each fixed k ≥ 2, we provide a polynomial-time decision algorithm for the abelian case, that is, for structures of which each color class has an abelian automorphism group. While the graph classes we consider may seem quite restrictive, graphs with 4-bounded abelian colors include CFI-graphs and multipedes, which form the basis of almost all known hard instances and lower bounds related to the Weisfeiler-Leman algorithm.
Cite as

Moritz Lichter, Simon Raßmann, and Pascal Schweitzer. Computational Complexity of the Weisfeiler-Leman Dimension. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 13:1-13:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{lichter_et_al:LIPIcs.CSL.2025.13,
  author =	{Lichter, Moritz and Ra{\ss}mann, Simon and Schweitzer, Pascal},
  title =	{{Computational Complexity of the Weisfeiler-Leman Dimension}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{13:1--13:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.13},
  URN =		{urn:nbn:de:0030-drops-227707},
  doi =		{10.4230/LIPIcs.CSL.2025.13},
  annote =	{Keywords: Weisfeiler-Leman algorithm, dimension, complexity, coherent configurations}
}
Document
DOI: 10.4230/LIPIcs.CSL.2025.14
Finite Variable Counting Logics with Restricted Requantification

Authors: Simon Raßmann, Georg Schindling, and Pascal Schweitzer

Published in: LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)

Abstract
Counting logics with a bounded number of variables form one of the central concepts in descriptive complexity theory. Although they restrict the number of variables that a formula can contain, the variables can be nested within scopes of quantified occurrences of themselves. In other words, the variables can be requantified. We study the fragments obtained from counting logics by restricting requantification for some but not necessarily all the variables. Similar to the logics without limitation on requantification, we develop tools to investigate the restricted variants. Specifically, we introduce a bijective pebble game in which certain pebbles can only be placed once and for all, and a corresponding two-parametric family of Weisfeiler-Leman algorithms. We show close correspondences between the three concepts. By using a suitable cops-and-robber game and adaptations of the Cai-Fürer-Immerman construction, we completely clarify the relative expressive power of the new logics. We show that the restriction of requantification has beneficial algorithmic implications in terms of graph identification. Indeed, we argue that with regard to space complexity, non-requantifiable variables only incur an additive polynomial factor when testing for equivalence. In contrast, for all we know, requantifiable variables incur a multiplicative linear factor. Finally, we observe that graphs of bounded tree-depth and 3-connected planar graphs can be identified using no, respectively, only a very limited number of requantifiable variables.
Cite as

Simon Raßmann, Georg Schindling, and Pascal Schweitzer. Finite Variable Counting Logics with Restricted Requantification. In 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 326, pp. 14:1-14:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ramann_et_al:LIPIcs.CSL.2025.14,
  author =	{Ra{\ss}mann, Simon and Schindling, Georg and Schweitzer, Pascal},
  title =	{{Finite Variable Counting Logics with Restricted Requantification}},
  booktitle =	{33rd EACSL Annual Conference on Computer Science Logic (CSL 2025)},
  pages =	{14:1--14:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-362-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{326},
  editor =	{Endrullis, J\"{o}rg and Schmitz, Sylvain},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.14},
  URN =		{urn:nbn:de:0030-drops-227716},
  doi =		{10.4230/LIPIcs.CSL.2025.14},
  annote =	{Keywords: Requantification, Finite variable counting logics, Weisfeiler-Leman algorithm}
}
Document
DOI: 10.4230/LIPIcs.IPEC.2023.25
Twin-Width of Graphs with Tree-Structured Decompositions

Authors: Irene Heinrich and Simon Raßmann

Published in: LIPIcs, Volume 285, 18th International Symposium on Parameterized and Exact Computation (IPEC 2023)

Abstract
The twin-width of a graph measures its distance to co-graphs and generalizes classical width concepts such as tree-width or rank-width. Since its introduction in 2020 [Édouard Bonnet et al., 2022; Édouard Bonnet et al., 2020], a mass of new results has appeared relating twin width to group theory, model theory, combinatorial optimization, and structural graph theory. We take a detailed look at the interplay between the twin-width of a graph and the twin-width of its components under tree-structured decompositions: We prove that the twin-width of a graph is at most twice its strong tree-width, contrasting nicely with the result of [Édouard Bonnet and Hugues Déprés, 2023; Édouard Bonnet and Hugues Déprés, 2022], which states that twin-width can be exponential in tree-width. Further, we employ the fundamental concept from structural graph theory of decomposing a graph into highly connected components, in order to obtain optimal linear bounds on the twin-width of a graph given the widths of its biconnected components. For triconnected components we obtain a linear upper bound if we add red edges to the components indicating the splits which led to the components. Extending this approach to quasi-4-connectivity, we obtain a quadratic upper bound. Finally, we investigate how the adhesion of a tree decomposition influences the twin-width of the decomposed graph.
Cite as

Irene Heinrich and Simon Raßmann. Twin-Width of Graphs with Tree-Structured Decompositions. In 18th International Symposium on Parameterized and Exact Computation (IPEC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 285, pp. 25:1-25:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{heinrich_et_al:LIPIcs.IPEC.2023.25,
  author =	{Heinrich, Irene and Ra{\ss}mann, Simon},
  title =	{{Twin-Width of Graphs with Tree-Structured Decompositions}},
  booktitle =	{18th International Symposium on Parameterized and Exact Computation (IPEC 2023)},
  pages =	{25:1--25:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-305-8},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{285},
  editor =	{Misra, Neeldhara and Wahlstr\"{o}m, Magnus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2023.25},
  URN =		{urn:nbn:de:0030-drops-194449},
  doi =		{10.4230/LIPIcs.IPEC.2023.25},
  annote =	{Keywords: twin-width, quasi-4 connected components, strong tree-width}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact