12 Search Results for "Verbitsky, Oleg"

Document
DOI: 10.4230/LIPIcs.GD.2025.29
Stabbing Faces by a Convex Curve

Authors: David Eppstein

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

Abstract
We prove that, for every plane graph G and every smooth convex curve C not on a single line, there exists a straight-line drawing of G for which every face is crossed by C.
Cite as

David Eppstein. Stabbing Faces by a Convex Curve. In 33rd International Symposium on Graph Drawing and Network Visualization (GD 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 357, pp. 29:1-29:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eppstein:LIPIcs.GD.2025.29,
  author =	{Eppstein, David},
  title =	{{Stabbing Faces by a Convex Curve}},
  booktitle =	{33rd International Symposium on Graph Drawing and Network Visualization (GD 2025)},
  pages =	{29:1--29:8},
  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.29},
  URN =		{urn:nbn:de:0030-drops-250155},
  doi =		{10.4230/LIPIcs.GD.2025.29},
  annote =	{Keywords: planar graphs, convex curves, stabbing, transversal}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2025.88
Color Refinement for Relational Structures

Authors: Benjamin Scheidt and Nicole Schweikardt

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

Abstract
Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is traditionally used as an imperfect way to test for isomorphism, the algorithm has permeated many other, seemingly unrelated, areas of computer science. The method is algorithmically simple, and it has a well-understood distinguishing power: it has been logically characterized by Immerman and Lander (1990) and Cai, Fürer, Immerman (1992), who showed that it distinguishes precisely those graphs that can be distinguished by a sentence of first-order logic with counting quantifiers and only two variables. A combinatorial characterization was given by Dvořák (2010), who showed that it distinguishes precisely those graphs that differ in the number of homomorphisms from some tree. In this paper, we introduce Relational Color Refinement (RCR, for short), a generalization of the Color Refinement method from graphs to arbitrary relational structures, whose distinguishing power admits the equivalent combinatorial and logical characterizations as Color Refinement has on graphs: we show that RCR distinguishes precisely those structures that differ in the number of homomorphisms from an acyclic connected relational structure. Further, we show that RCR distinguishes precisely those structures that are distinguished by a sentence of the guarded fragment of first-order logic with counting quantifiers. Additionally, we show that for every fixed finite relational signature, RCR can be implemented to run on structures of that signature in time O(N⋅log N), where N denotes the number of tuples present in the structure.
Cite as

Benjamin Scheidt and Nicole Schweikardt. Color Refinement for Relational Structures. In 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 345, pp. 88:1-88:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{scheidt_et_al:LIPIcs.MFCS.2025.88,
  author =	{Scheidt, Benjamin and Schweikardt, Nicole},
  title =	{{Color Refinement for Relational Structures}},
  booktitle =	{50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025)},
  pages =	{88:1--88:19},
  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.88},
  URN =		{urn:nbn:de:0030-drops-241958},
  doi =		{10.4230/LIPIcs.MFCS.2025.88},
  annote =	{Keywords: color refinement, counting logics, homomorphism counts, homomorphism indistinguishability, guarded logics, pebble games, relational structures, alpha-acyclicity, join-trees}
}
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.STACS.2025.75
Canonical Labeling of Sparse Random Graphs

Authors: Oleg Verbitsky and Maksim Zhukovskii

Published in: LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)

Abstract
We show that if p = O(1/n), then the Erdős-Rényi random graph G(n,p) with high probability admits a canonical labeling computable in time O(nlog n). Combined with the previous results on the canonization of random graphs, this implies that G(n,p) with high probability admits a polynomial-time canonical labeling whatever the edge probability function p. Our algorithm combines the standard color refinement routine with simple post-processing based on the classical linear-time tree canonization. Noteworthy, our analysis of how well color refinement performs in this setting allows us to complete the description of the automorphism group of the 2-core of G(n,p).
Cite as

Oleg Verbitsky and Maksim Zhukovskii. Canonical Labeling of Sparse Random Graphs. In 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 327, pp. 75:1-75:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{verbitsky_et_al:LIPIcs.STACS.2025.75,
  author =	{Verbitsky, Oleg and Zhukovskii, Maksim},
  title =	{{Canonical Labeling of Sparse Random Graphs}},
  booktitle =	{42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025)},
  pages =	{75:1--75:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-365-2},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{327},
  editor =	{Beyersdorff, Olaf and Pilipczuk, Micha{\l} and Pimentel, Elaine and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.75},
  URN =		{urn:nbn:de:0030-drops-229003},
  doi =		{10.4230/LIPIcs.STACS.2025.75},
  annote =	{Keywords: Graph isomorphism, random graphs, canonical labeling, color refinement}
}
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.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.ESA.2023.100
Canonization of a Random Graph by Two Matrix-Vector Multiplications

