14 Search Results for "McKay, Brendan D."

Document
Invited Talk
DOI: 10.4230/LIPIcs.CSL.2026.2
The Logic Behind Colour Refinement (Invited Talk)

Authors: Sandra Kiefer

Published in: LIPIcs, Volume 363, 34th EACSL Annual Conference on Computer Science Logic (CSL 2026)

Abstract
Colour Refinement is a combinatorial algorithm that computes a vertex colouring for an input graph to reveal its structural properties. Each iteration of the algorithm refines the current colouring by assessing local information. More precisely, the new colour of a vertex is determined by its current colour and the multiset of colours in its neighbourhood. This refinement procedure continues until it reaches a stable partition of the vertex set into colour classes. On the practical side, the algorithm admits fast implementations. Because the final colouring is isomorphism-invariant, executing the algorithm on two graphs in parallel can be used to demonstrate that they are not isomorphic. From a theoretical perspective, the algorithm is arguably the most straightforward combinatorial approach to detecting asymmetries - specifically for distinguishing vertices that do not belong to the same orbit of the automorphism group of the graph. Its numerous connections to other areas in computer science stand as evidence of its robustness and naturalness and make it a fascinating object of research. Among the most elegant connections is the link to counting logic. Colour Refinement assigns distinct final colours to two vertices in a graph if and only if there is a formula in the two-variable fragment C² of the logic C that distinguishes them, meaning that the formula holds for precisely one of the two vertices. In fact, the vertex colours translate directly into logical formulas with one free variable. As a consequence, Colour Refinement distinguishes two graphs if and only if there is a C²-sentence that distinguishes them. This correspondence extends to higher dimensions: the k-variable fragment C^k of C corresponds to the (k-1)-dimensional extension of Colour Refinement, the (k-1)-dimensional Weisfeiler-Leman algorithm. This algorithm computes a unique colouring for a graph G if and only if G is definable in C^k, i.e. there is a sentence in C^k whose only models are G and its isomorphic copies. As a matter of fact, the link to the logic C goes even deeper: the number of Colour Refinement iterations required to compute distinct colours corresponds exactly to the quantifier depth of a distinguishing formula. Since the iterations induce a sequence of strictly nested vertex partitions, the process must terminate after at most n-1 rounds, where n is the number of vertices. Consequently, the value n-1 serves as a trivial upper bound on both the number of iterations and the quantifier depth required to distinguish any two (distinguishable) vertices in C². My talk provides an introduction to the link between the Colour Refinement procedure and the logic C². We revisit a simple characterisation of their expressivity on graphs and on general relational structures. The characterisation implies that the definability of a graph in C² can be checked very efficiently. We then discuss tight lower bounds on the quantifier depth of C²-formulas required to distinguish vertices. Through a thorough analysis of computational data from Colour Refinement executions, we constructed infinite families of graphs that witness those bounds. We finish with a presentation of a recent purely theoretical reverse-engineering approach to finding long-refinement graphs and a classification of all such graphs with small (or, equivalently, large) degrees. The talk is based on the collaborations[Sandra Kiefer and T. Devini de Mel, 2026; Kiefer and McKay, 2020; Sandra Kiefer et al., 2022] and unpublished work.
Cite as

