Source author record

Oleg Verbitsky

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Computational Complexity math.CO Discrete Mathematics Logic in Computer Science Computational Geometry math.LO Artificial Intelligence Distributed, Parallel, and Cluster Computing

Catalog footprint

Research overview

19works

8topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

As it is well known, 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 much 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 graphs of color multiplicity 4 with directed and 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_3)$ -configurations in incidence geometry.

preprint2020arXiv

Local WL Invariance and Hidden Shades of Regularity

The $k$ -dimensional Weisfeiler-Leman algorithm is a powerful tool in graph isomorphism testing. For an input graph $G$ , the algorithm determines a canonical coloring of $s$ -tuples of vertices of $G$ for each $s$ between 1 and $k$ . We say that a numerical parameter of $s$ -tuples is $k$ -WL-invariant if it is determined by the tuple color. As an application of Dvořák's result on $k$ -WL-invariance of homomorphism counts, we spot some non-obvious regularity properties of strongly regular graphs and related graph families. For example, if $G$ is a strongly regular graph, then the number of paths of length 6 between vertices $x$ and $y$ in $G$ depends only on whether or not $x$ and $y$ are adjacent (and the length 6 is here optimal). Or, the number of cycles of length 7 passing through a vertex $x$ in $G$ is the same for every $x$ (where the length 7 is also optimal).

preprint2020arXiv

On the Weisfeiler-Leman Dimension of Fractional Packing

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.

preprint2020arXiv

The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

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$ . However, if $n$ is divisible by 16, then $k$ -WL is unable to distinguish between vertex-transitive and non-vertex-transitive graphs with $n$ vertices as long as $k=o(\sqrt n)$ . Similar results are obtained for recognition of arc-transitivity.

preprint2016arXiv

Drawing Graphs on Few Lines and Few Planes

We investigate the problem of drawing graphs in 2D and 3D such that their edges (or only their vertices) can be covered by few lines or planes. We insist on straight-line edges and crossing-free drawings. This problem has many connections to other challenging graph-drawing problems such as small-area or small-volume drawings, layered or track drawings, and drawing graphs with low visual complexity. While some facts about our problem are implicit in previous work, this is the first treatment of the problem in its full generality. Our contribution is as follows. We show lower and upper bounds for the numbers of lines and planes needed for covering drawings of graphs in certain graph classes. In some cases our bounds are asymptotically tight; in some cases we are able to determine exact values. We relate our parameters to standard combinatorial characteristics of graphs (such as the chromatic number, treewidth, maximum degree, or arboricity) and to parameters that have been studied in graph drawing (such as the track number or the number of segments appearing in a drawing). We pay special attention to planar graphs. For example, we show that there are planar graphs that can be drawn in 3-space on a lot fewer lines than in the plane.

preprint2015arXiv

Graph Isomorphism, Color Refinement, and Compactness

Color refinement is a classical technique used to show that two given graphs G and H are non-isomorphic; it is very efficient, although it does not succeed on all graphs. We call a graph G amenable to color refinement if it succeeds in distinguishing G from any non-isomorphic graph H. Tinhofer (1991) explored a linear programming approach to Graph Isomorphism and defined compact graphs: A graph is compact if its fractional automorphisms polytope is integral. Tinhofer noted that isomorphism testing for compact graphs can be done quite efficiently by linear programming. However, the problem of characterizing and recognizing compact graphs in polynomial time remains an open question. Our results are summarized below: - We show that amenable graphs are recognizable in time O((n + m)logn), where n and m denote the number of vertices and the number of edges in the input graph. - We show that all amenable graphs are compact. - We study related combinatorial and algebraic graph properties introduced by Tinhofer and Godsil. The corresponding classes of graphs form a hierarchy and we prove that recognizing each of these graph classes is P-hard. In particular, this gives a first complexity lower bound for recognizing compact graphs.

preprint2015arXiv

Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth

