Author name cluster

Oleg Verbitsky

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

9 papers

1 author row

TCS Journal 2025 Journal Article

On the expressibility of the reconstructional color refinement

V. Arvind
Johannes Köbler
Oleg Verbitsky

In this note we explore the color refinement procedure — also known as the 1-dimensional Weisfeiler-Leman procedure, well-studied in connection with the Graph Isomorphism problem — in the context of the Graph Reconstruction conjecture of Ulam. A basic fact about the Ulam reconstruction conjecture is that the connectedness of a graph is determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness of a graph can even be determined from the deck of its vertex-deleted subgraphs given only by their stable colorings (i. e. , up to equivalence under color refinement). It follows as a consequence that connectedness is recognizable by Reconstruction Graph Neural Networks, which is a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).

Details DOI

I&C Journal 2022 Journal Article

On the Weisfeiler-Leman dimension of fractional packing

V. Arvind
Frank Fuhlbrück
Johannes Köbler
Oleg Verbitsky

The k-dimensional Weisfeiler-Leman procedure ( k - WL ), which colors k-tuples of vertices in rounds based on the neighborhood structure in the graph, has proven to be immensely fruitful in the algorithmic study of Graph Isomorphism. More generally, it is of fundamental importance in understanding and exploiting symmetries in graphs in various settings. Two graphs are k - WL -equivalent if the k-dimensional Weisfeiler-Leman procedure produces the same final coloring on both graphs. 1 - WL -equivalence is known as fractional isomorphism of graphs, and the k - WL -equivalence relation becomes finer as k increases. We investigate to what extent standard graph parameters are preserved by k - WL -equivalence, focusing on fractional graph packing numbers. The integral packing numbers are typically NP-hard to compute, and we discuss applicability of k - WL -invariance for estimating the integrality gap of the LP relaxation provided by their fractional counterparts.

Details DOI

TCS Journal 2021 Journal Article

The Weisfeiler-Leman algorithm and recognition of graph properties

Frank Fuhlbrück
Johannes Köbler
Ilia Ponomarenko
Oleg Verbitsky

The k-dimensional Weisfeiler-Leman algorithm ( k - WL ) is a very useful combinatorial tool in graph isomorphism testing. We address the applicability of k - WL to recognition of graph properties. Let G be an input graph with n vertices. We show that, if n is prime, then vertex-transitivity of G can be seen in a straightforward way from the output of 2 - WL on G and on the vertex-individualized copies of G. This is perhaps the first non-trivial example of using the Weisfeiler-Leman algorithm for recognition of a natural graph property rather than for isomorphism testing. On the other hand, we show that, if n is divisible by 16, then k - WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with n vertices unless k = Ω ( n ). Similar results are obtained for recognition of arc-transitivity. Our lower bounds are based on an analysis of the Cai-Fürer-Immerman construction, which might be of independent interest. In particular, we provide sufficient conditions under which the Cai-Fürer-Immerman graphs can be made colorless.

Details DOI

Highlights Conference 2018 Conference Abstract

On the First-Order Complexity of Subgraph Isomorphism

Oleg Verbitsky

ABSTRACT. Let F be a fixed pattern graph with k vertices. The Subgraph Isomorphism problem asks whether a given host graph G contains a subgraph isomorphic to F. In the induced version of the problem, the question is whether G has an induced copy of F. Each of the two problems can be expressed by a first-order sentence of quantifier depth k. We investigate the question whether this can be done more succinctly with respect to the quantifier depth and the variable width. A more detailed 2-page abstract is uploaded as a pdf file. This is joint work with Maksim Zhukovskii.

Details

I&C Journal 2016 Journal Article

On the isomorphism problem for Helly circular-arc graphs

Johannes Köbler
Sebastian Kuhnert
Oleg Verbitsky

The isomorphism problem is known to be efficiently solvable for interval graphs, while for the larger class of circular-arc graphs its complexity status stays open. We consider the intermediate class of intersection graphs for families of circular arcs that satisfy the Helly property. We solve the isomorphism problem for this class in logarithmic space. If an input graph has a Helly circular-arc model, then our algorithm constructs it canonically, which means that the models constructed for isomorphic graphs are equal.

Details DOI

Highlights Conference 2013 Conference Abstract

Bounds for the quantifier depth in two-variable logics

Oleg Verbitsky

Given structures $G$ and $H$ and a first-order formula $F$ over the same vocabulary, we say that $F$ distinguishes $G$ from $H$ if $F$ is true on $G$ but false on $H$. By alternation depth of $F$ we mean the maximum length of a sequence of nested alternating quantifiers in $F$. Obviously, this parameter is bounded from above by the quantifier depth of $F$. We will examine the maximum alternation depth and quantifier depth needed to distinguish two structures in two-variable first-order logic and its fragments. Lower bounds for the quantifier depth in the existential-positive fragment have applications to analysis of the computational complexity of Arc Consistency testing, one of the most popular heuristics for the constraint satisfaction problem.

PDF Details

TCS Journal 2008 Journal Article

On the obfuscation complexity of planar graphs

Oleg Verbitsky

Being motivated by John Tantalo’s Planarity Game, we consider straight line plane drawings of a planar graph G with edge crossings and wonder how obfuscated such drawings can be. We define obf ( G ), the obfuscation complexity of G, to be the maximum number of edge crossings in a drawing of G. Relating obf ( G ) to the distribution of vertex degrees in G, we show an efficient way of constructing a drawing of G with at least obf ( G ) / 3 edge crossings. We prove bounds ( δ ( G ) 2 / 24 − o ( 1 ) ) n 2 ≤ obf ( G ) < 3 n 2 for an n -vertex planar graph G with minimum vertex degree δ ( G ) ≥ 2. The shift complexity of G, denoted by shift ( G ), is the minimum number of vertex shifts sufficient to eliminate all edge crossings in an arbitrarily obfuscated drawing of G (after shifting a vertex, all incident edges are supposed to be redrawn correspondingly). If δ ( G ) ≥ 3, then shift ( G ) is linear in the number of vertices due to the known fact that the matching number of G is linear. However, in the case δ ( G ) ≥ 2 we notice that shift ( G ) can be linear even if the matching number is bounded. As for computational complexity, we show that, given a drawing D of a planar graph, it is NP-hard to find an optimum sequence of shifts making D crossing-free.

Details DOI

TCS Journal 2005 Journal Article

The first order definability of graphs with separators via the Ehrenfeucht game

Oleg Verbitsky

We say that a first order formula Φ defines a graph G if Φ is true on G and false on every graph G ′ non-isomorphic with G. Let D ( G ) be the minimum quantifier rank of a such formula. We prove that, if G is a tree of bounded degree or a Hamiltonian (equivalently, 2-connected) outerplanar graph, then D ( G ) = O ( log n ), where n denotes the order of G. This bound is optimal up to a constant factor. If h is a constant, for connected graphs with no minor K h and degree O ( n / log n ), we prove the bound D ( G ) = O ( n ). This result applies to planar graphs and, more generally, to graphs of bounded genus. Our proof techniques are based on the characterization of the quantifier rank as the length of the Ehrenfeucht game on non-isomorphic graphs. We use the separator theorems to design a winning strategy for Spoiler in this game.

Details DOI

TCS Journal 1996 Journal Article

Towards the parallel repetition conjecture

Oleg Verbitsky

We consider the behavior of the error probability of a two-prover one-round interactive protocol repeated n times in parallel. We point out the connection of this problem with the density form of the Hales-Jewett theorem in Ramsey theory. This allows us to show that the error probability converges to 0 as n → ∞.

Details DOI