5 Search Results for "Fuhlbrück, Frank"

Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.129
An Upper Bound on the Weisfeiler-Leman Dimension

Authors: Thomas Schneider and Pascal Schweitzer

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
The Weisfeiler-Leman (WL) algorithms form a family of incomplete approaches to the graph isomorphism problem. They recently found various applications in algorithmic group theory and machine learning. In fact, the algorithms form a parameterized family: for each k ∈ ℕ there is a corresponding k-dimensional algorithm WLk. The algorithms become increasingly powerful with increasing dimension, but at the same time the running time increases. The WL-dimension of a graph G is the smallest k ∈ ℕ for which WLk correctly decides isomorphism between G and every other graph. In some sense, the WL-dimension measures how difficult it is to test isomorphism of one graph to others using a fairly general class of combinatorial algorithms. Nowadays, it is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on n vertices is at most 3/20 ⋅ n + o(n) = 0.15 ⋅ n + o(n). Reducing the question to coherent configurations, the proof develops various techniques to analyze their structure. This includes sufficient conditions under which a fiber can be restored uniquely up to isomorphism if it is removed, a recursive proof exploiting a degree reduction and treewidth bounds, as well as an exhaustive analysis of interspaces involving small fibers. As a base case, we also analyze the dimension of coherent configurations with small fiber size and thereby graphs with small color class size.
Cite as

Thomas Schneider and Pascal Schweitzer. An Upper Bound on the Weisfeiler-Leman Dimension. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 129:1-129:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{schneider_et_al:LIPIcs.ICALP.2025.129,
  author =	{Schneider, Thomas and Schweitzer, Pascal},
  title =	{{An Upper Bound on the Weisfeiler-Leman Dimension}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{129:1--129:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.129},
  URN =		{urn:nbn:de:0030-drops-235065},
  doi =		{10.4230/LIPIcs.ICALP.2025.129},
  annote =	{Keywords: Weisfeiler-Leman dimension, descriptive complexity, coherent configurations}
}
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.STACS.2024.6
On a Hierarchy of Spectral Invariants for Graphs

Authors: V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky

Published in: LIPIcs, Volume 289, 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)

Abstract
We consider a hierarchy of graph invariants that naturally extends the spectral invariants defined by Fürer (Lin. Alg. Appl. 2010) based on the angles formed by the set of standard basis vectors and their projections onto eigenspaces of the adjacency matrix. We provide a purely combinatorial characterization of this hierarchy in terms of the walk counts. This allows us to give a complete answer to Fürer’s question about the strength of his invariants in distinguishing non-isomorphic graphs in comparison to the 2-dimensional Weisfeiler-Leman algorithm, extending the recent work of Rattan and Seppelt (SODA 2023). As another application of the characterization, we prove that almost all graphs are determined up to isomorphism in terms of the spectrum and the angles, which is of interest in view of the long-standing open problem whether almost all graphs are determined by their eigenvalues alone. Finally, we describe the exact relationship between the hierarchy and the Weisfeiler-Leman algorithms for small dimensions, as also some other important spectral characteristics of a graph such as the generalized and the main spectra.
Cite as

V. Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On a Hierarchy of Spectral Invariants for Graphs. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 289, pp. 6:1-6:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.STACS.2024.6,
  author =	{Arvind, V. and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg},
  title =	{{On a Hierarchy of Spectral Invariants for Graphs}},
  booktitle =	{41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024)},
  pages =	{6:1--6:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-311-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{289},
  editor =	{Beyersdorff, Olaf and Kant\'{e}, Mamadou Moustapha and Kupferman, Orna and Lokshtanov, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2024.6},
  URN =		{urn:nbn:de:0030-drops-197166},
  doi =		{10.4230/LIPIcs.STACS.2024.6},
  annote =	{Keywords: Graph Isomorphism, spectra of graphs, combinatorial refinement, strongly regular graphs}
}
Document
DOI: 10.4230/LIPIcs.STACS.2020.43
Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Authors: Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky

Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)