Given a connected graph $G$ and its vertex $x$ , let $U_x(G)$ denote the universal cover of $G$ obtained by unfolding $G$ into a tree starting from $x$ . Let $T=T(n)$ be the minimum number such that, for graphs $G$ and $H$ with at most $n$ vertices each, the isomorphism of $U_x(G)$ and $U_y(H)$ surely follows from the isomorphism of these rooted trees truncated at depth $T$ . Motivated by applications in theory of distributed computing, Norris [Discrete Appl. Math. 1995] asks if $T(n)\le n$ . We answer this question in the negative by establishing that $T(n)=(2-o(1))n$ . Our solution uses basic tools of finite model theory such as a bisimulation version of the Immerman-Lander 2-pebble counting game. The graphs $G_n$ and $H_n$ we construct to prove the lower bound for $T(n)$ also show some other tight lower bounds. Both having $n$ vertices, $G_n$ and $H_n$ can be distinguished in 2-variable counting logic only with quantifier depth $(1-o(1))n$ . It follows that color refinement, the classical procedure used in isomorphism testing and other areas for computing the coarsest equitable partition of a graph, needs $(1-o(1))n$ rounds to achieve color stabilization on each of $G_n$ and $H_n$ . Somewhat surprisingly, this number of rounds is not enough for color stabilization on the disjoint union of $G_n$ and $H_n$ , where $(2-o(1))n$ rounds are needed.

preprint2014arXiv

On the dynamic width of the 3-colorability problem

A graph $G$ is 3-colorable if and only if it maps homomorphically to the complete 3-vertex graph $K_3$ . The last condition can be checked by a $k$ -consistency algorithm where the parameter $k$ has to be chosen large enough, dependent on $G$ . Let $W(G)$ denote the minimum $k$ sufficient for this purpose. For a non-3-colorable graph $G$ , $W(G)$ is equal to the minimum $k$ such that $G$ can be distinguished from $K_3$ in the $k$ -variable existential-positive first-order logic. We define the dynamic width of the 3-colorability problem as the function $W(n)=\max_G W(G)$ , where the maximum is taken over all non-3-colorable $G$ with $n$ vertices. The assumption $\mathrm{NP}\ne\mathrm{P}$ implies that $W(n)$ is unbounded. Indeed, a lower bound $W(n)=Ω(\log\log n/\log\log\log n)$ follows unconditionally from the work of Nesetril and Zhu on bounded treewidth duality. The Exponential Time Hypothesis implies a much stronger bound $W(n)=Ω(n/\log n)$ and indeed we unconditionally prove that $W(n)=Ω(n)$ . In fact, an even stronger statement is true: A first-order sentence distinguishing any 3-colorable graph on $n$ vertices from any non-3-colorable graph on $n$ vertices must have $Ω(n)$ variables. On the other hand, we observe that $W(G)\le 3\,α(G)+1$ and $W(G)\le n-α(G)+1$ for every non-3-colorable graph $G$ with $n$ vertices, where $α(G)$ denotes the independence number of $G$ . This implies that $W(n)\le\frac34\,n+1$ , improving on the trivial upper bound $W(n)\le n$ . We also show that $W(G)>\frac1{16}\, g(G)$ for every non-3-colorable graph $G$ , where $g(G)$ denotes the girth of $G$ . Finally, we consider the function $W(n)$ over planar graphs and prove that $W(n)=Θ(\sqrt n)$ in the case.

preprint2013arXiv

Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy

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)\ge n/8-2$ , which is tight up to a constant factor. For each $k\ge2$ , 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\ge3$ . For $k\ge 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 $Σ_{i}$ it is possible to distinguish $G$ from $H$ with bounded quantifier depth, in $Π_{i}$ this requires quantifier depth $Ω(n^2)$ . 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}$ .

preprint2013arXiv

Circular-arc hypergraphs: Rigidity via Connectedness

A circular-arc hypergraph $H$ is a hypergraph admitting an arc ordering, that is, a circular ordering of the vertex set $V(H)$ such that every hyperedge is an arc of consecutive vertices. An arc ordering is tight if, for any two hyperedges $A$ and $B$ such that $A$ is a nonempty subset of $B$ and $B$ is not equal to $V(H)$ , the corresponding arcs share a common endpoint. We give sufficient conditions for $H$ to have, up to reversing, a unique arc ordering and a unique tight arc ordering. These conditions are stated in terms of connectedness properties of $H$ . It is known that $G$ is a proper circular-arc graph exactly when its closed neighborhood hypergraph $N[G]$ admits a tight arc ordering. We explore connectedness properties of $N[G]$ and prove that, if $G$ is a connected, twin-free, proper circular-arc graph with non-bipartite complement, then $N[G]$ has, up to reversing, a unique arc ordering. If the complement of $G$ is bipartite and connected, then $N[G]$ has, up to reversing, two tight arc orderings. As a corollary, we notice that in both of the two cases $G$ has an essentially unique intersection representation. The last result also follows from the work by Deng, Hell, and Huang based on a theory of local tournaments.