Sandra Kiefer. The Logic Behind Colour Refinement (Invited Talk). In 34th EACSL Annual Conference on Computer Science Logic (CSL 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 363, pp. 2:1-2:2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kiefer:LIPIcs.CSL.2026.2,
  author =	{Kiefer, Sandra},
  title =	{{The Logic Behind Colour Refinement}},
  booktitle =	{34th EACSL Annual Conference on Computer Science Logic (CSL 2026)},
  pages =	{2:1--2:2},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-411-6},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{363},
  editor =	{Guerrini, Stefano and K\"{o}nig, Barbara},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2026.2},
  URN =		{urn:nbn:de:0030-drops-254263},
  doi =		{10.4230/LIPIcs.CSL.2026.2},
  annote =	{Keywords: Colour Refinement, counting logic, Weisfeiler-Leman algorithm, variable width, quantifier depth}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.12
Semi-Random Graphs, Robust Asymmetry, and Reconstruction

Authors: Julian Asilis, Xi Chen, Dutch Hansen, and Shang-Hua Teng

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
The Graph Reconstruction Conjecture famously posits that any undirected graph on at least three vertices is determined up to isomorphism by its family of (unlabeled) induced subgraphs. At present, the conjecture admits partial resolutions of two types: 1) casework-based demonstrations of reconstructibility for families of graphs satisfying certain structural properties, and 2) probabilistic arguments establishing reconstructibility of random graphs by leveraging average-case phenomena. While results in the first category capture the worst-case nature of the conjecture, they play a limited role in understanding the general case. Results in the second category address much larger graph families, but it remains unclear how heavily the necessary arguments rely on optimistic distributional properties. Drawing on the algorithmic notions of smoothed and semi-random analysis, we study the robustness of what are arguably the two most fundamental properties in this latter line of work: asymmetry and uniqueness of subgraphs. Notably, we find that various natural semi-random graph distributions exhibit these properties asymptotically, much like their Erdős-Rényi counterparts. In particular, Bollobás [Bollob{á}s, 1990] demonstrated that almost all Erdős-Rényi random graphs G = (V, E) ∼ G(n, p) enjoy the property that their induced subgraphs on n - Θ(1) vertices are asymmetric and mutually non-isomorphic, for 1 - p, p = Ω(log(n) / n). As our primary result, we demonstrate that this property is robust against perturbation - even when an adversary is permitted to add/remove each vertex pair in V^{(2)} with (independent) arbitrarily large constant probability. Exploiting this result, we derive asymptotic characterizations of asymmetry in random graphs with large planted structure and bounded adversarial corruptions, along with improved bounds on the probability mass of nonreconstructible graphs in G(n, p).
Cite as