Authors: Oleg Verbitsky and Maksim Zhukovskii

Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)

Abstract
We show that a canonical labeling of a random n-vertex graph can be obtained by assigning to each vertex x the triple (w₁(x),w₂(x),w₃(x)), where w_k(x) is the number of walks of length k starting from x. This takes time 𝒪(n²), where n² is the input size, by using just two matrix-vector multiplications. The linear-time canonization of a random graph is the classical result of Babai, Erdős, and Selkow. For this purpose they use the well-known combinatorial color refinement procedure, and we make a comparative analysis of the two algorithmic approaches.
Cite as

Oleg Verbitsky and Maksim Zhukovskii. Canonization of a Random Graph by Two Matrix-Vector Multiplications. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 100:1-100:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{verbitsky_et_al:LIPIcs.ESA.2023.100,
  author =	{Verbitsky, Oleg and Zhukovskii, Maksim},
  title =	{{Canonization of a Random Graph by Two Matrix-Vector Multiplications}},
  booktitle =	{31st Annual European Symposium on Algorithms (ESA 2023)},
  pages =	{100:1--100:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-295-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{274},
  editor =	{G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2023.100},
  URN =		{urn:nbn:de:0030-drops-187536},
  doi =		{10.4230/LIPIcs.ESA.2023.100},
  annote =	{Keywords: Graph Isomorphism, canonical labeling, random graphs, walk matrix, color refinement, linear time}
}
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.CSL.2017.40
On the First-Order Complexity of Induced Subgraph Isomorphism

Authors: Oleg Verbitsky and Maksim Zhukovskii

Published in: LIPIcs, Volume 82, 26th EACSL Annual Conference on Computer Science Logic (CSL 2017)

Abstract
Given a graph F, let I(F) be the class of graphs containing F as an induced subgraph. Let W[F] denote the minimum k such that I(F) is definable in k-variable first-order logic. The recognition problem of I(F), known as Induced Subgraph Isomorphism (for the pattern graph F), is solvable in time O(n^{W[F]}). Motivated by this fact, we are interested in determining or estimating the value of W[F]. Using Olariu's characterization of paw-free graphs, we show that I(K_3+e) is definable by a first-order sentence of quantifier depth 3, where K_3+e denotes the paw graph. This provides an example of a graph F with W[F] strictly less than the number of vertices in F. On the other hand, we prove that W[F]=4 for all F on 4 vertices except the paw graph and its complement. If F is a graph on t vertices, we prove a general lower bound W[F]>(1/2-o(1))t, where the function in the little-o notation approaches 0 as t increases. This bound holds true even for a related parameter W^*[F], which is defined as the minimum k such that I(F) is definable in the k-variable infinitary logic. We show that W^*[F] can be strictly less than W[F]. Specifically, W^*[P_4]=3 for P_4 being the path graph on 4 vertices.
Cite as

Oleg Verbitsky and Maksim Zhukovskii. On the First-Order Complexity of Induced Subgraph Isomorphism. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 82, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{verbitsky_et_al:LIPIcs.CSL.2017.40,
  author =	{Verbitsky, Oleg and Zhukovskii, Maksim},
  title =	{{On the First-Order Complexity of Induced Subgraph Isomorphism}},
  booktitle =	{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-045-3},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{82},
  editor =	{Goranko, Valentin and Dam, Mads},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2017.40},
  URN =		{urn:nbn:de:0030-drops-76841},
  doi =		{10.4230/LIPIcs.CSL.2017.40},
  annote =	{Keywords: the induced subgraph isomorphism problem, descriptive and computational complexity, finite-variable first-order logic, quantifier depth and variable w}
}
Document
DOI: 10.4230/LIPIcs.CSL.2013.61
Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy

Authors: Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky

Published in: LIPIcs, Volume 23, Computer Science Logic 2013 (CSL 2013)

