Distributed Stochastic Graph Algorithms

Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis · 2026

Read Distributed Stochastic Graph Algorithms by Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-21248.txt.

Introduction

Keren Censor-Hillel, Aditi Dudeja, and George Giakkoupis study stochastic graph optimization in a distributed setting. A random subgraph keeps each edge of a known base graph with a known chance, and the task must be solved despite edge doubt. Here each vertex knows only its own edges and talks only over them, with cost counted in sync rounds. The authors show distributed stochastic methods can beat non-stochastic methods and known lower bounds, with fast approximations for maximum matching and related tasks.

Catalog record

CREATORKeren Censor-Hillel, Aditi Dudeja, George Giakkoupis
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE81777
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.21248

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributed Stochastic Graph Algorithms Keren Censor-Hillel, Aditi Dudeja, George Giakkoupis Abstract We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph G ∗ G^{\ast} of a known base graph G G is realized by including each edge e e independently with a known probability p e p_{e} , and we must solve an optimization problem on G ∗ G^{\ast} despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of G G to learn if the edge exists in G ∗ G^{\ast} , and its complexity is the number of queried edges. The distributed setting incorporates uncertainty in a natural manner, by having each vertex know only about its own edges in G ∗ G^{\ast} (and only communicate over them), and the complexity is measured by the number of synchronous communication rounds. We establish that distributed stochastic algorithms can be drastically faster than their non-stochastic counterparts and overcome known lower bounds, by showing fast distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set. Specifically: • Within two rounds of single-bit messages we obtain a constant approximation for maximum matching, and a single round suffices for an O ⁡ ( log ⁡ Δ ¯ ) O(\log\bar{\Delta}) -approximation algorithm for minimum dominating set, where Δ ¯ \bar{\Delta} is the maximum expected degree of G ∗ G^{\ast} . Our most novel technical contribution is a constant approximation algorithm for minimum vertex cover which uses no communication at all. • Allowing more, but still a constant number of rounds enables better approximations: For maximum matching we provide a ( 0.68 − ϵ ) (0.68-\epsilon) -approximation and a ( 0.73 − ϵ ) (0.73-\epsilon) -approximation algorithms for general and bipartite graphs, respectively, running in poly ⁡ ( 1 / ϵ ) \poly(1/\epsilon) rounds; and for minimum vertex cover we give a ( 2 + ϵ ) (2+\epsilon) -approximation algorithm running in poly ⁡ ( 1 / ϵ ) \poly(1/\epsilon) rounds. Some of these results rely on previous works on the standard stochastic setting, namely, [Behnezhad et al., SODA 2022] and [Derakhshan and Saneian, ICALP 2025], while others require new algorithmic ideas. 1 Introduction Stochastic algorithms address a setting in which a problem needs to be solved over some random sample of a given data set. In particular, there has been extensive research on stochastic graph algorithms [ 27 , 7 , 24 , 6 , 8 , 20 , 23 , 22 , 21 , 19 , 33 , 38 , 11 , 35 , 19 , 32 , 34 ] , where each edge e of a known base graph G has some known probability p_{e} of being present in a sampled realization G^{\ast} of G , and the graph problem needs to be solved over G^{\ast} . The challenge for a stochastic algorithm is the uncertainty about which edges of G actually get realized in G^{\ast} . To this end, the algorithm can query (non-adaptively) any set of edges to learn this information, and the complexity of a stochastic graph algorithm is typically measured by the number of edges it queries. In this paper, we introduce and study a distributed variant of the centralized stochastic setting: Nodes know the base graph G and the edge realization probabilities p_{e} , as in the centralized setting. In addition, each node knows its realized edges and can exchange messages (only) through these edges, and the complexity is measured by the number of communication rounds. This model is motivated by the observation that the traditional assumption in distributed graph algorithms that nodes do not have any information about the graph (except possibly for their set of direct neighbors), does not reflect modern networked systems, such as large-scale data centers or content delivery networks, where the underlying physical infrastructure – the base graph G – is often static and known to all participants, and the challenge is that link availability and node congestion fluctuate according to unpredictable, stochastic processes. The model we propose is perhaps one of the simplest and most natural abstractions for leveraging the history of a network with the goal of improving algorithmic complexity. In practice, realization probabilities p_{e} can be viewed as predictions generated by machine learning models trained on historical traffic patterns. Next we describe the model in detail. Distributed Stochastic Model. In the classic distributed models, n vertices in a network communicate in synchronous rounds, in each of which every vertex can send a message to each of its neighbors. When considering distributed algorithms for a stochastic setting, we follow the paradigm of the centralized stochastic setting, which allows the algorithm to preprocess the base graph. Thus, in the distributed stochastic model, the base graph G=(V,E) (i.e., the network) is known to all vertices. For a graph problem P , its stochastic version is the problem P over a random realization G^{\ast} , which is a subgraph of G obtained by including every edge e\in E(G) in it independently with probability p_{e} , where the values p_{e} are known to all vertices. The uncertainty about which edges actually appear in G^{\ast} is incorporated into the distributed model in a natural manner: each vertex v knows only the set N_{G^{\ast}}(v) of its neighbors in G^{\ast} , and can communicate only over these edges. A distributed stochastic algorithm may preprocess the base network graph G , and its complexity is its number of communication rounds after G^{*} is realized. 1 1 1 More generally, instead of knowing the complete base graph G , one may allow each vertex v to know (and preprocess) only the subgraph of G induced by v ’s h -hop neighborhood in G . We believe that some of our algorithms can be adapted to this more refined model, for h=\poly\log(n) . We demonstrate that the distributed stochastic model is remarkably powerful, allowing us to bypass lower bounds that apply to classical distributed algorithms. Namely, we provide distributed approximation algorithms for maximum matching, minimum vertex cover, and minimum dominating set, that require a constant number of communication rounds (and sometimes no communication at all). Achieving comparable approximations by classical distributed algorithms requires a super-constant number of communication rounds. 1.1 Our Contribution For stochastic algorithms, an \alpha -approximation refers to the ratio between the expected size of the solution and the expected size of an optimal solution (both for G^{\ast} ). The round complexity of our algorithms is either a small constant, or a constant that depends on an approximation constant \epsilon . Notably, the round complexity does not depend on n nor on the realization probabilities p_{e} . In contrast, in the centralized setting it is known that that the total number of queries must depend on both (as well as on \epsilon ) [ 8 ] . All of our algorithms use messages of size at most O(\log{n}) bits as in the distributed Congest model, and many of them only need single-bit messages. For all three optimization problems, our results can be contrasted with the non-stochastic distributed setting, in which any polylogarithmic approximation needs a number of rounds that is \Omega(\log\Delta/\log\log\Delta) or \Omega(\sqrt{\log{n}/\log\log{n}}) [ 68

Read the complete text