Julian Asilis, Xi Chen, Dutch Hansen, and Shang-Hua Teng. Semi-Random Graphs, Robust Asymmetry, and Reconstruction. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 12:1-12:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{asilis_et_al:LIPIcs.ITCS.2026.12,
  author =	{Asilis, Julian and Chen, Xi and Hansen, Dutch and Teng, Shang-Hua},
  title =	{{Semi-Random Graphs, Robust Asymmetry, and Reconstruction}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{12:1--12:21},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.12},
  URN =		{urn:nbn:de:0030-drops-252993},
  doi =		{10.4230/LIPIcs.ITCS.2026.12},
  annote =	{Keywords: Graph reconstruction, random graphs}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.52
Diffie-Hellman Key Exchange from Commutativity to Group Laws

Authors: Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In Diffie-Hellman key exchange, the commutativity of power operations is instrumental in the agreement of keys. Viewing commutativity as a law in abelian groups, we propose Diffie-Hellman key exchange in the group action framework (Brassard-Yung, Crypto'90; Ji-Qiao-Song-Yun, TCC'19), for actions of non-abelian groups with laws. The security of this protocol is shown, following Fischlin, Günther, Schmidt, and Warinschi (IEEE S&P'16), based on a pseudorandom group action assumption. A concrete instantiation is proposed based on the monomial code equivalence problem.
Cite as

Dung Hoang Duong, Youming Qiao, and Chuanqi Zhang. Diffie-Hellman Key Exchange from Commutativity to Group Laws. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 52:1-52:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{duong_et_al:LIPIcs.ITCS.2026.52,
  author =	{Duong, Dung Hoang and Qiao, Youming and Zhang, Chuanqi},
  title =	{{Diffie-Hellman Key Exchange from Commutativity to Group Laws}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{52:1--52:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.52},
  URN =		{urn:nbn:de:0030-drops-253396},
  doi =		{10.4230/LIPIcs.ITCS.2026.52},
  annote =	{Keywords: Diffie-Hellman, Key Exchange, Group Laws, Group Actions, Code Equivalence}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.14
OOPS: Optimized One-Planarity Solver via SAT

Authors: Sergey Pupyrev

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
We present OOPS (Optimized One-Planarity Solver), a practical heuristic for recognizing 1-planar graphs and several important subclasses. A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once - a natural generalization of planar graphs that has received increasing attention in graph drawing and beyond-planar graph theory. Although testing planarity can be done in linear time, recognizing 1-planar graphs is NP-complete, making effective practical algorithms especially valuable. The core idea of our approach is to reduce the recognition of 1-planarity to a propositional satisfiability (SAT) instance, enabling the use of modern SAT solvers to efficiently explore the search space. Despite the inherent complexity of the problem, our method is substantially faster in practice than naïve or brute-force algorithms. In addition to demonstrating the empirical performance of our solver on synthetic and real-world instances, we show how OOPS can be used as a discovery tool in theoretical graph theory. Specifically, we employ OOPS to investigate two research problems concerning 1-planarity of specific graph families. Our implementation of the algorithm is publicly available to support further exploration in the field.
Cite as

Sergey Pupyrev. OOPS: Optimized One-Planarity Solver via SAT. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{pupyrev:LIPIcs.GD.2025.14,
  author =	{Pupyrev, Sergey},
  title =	{{OOPS: Optimized One-Planarity Solver via SAT}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.14},
  URN =		{urn:nbn:de:0030-drops-250004},
  doi =		{10.4230/LIPIcs.GD.2025.14},
  annote =	{Keywords: beyond planarity, 1-planar graph, SAT, book embeddings, upward 1-planarity}
}
Document
DOI: 10.4230/LIPIcs.GD.2025.6
Approximating Barnette’s Conjecture

Authors: Michael A. Bekos, Michael Kaufmann, and Maximilian Pfister

Published in: LIPIcs, Volume 357, 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)

Abstract
A well-known conjecture, named after David W. Barnette, asserts that every 3-regular, 3-connected, bipartite, planar graph (for short, Barnette graph) is Hamiltonian. As another step towards addressing Barnette’s conjecture positively, we show that every n-vertex Barnette graph admits a subhamiltonian cycle containing 5n/6 edges, improving upon the previous bound of 2n/3. Equivalently, every Barnette graph admits a 2-page book embedding in which at least 5n/6 consecutive vertex pairs along the spine are connected by edges. As a byproduct, we present a simple proof for a known result that guarantees the existence of Hamiltonian cycles in a certain subclass of Barnette graphs.
Cite as

Michael A. Bekos, Michael Kaufmann, and Maximilian Pfister. Approximating Barnette’s Conjecture. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 6:1-6:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{bekos_et_al:LIPIcs.GD.2025.6,
  author =	{Bekos, Michael A. and Kaufmann, Michael and Pfister, Maximilian},
  title =	{{Approximating Barnette’s Conjecture}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{6:1--6:7},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-403-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{357},
  editor =	{Dujmovi\'{c}, Vida and Montecchiani, Fabrizio},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2025.6},
  URN =		{urn:nbn:de:0030-drops-249927},
  doi =		{10.4230/LIPIcs.GD.2025.6},
  annote =	{Keywords: Barnette’s Conjecture, Subhamiltonicity, Book embeddings}
}
Document
DOI: 10.4230/LIPIcs.ITP.2025.18
Formalising New Mathematics in Isabelle: Diagonal Ramsey

Authors: Lawrence C. Paulson

Published in: LIPIcs, Volume 352, 16th International Conference on Interactive Theorem Proving (ITP 2025)

Abstract
The formalisation of mathematics is becoming routine, but its value to research mathematicians remains unproven. There are few examples of using proof assistants to verify new work. This paper reports the formalisation - inspired by a Lean one by Bhavik Mehta - of a major new result [Marcelo Campos et al., 2023] about Ramsey numbers. One unexpected finding was a heavy role for computer algebra techniques.
Cite as

Lawrence C. Paulson. Formalising New Mathematics in Isabelle: Diagonal Ramsey. In 16th International Conference on Interactive Theorem Proving (ITP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 352, pp. 18:1-18:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{paulson:LIPIcs.ITP.2025.18,
  author =	{Paulson, Lawrence C.},
  title =	{{Formalising New Mathematics in Isabelle: Diagonal Ramsey}},
  booktitle =	{16th International Conference on Interactive Theorem Proving (ITP 2025)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-396-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{352},
  editor =	{Forster, Yannick and Keller, Chantal},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2025.18},
  URN =		{urn:nbn:de:0030-drops-246163},
  doi =		{10.4230/LIPIcs.ITP.2025.18},
  annote =	{Keywords: Isabelle, formalisation of mathematics, Ramsey’s theorem, computer algebra}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.15
Symmetry Classes of Hamiltonian Cycles

Authors: Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We initiate the study of Hamiltonian cycles up to symmetries of the underlying graph. Our focus lies on the extremal case of Hamiltonian-transitive graphs, i.e., Hamiltonian graphs where, for every pair of Hamiltonian cycles, there is a graph automorphism mapping one cycle to the other. This generalizes the extensively studied uniquely Hamiltonian graphs. In this paper, we show that Cayley graphs of abelian groups are not Hamiltonian-transitive (under some mild conditions and some non-surprising exceptions), i.e., they contain at least two structurally different Hamiltonian cycles. To show this, we reduce Hamiltonian-transitivity to properties of the prime factors of a Cartesian product decomposition, which we believe is interesting in its own right. We complement our results by constructing infinite families of regular Hamiltonian-transitive graphs and take a look at the opposite extremal case by constructing a family with many different Hamiltonian cycles up to symmetry.
Cite as

Júlia Baligács, Sofia Brenner, Annette Lutz, and Lena Volk. Symmetry Classes of Hamiltonian Cycles. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 15:1-15:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{baligacs_et_al:LIPIcs.MFCS.2025.15,
  author =	{Balig\'{a}cs, J\'{u}lia and Brenner, Sofia and Lutz, Annette and Volk, Lena},
  title =	{{Symmetry Classes of Hamiltonian Cycles}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{15:1--15:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.15},
  URN =		{urn:nbn:de:0030-drops-241221},
  doi =		{10.4230/LIPIcs.MFCS.2025.15},
  annote =	{Keywords: Hamiltonian cycles, graph automorphisms, Cayley graphs, abelian groups, Cartesian product of graphs}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.73
Counting Locally Optimal Tours in the TSP

Authors: Bodo Manthey and Jesse van Rhijn

Published in: LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)

Abstract
We show that the problem of counting 2-optimal tours in instances of the Travelling Salesperson Problem (TSP) on complete graphs is #P-complete. In addition, we show that the expected number of 2-optimal tours in random instances of the TSP on complete graphs is O(1.2098ⁿ √{n!}). Based on numerical experiments, we conjecture that the true bound is at most O(√{n!}), which is approximately the square root of the total number of tours.
Cite as

Bodo Manthey and Jesse van Rhijn. Counting Locally Optimal Tours in the TSP. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 73:1-73:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{manthey_et_al:LIPIcs.MFCS.2025.73,
  author =	{Manthey, Bodo and van Rhijn, Jesse},
  title =	{{Counting Locally Optimal Tours in the TSP}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{73:1--73:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-388-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{345},
  editor =	{Gawrychowski, Pawe{\l} and Mazowiecki, Filip and Skrzypczak, Micha{\l}},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.73},
  URN =		{urn:nbn:de:0030-drops-241807},
  doi =		{10.4230/LIPIcs.MFCS.2025.73},
  annote =	{Keywords: Travelling salesman problem, probabilistic analysis, local search, heuristics, 2-opt}
}
Document
DOI: 10.4230/LIPIcs.CP.2025.32
BFS-Based Canonical Codes for Generating Graphs with Constraint Programming

Authors: Xiao Peng and Christine Solnon

Published in: LIPIcs, Volume 340, 31st International Conference on Principles and Practice of Constraint Programming (CP 2025)

Abstract
We consider the problem of generating all graphs that satisfy some given additional constraints (on vertex degrees, or cycle lengths, for example). Most previous works have proposed to generate canonical codes associated with adjacency matrices. In this paper, we consider canonical codes based on Breadth First Search (BFS), and we show how to generate them with Constraint Programming (CP): we introduce a set of basic constraints that must be satisfied by all canonical codes, thus breaking many symmetries, and we introduce a global constraint to break other symmetries. We illustrate the interest of our approach on connected claw-free cubic graphs, and show that it outperforms state-of-the-art CP and SAT Modulo Theory (SMT) approaches.
Cite as

Xiao Peng and Christine Solnon. BFS-Based Canonical Codes for Generating Graphs with Constraint Programming. In 31st International Conference on Principles and Practice of Constraint Programming (CP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 340, pp. 32:1-32:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{peng_et_al:LIPIcs.CP.2025.32,
  author =	{Peng, Xiao and Solnon, Christine},
  title =	{{BFS-Based Canonical Codes for Generating Graphs with Constraint Programming}},
  booktitle =	{31st International Conference on Principles and Practice of Constraint Programming (CP 2025)},
  pages =	{32:1--32:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-380-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{340},
  editor =	{de la Banda, Maria Garcia},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2025.32},
  URN =		{urn:nbn:de:0030-drops-238935},
  doi =		{10.4230/LIPIcs.CP.2025.32},
  annote =	{Keywords: Graph Generation, Automorphisms, Symmetry Breaking}
}
Document
DOI: 10.4230/LIPIcs.SEA.2025.16
Exact Lower Bounds for the Number of Comparisons in Selection

Authors: Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober

Published in: LIPIcs, Volume 338, 23rd International Symposium on Experimental Algorithms (SEA 2025)

Abstract
Selection is the problem of finding the i-th smallest element among n elements. We apply computer search to find optimal algorithms for small instances of the selection problem. Using new algorithmic ideas, we establish tighter lower bounds for the number of comparisons required, denoted as V_i(n). Our results include optimal algorithms for n up to 15 and arbitrary i, and for n = 16 when i ≤ 6. We determine the precise values V₇(14) = 25, V₆(15) = V₇(15) = 26, and V₈(15) = 27, where previously, only a range was known.
Cite as

Josua Dörrer, Konrad Gendle, Johanna Betz, Julius von Smercek, Andreas Steding, and Florian Stober. Exact Lower Bounds for the Number of Comparisons in Selection. In 23rd International Symposium on Experimental Algorithms (SEA 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 338, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{dorrer_et_al:LIPIcs.SEA.2025.16,
  author =	{D\"{o}rrer, Josua and Gendle, Konrad and Betz, Johanna and von Smercek, Julius and Steding, Andreas and Stober, Florian},
  title =	{{Exact Lower Bounds for the Number of Comparisons in Selection}},
  booktitle =	{23rd International Symposium on Experimental Algorithms (SEA 2025)},
  pages =	{16:1--16:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-375-1},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{338},
  editor =	{Mutzel, Petra and Prezza, Nicola},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2025.16},
  URN =		{urn:nbn:de:0030-drops-232547},
  doi =		{10.4230/LIPIcs.SEA.2025.16},
  annote =	{Keywords: selection, lower bounds, exhaustive computer search}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.82
(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs

Authors: Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi

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

Abstract
Research of cycles through specific vertices is a central topic in graph theory. In this context, we focus on a well-studied computational problem, T-Cycle: given an undirected n-vertex graph G and a set of k vertices T ⊆ V(G) termed terminals, the objective is to determine whether G contains a simple cycle C through all the terminals. Our contribution is twofold: (i) We provide a 2^{O(√klog k)}⋅ n-time fixed-parameter deterministic algorithm for T-Cycle on planar graphs; (ii) We provide a k^{O(1)}⋅ n-time deterministic kernelization algorithm for T-Cycle on planar graphs where the produced instance is of size klog^{O(1)}k. Both of our algorithms are optimal in terms of both k and n up to (poly)logarithmic factors in k under the ETH. In fact, our algorithms are the first subexponential-time fixed-parameter algorithm for T-Cycle on planar graphs, as well as the first polynomial kernel for T-Cycle on planar graphs. This substantially improves upon/expands the known literature on the parameterized complexity of the problem.
Cite as

Harmender Gahlawat, Abhishek Rathod, and Meirav Zehavi. (Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 82:1-82:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{gahlawat_et_al:LIPIcs.ICALP.2025.82,
  author =	{Gahlawat, Harmender and Rathod, Abhishek and Zehavi, Meirav},
  title =	{{(Almost-)Optimal FPT Algorithm and Kernel for T-Cycle on Planar Graphs}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{82:1--82: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.82},
  URN =		{urn:nbn:de:0030-drops-234593},
  doi =		{10.4230/LIPIcs.ICALP.2025.82},
  annote =	{Keywords: FPT Algorithms, Kernelization, T-Cycle, Subexponential Algorithmms}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.70
Tiling Random Regular Graphs Efficiently

Authors: Sahar Diskin, Ilay Hoshen, and Maksim Zhukovskii

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

Abstract
We show that for every ε > 0 there exists a sufficiently large d₀ ∈ ℕ such that for every d ≥ d₀, whp the random d-regular graph G(n,d) contains a T-factor for every tree T on at most (1-ε)d/log d vertices. This is best possible since, for large enough integer d, whp G(n,d) does not contain a ((1+ε)d)/(log d)-star-factor. Our method gives a randomised algorithm which whp finds said T-factor and whose expected running time is O(n^{1+o(1)}), as well as an efficient deterministic counterpart.
Cite as

Sahar Diskin, Ilay Hoshen, and Maksim Zhukovskii. Tiling Random Regular Graphs Efficiently. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 70:1-70:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{diskin_et_al:LIPIcs.ICALP.2025.70,
  author =	{Diskin, Sahar and Hoshen, Ilay and Zhukovskii, Maksim},
  title =	{{Tiling Random Regular Graphs Efficiently}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{70:1--70:17},
  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.70},
  URN =		{urn:nbn:de:0030-drops-234477},
  doi =		{10.4230/LIPIcs.ICALP.2025.70},
  annote =	{Keywords: Random regular graphs, Tree tilings}
}
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
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.73
The Iteration Number of Colour Refinement

Authors: Sandra Kiefer and Brendan D. McKay

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The Colour Refinement procedure and its generalisation to higher dimensions, the Weisfeiler-Leman algorithm, are central subroutines in approaches to the graph isomorphism problem. In an iterative fashion, Colour Refinement computes a colouring of the vertices of its input graph. A trivial upper bound on the iteration number of Colour Refinement on graphs of order n is n-1. We show that this bound is tight. More precisely, we prove via explicit constructions that there are infinitely many graphs G on which Colour Refinement takes |G|-1 iterations to stabilise. Modifying the infinite families that we present, we show that for every natural number n ≥ 10, there are graphs on n vertices on which Colour Refinement requires at least n-2 iterations to reach stabilisation.
Cite as

Sandra Kiefer and Brendan D. McKay. The Iteration Number of Colour Refinement. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 73:1-73:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kiefer_et_al:LIPIcs.ICALP.2020.73,
  author =	{Kiefer, Sandra and McKay, Brendan D.},
  title =	{{The Iteration Number of Colour Refinement}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{73:1--73:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.73},
  URN =		{urn:nbn:de:0030-drops-124801},
  doi =		{10.4230/LIPIcs.ICALP.2020.73},
  annote =	{Keywords: Colour Refinement, iteration number, Weisfeiler-Leman algorithm, quantifier depth}
}
  • Refine by Type
  • 14 Document/PDF
  • 13 Document/HTML

  • Refine by Publication Year
  • 3 2026
  • 10 2025
  • 1 2020

  • Refine by Author
  • 2 Kiefer, Sandra
  • 1 Asilis, Julian
  • 1 Baligács, Júlia
  • 1 Bekos, Michael A.
  • 1 Betz, Johanna
  • Show More...

  • Refine by Series/Journal
  • 14 LIPIcs

  • Refine by Classification
  • 5 Mathematics of computing → Graph theory
  • 3 Mathematics of computing → Combinatorial algorithms
  • 3 Mathematics of computing → Combinatorics
  • 2 Mathematics of computing → Graph algorithms
  • 2 Mathematics of computing → Random graphs
  • Show More...

  • Refine by Keyword
  • 3 Weisfeiler-Leman algorithm
  • 2 Colour Refinement
  • 2 quantifier depth
  • 1 1-planar graph
  • 1 2-opt
  • 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