Oleg Verbitsky

Joel Rybicki, Oleg Verbitsky, Maksim Zhukovskii

We study what deterministic distributed algorithms can compute on random input graphs in extremely weak models of distributed computing: all nodes are anonymous, and in each communication round, nodes broadcast a message to all their neighbors, receive a (multi)set of messages from their neighbors, and update their local state. These correspond to the SB and MB models introduced by Hella et al. [PODC 2012] and are strictly weaker than the standard port-numbering PN and LOCAL models. We investigate what can be computed almost surely on random input graphs. We give a one-round deterministic SB-algorithm using $O(\log n)$-bit messages that computes unique identifiers with high probability on anonymous networks sampled from $G(n,p)$, where $n^{\varepsilon-1} \le p \le 1/2$ and $\varepsilon>0$ is an arbitrarily small constant. This algorithm is inspired by canonical labeling techniques in graph isomorphism testing and can be used to "anonymize" existing distributed graph algorithms designed for the broadcast CONGEST and LOCAL models. In particular, we give a new anonymous algorithm that finds a triangle in $O(1/\varepsilon)$ rounds on the above input distribution. We also investigate computational power of natural analogs of "Monte Carlo" and "Las Vegas" distributed graph algorithms in the random graph setting, and establish some new collapse and hierarchy results. For example, our work shows the collapse of the weak model hierarchy of Hella et al. on $G(n,p)$, as apart from a vanishingly small fraction of input graphs, the SB model is as powerful as LOCAL.

V. Arvind, Johannes Köbler, Oleg Verbitsky

One of the most basic facts related to the famous Ulam reconstruction conjecture is that the connectedness of a graph can be determined by the deck of its vertex-deleted subgraphs, which are considered up to isomorphism. We strengthen this result by proving that connectedness can still be determined when the subgraphs in the deck are given up to equivalence under the color refinement isomorphism test. Consequently, this implies that connectedness is recognizable by Reconstruction Graph Neural Networks, a recently introduced GNN architecture inspired by the reconstruction conjecture (Cotta, Morris, Ribeiro 2021).

Sergei Kiselev, Andrey Kupavskii, Oleg Verbitsky et al.

We study vulnerability of a uniformly distributed random graph to an attack by an adversary who aims for a global change of the distribution while being able to make only a local change in the graph. We call a graph property $A$ anti-stochastic if the probability that a random graph $G$ satisfies $A$ is small but, with high probability, there is a small perturbation transforming $G$ into a graph satisfying $A$. While for labeled graphs such properties are easy to obtain from binary covering codes, the existence of anti-stochastic properties for unlabeled graphs is not so evident. If an admissible perturbation is either the addition or the deletion of one edge, we exhibit an anti-stochastic property that is satisfied by a random unlabeled graph of order $n$ with probability $(2+o(1))/n^2$, which is as small as possible. We also express another anti-stochastic property in terms of the degree sequence of a graph. This property has probability $(2+o(1))/(n\ln n)$, which is optimal up to factor of 2.

Christoph Berkholz, Oleg Verbitsky

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.