preprint2013arXiv

Logical complexity of graphs: a survey

We discuss the definability of finite graphs in first-order logic with two relation symbols for adjacency and equality of vertices. The logical depth $D(G)$ of a graph $G$ is equal to the minimum quantifier depth of a sentence defining $G$ up to isomorphism. The logical width $W(G)$ is the minimum number of variables occurring in such a sentence. The logical length $L(G)$ is the length of a shortest defining sentence. We survey known estimates for these graph parameters and discuss their relations to other topics (such as the efficiency of the Weisfeiler-Lehman algorithm in isomorphism testing, the evolution of a random graph, quantitative characteristics of the zero-one law, or the contribution of Frank Ramsey to the research on Hilbert's Entscheidungsproblem). Also, we trace the behavior of the descriptive complexity of a graph as the logic becomes more restrictive (for example, only definitions with a bounded number of variables or quantifier alternations are allowed) or more expressible (after powering with counting quantifiers).

preprint2013arXiv

On the speed of constraint propagation and the time complexity of arc consistency testing

Establishing arc consistency on two relational structures is one of the most popular heuristics for the constraint satisfaction problem. We aim at determining the time complexity of arc consistency testing. The input structures $G$ and $H$ can be supposed to be connected colored graphs, as the general problem reduces to this particular case. We first observe the upper bound $O(e(G)v(H)+v(G)e(H))$ , which implies the bound $O(e(G)e(H))$ in terms of the number of edges and the bound $O((v(G)+v(H))^3)$ in terms of the number of vertices. We then show that both bounds are tight up to a constant factor as long as an arc consistency algorithm is based on constraint propagation (like any algorithm currently known). Our argument for the lower bounds is based on examples of slow constraint propagation. We measure the speed of constraint propagation observed on a pair $G,H$ by the size of a proof, in a natural combinatorial proof system, that Spoiler wins the existential 2-pebble game on $G,H$ . The proof size is bounded from below by the game length $D(G,H)$ , and a crucial ingredient of our analysis is the existence of $G,H$ with $D(G,H)=Ω(v(G)v(H))$ . We find one such example among old benchmark instances for the arc consistency problem and also suggest a new, different construction.

preprint2013arXiv

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

We present a logspace algorithm that constructs a canonical intersection model for a given proper circular-arc graph, where `canonical' means that models of isomorphic graphs are equal. This implies that the recognition and the isomorphism problems for this class of graphs are solvable in logspace. For a broader class of concave-round graphs, that still possess (not necessarily proper) circular-arc models, we show that those can also be constructed canonically in logspace. As a building block for these results, we show how to compute canonical models of circular-arc hypergraphs in logspace, which are also known as matrices with the circular-ones property. Finally, we consider the search version of the Star System Problem that consists in reconstructing a graph from its closed neighborhood hypergraph. We solve it in logspace for the classes of proper circular-arc, concave-round, and co-convex graphs.

preprint2011arXiv

On collinear sets in straight line drawings

We consider straight line drawings of a planar graph $G$ with possible edge crossings. The \emph{untangling problem} is to eliminate all edge crossings by moving as few vertices as possible to new positions. Let $fix(G)$ denote the maximum number of vertices that can be left fixed in the worst case. In the \emph{allocation problem}, we are given a planar graph $G$ on $n$ vertices together with an $n$ -point set $X$ in the plane and have to draw $G$ without edge crossings so that as many vertices as possible are located in $X$ . Let $fit(G)$ denote the maximum number of points fitting this purpose in the worst case. As $fix(G)\le fit(G)$ , we are interested in upper bounds for the latter and lower bounds for the former parameter. For each $ε>0$ , we construct an infinite sequence of graphs with $fit(G)=O(n^{σ+ε})$ , where $σ<0.99$ is a known graph-theoretic constant, namely the shortness exponent for the class of cubic polyhedral graphs. To the best of our knowledge, this is the first example of graphs with $fit(G)=o(n)$ . On the other hand, we prove that $fix(G)\ge\sqrt{n/30}$ for all $G$ with tree-width at most 2. This extends the lower bound obtained by Goaoc et al. [Discrete and Computational Geometry 42:542-569 (2009)] for outerplanar graphs. Our upper bound for $fit(G)$ is based on the fact that the constructed graphs can have only few collinear vertices in any crossing-free drawing. To prove the lower bound for $fix(G)$ , we show that graphs of tree-width 2 admit drawings that have large sets of collinear vertices with some additional special properties.

preprint2010arXiv

Untangling planar graphs from a specified vertex position - Hard cases

Given a planar graph $G$ , we consider drawings of $G$ in the plane where edges are represented by straight line segments (which possibly intersect). Such a drawing is specified by an injective embedding $π$ of the vertex set of $G$ into the plane. We prove that a wheel graph $W_n$ admits a drawing $π$ such that, if one wants to eliminate edge crossings by shifting vertices to new positions in the plane, then at most $(2+o(1))\sqrt n$ of all $n$ vertices can stay fixed. Moreover, such a drawing $π$ exists even if it is presupposed that the vertices occupy any prescribed set of points in the plane. Similar questions are discussed for other families of planar graphs.

preprint2009arXiv

Fermat's spiral and the line between Yin and Yang

Let $D$ denote a disk of unit area. We call a subset $A$ of $D$ perfect if it has measure 1/2 and, with respect to any axial symmetry of $D$ , the maximal symmetric subset of $A$ has measure 1/4. We call a curve $β$ in $D$ an yin-yang line if $β$ splits $D$ into two congruent perfect sets, $β$ crosses each concentric circle of $D$ twice, $β$ crosses each radius of $D$ once. We prove that Fermat's spiral is a unique yin-yang line in the class of smooth curves algebraic in polar coordinates.

preprint2007arXiv

From Invariants to Canonization in Parallel

A function $f$ of a graph is called a complete graph invariant if the isomorphism of graphs $G$ and $H$ is equivalent to the equality $f(G)=f(H)$ . If, in addition, $f(G)$ is a graph isomorphic to $G$ , then $f$ is called a canonical form for graphs. Gurevich proves that graphs have a polynomial-time computable canonical form exactly when they have a polynomial-time computable complete invariant. We extend this equivalence to the polylogarithmic-time model of parallel computation for classes of graphs with bounded rigidity index and for classes of graphs with small separators. In particular, our results apply to three representative classes of graphs embeddable into a fixed surface, namely, to 5-connected graphs, to 3-connected graphs admitting a polyhedral embedding, and 3-connected graphs admitting a large-edge-width embedding. Another application covers graphs with bounded treewidth. Since in the latter case an NC complete-invariant algorithm is known, we conclude that graphs of bounded treewidth have a canonical form (and even a canonical labeling) computable in NC.

preprint2007arXiv

On the Obfuscation Complexity of Planar Graphs

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)\ge 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)\ge 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)\ge2$ 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.

preprint2003arXiv

The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

We say that a first order formula A distinguishes a graph G from another graph G' if A is true on G and false on G'. Provided G and G' are non-isomorphic, let D(G,G') denote the minimal quantifier rank of a such formula. We prove that, if G and G' have the same order n, then D(G,G')\le(n+3)/2, which is tight up to an additive constant of 1. The analogous questions are considered for directed graphs (more generally, for arbitrary structures with maximum relation arity 2) and for k-uniform hypergraphs. Also, we study defining formulas, where we require that A distinguishes G from any other non-isomorphic G'.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Oleg Verbitsky

Research overview

Is this your work?

19 publications

Identifiability of Graphs with Small Color Classes by the Weisfeiler-Leman Algorithm

Local WL Invariance and Hidden Shades of Regularity

On the Weisfeiler-Leman Dimension of Fractional Packing

The Weisfeiler-Leman Algorithm and Recognition of Graph Properties

Drawing Graphs on Few Lines and Few Planes

Graph Isomorphism, Color Refinement, and Compactness

Universal covers, color refinement, and two-variable counting logic: Lower bounds for the depth

On the dynamic width of the 3-colorability problem

Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy

Circular-arc hypergraphs: Rigidity via Connectedness

Logical complexity of graphs: a survey

On the speed of constraint propagation and the time complexity of arc consistency testing

Solving the Canonical Representation and Star System Problems for Proper Circular-Arc Graphs in Log-Space

On collinear sets in straight line drawings

Untangling planar graphs from a specified vertex position - Hard cases

Fermat's spiral and the line between Yin and Yang

From Invariants to Canonization in Parallel

On the Obfuscation Complexity of Planar Graphs

The First Order Definability of Graphs: Upper Bounds for Quantifier Rank

See the researcher in context

Building this map preview