Abstract
Given two structures G and H distinguishable in FO^k (first-order logic with k variables), let A^k(G,H) denote the minimum alternation depth of a FO^k formula distinguishing G from H. Let A^k(n) be the maximum value of A^k(G,H) over n-element structures. We prove the strictness of the quantifier alternation hierarchy of FO^2 in a strong quantitative form, namely A^2(n) >= n/8-2, which is tight up to a constant factor. For each k >= 2, it holds that A^k(n) > log_(k+1) n-2 even over colored trees, which is also tight up to a constant factor if k >= 3. For k >= 3 the last lower bound holds also over uncolored trees, while the alternation hierarchy of FO^2 collapses even over all uncolored graphs. We also show examples of colored graphs G and H on n vertices that can be distinguished in FO^2 much more succinctly if the alternation number is increased just by one: while in Sigma_i it is possible to distinguish G from H with bounded quantifier depth, in Pi_i this requires quantifier depth Omega(n2). The quadratic lower bound is best possible here because, if G and H can be distinguished in FO^k with i quantifier alternations, this can be done with quantifier depth n^(2k-2).
Cite as

Christoph Berkholz, Andreas Krebs, and Oleg Verbitsky. Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy. In Computer Science Logic 2013 (CSL 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 23, pp. 61-80, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{berkholz_et_al:LIPIcs.CSL.2013.61,
  author =	{Berkholz, Christoph and Krebs, Andreas and Verbitsky, Oleg},
  title =	{{Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy}},
  booktitle =	{Computer Science Logic 2013 (CSL 2013)},
  pages =	{61--80},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-60-6},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{23},
  editor =	{Ronchi Della Rocca, Simona},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2013.61},
  URN =		{urn:nbn:de:0030-drops-41907},
  doi =		{10.4230/LIPIcs.CSL.2013.61},
  annote =	{Keywords: Alternation hierarchy, finite-variable logic}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2012.387
Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace

Authors: Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky

Published in: LIPIcs, Volume 18, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)

Abstract
We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where canonical means that isomorphic graphs receive identical models. This implies that the recognition and the isomorphism problems for these graphs are solvable in logspace. For the broader class of concave-round graphs, which still possess (not necessarily proper) circular-arc models, we show that a canonical circular-arc model can also be constructed in logspace. As a building block for these results, we design a logspace algorithm for computing canonical circular-arc models of circular-arc hypergraphs; this important class of hypergraphs corresponds to matrices with the circular ones property. Furthermore, we consider the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We show that this problem is solvable in logarithmic space for the classes of proper circular-arc, concave-round, and co-convex graphs.
Cite as

Johannes Köbler, Sebastian Kuhnert, and Oleg Verbitsky. Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 18, pp. 387-399, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2012)

Copy BibTex To Clipboard

@InProceedings{kobler_et_al:LIPIcs.FSTTCS.2012.387,
  author =	{K\"{o}bler, Johannes and Kuhnert, Sebastian and Verbitsky, Oleg},
  title =	{{Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Logspace}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012)},
  pages =	{387--399},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-47-7},
  ISSN =	{1868-8969},
  year =	{2012},
  volume =	{18},
  editor =	{D'Souza, Deepak and Radhakrishnan, Jaikumar and Telikepalli, Kavitha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2012.387},
  URN =		{urn:nbn:de:0030-drops-38757},
  doi =		{10.4230/LIPIcs.FSTTCS.2012.387},
  annote =	{Keywords: Proper circular-arc graphs, graph isomorphism, canonization, circular ones property, logspace complexity}
}
  • Refine by Type
  • 12 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 6 2025
  • 1 2024
  • 1 2023
  • 1 2020
  • 1 2017
  • Show More...

  • Refine by Author
  • 7 Verbitsky, Oleg
  • 3 Köbler, Johannes
  • 3 Schweitzer, Pascal
  • 3 Zhukovskii, Maksim
  • 2 Fuhlbrück, Frank
  • Show More...

  • Refine by Series/Journal
  • 12 LIPIcs

  • Refine by Classification
  • 4 Mathematics of computing → Graph algorithms
  • 3 Theory of computation → Graph algorithms analysis
  • 2 Mathematics of computing → Graph theory
  • 2 Mathematics of computing → Random graphs
  • 2 Theory of computation → Complexity theory and logic
  • Show More...

  • Refine by Keyword
  • 3 Graph Isomorphism
  • 3 color refinement
  • 2 Weisfeiler-Leman algorithm
  • 2 canonical labeling
  • 2 coherent configurations
  • 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