Abstract
It is well known that the isomorphism problem for vertex-colored graphs with color multiplicity at most 3 is solvable by the classical 2-dimensional Weisfeiler-Leman algorithm (2-WL). On the other hand, the prominent Cai-Fürer-Immerman construction shows that even the multidimensional version of the algorithm does not suffice for graphs with color multiplicity 4. We give an efficient decision procedure that, given a graph G of color multiplicity 4, recognizes whether or not G is identifiable by 2-WL, that is, whether or not 2-WL distinguishes G from any non-isomorphic graph. In fact, we solve the more general problem of recognizing whether or not a given coherent configuration of maximum fiber size 4 is separable. This extends our recognition algorithm to directed graphs of color multiplicity 4 with colored edges. Our decision procedure is based on an explicit description of the class of graphs with color multiplicity 4 that are not identifiable by 2-WL. The Cai-Fürer-Immerman graphs of color multiplicity 4 distinctly appear here as a natural subclass, which demonstrates that the Cai-Fürer-Immerman construction is not ad hoc. Our classification reveals also other types of graphs that are hard for 2-WL. One of them arises from patterns known as (n₃)-configurations in incidence geometry.
Cite as

Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 43:1-43:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{fuhlbruck_et_al:LIPIcs.STACS.2020.43,
  author =	{Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Verbitsky, Oleg},
  title =	{{Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm}},
  booktitle =	{37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)},
  pages =	{43:1--43:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-140-5},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{154},
  editor =	{Paul, Christophe and Bl\"{a}ser, Markus},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.43},
  URN =		{urn:nbn:de:0030-drops-119046},
  doi =		{10.4230/LIPIcs.STACS.2020.43},
  annote =	{Keywords: Graph Isomorphism, Weisfeiler-Leman Algorithm, Cai-F\"{u}rer-Immerman Graphs, coherent Configurations}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2016.13
The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs

Authors: Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan

Published in: LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

Abstract
In this paper we study the complexity of the following problems: 1. Given a colored graph X=(V,E,c), compute a minimum cardinality set of vertices S (subset of V) such that no nontrivial automorphism of X fixes all vertices in S. A closely related problem is computing a minimum base S for a permutation group G <= S_n given by generators, i.e., a minimum cardinality subset S of [n] such that no nontrivial permutation in G fixes all elements of S. Our focus is mainly on the parameterized complexity of these problems. We show that when k=|S| is treated as parameter, then both problems are MINI[1]-hard. For the dual problems, where k=n-|S| is the parameter, we give FPT~algorithms. 2. A notion closely related to fixing is called individualization. Individualization combined with the Weisfeiler-Leman procedure is a fundamental technique in algorithms for Graph Isomorphism. Motivated by the power of individualization, in the present paper we explore the complexity of individualization: what is the minimum number of vertices we need to individualize in a given graph such that color refinement "succeeds" on it. Here "succeeds" could have different interpretations, and we consider the following: It could mean the individualized graph becomes: (a) discrete, (b) amenable, (c)compact, or (d) refinable. In particular, we study the parameterized versions of these problems where the parameter is the number of vertices individualized. We show a dichotomy: For graphs with color classes of size at most 3 these problems can be solved in polynomial time, while starting from color class size 4 they become W[P]-hard.
Cite as

Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, Sebastian Kuhnert, and Gaurav Rattan. The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{arvind_et_al:LIPIcs.MFCS.2016.13,
  author =	{Arvind, Vikraman and Fuhlbr\"{u}ck, Frank and K\"{o}bler, Johannes and Kuhnert, Sebastian and Rattan, Gaurav},
  title =	{{The Parameterized Complexity of Fixing Number and Vertex Individualization in Graphs}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.13},
  URN =		{urn:nbn:de:0030-drops-64294},
  doi =		{10.4230/LIPIcs.MFCS.2016.13},
  annote =	{Keywords: parameterized complexity, graph automorphism, fixing number, base size, individualization}
}
  • Refine by Type
  • 5 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2024
  • 1 2020
  • 1 2016

  • Refine by Author
  • 3 Fuhlbrück, Frank
  • 3 Köbler, Johannes
  • 2 Schweitzer, Pascal
  • 2 Verbitsky, Oleg
  • 1 Arvind, V.
  • Show More...

  • Refine by Series/Journal
  • 5 LIPIcs

  • Refine by Classification
  • 2 Mathematics of computing → Graph algorithms
  • 2 Theory of computation → Graph algorithms analysis
  • 2 Theory of computation → Problems, reductions and completeness
  • 1 Mathematics of computing → Combinatorics
  • 1 Mathematics of computing → Graph theory
  • Show More...

  • Refine by Keyword
  • 2 Graph Isomorphism
  • 2 coherent configurations
  • 1 Cai-Fürer-Immerman Graphs
  • 1 Weisfeiler-Leman Algorithm
  • 1 Weisfeiler-Leman algorithm
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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