arXiv CSopen access

Distributed Stochastic Graph Algorithms

Distributed Stochastic Graph Algorithms Keren Censor-Hillel

Aditi Dudeja

Technion, Israel [email protected]

The Chinese University of Hong Kong, Shenzhen [email protected]

arXiv:2605.21248v1 [cs.DS] 20 May 2026

George Giakkoupis Inria, France [email protected]

Abstract We study stochastic graph optimization problems in a novel distributed setting. As in the standard centralized setting, a random subgraph G∗ of a known base graph G is realized by including each edge e independently with a known probability pe , and we must solve an optimization problem on G∗ despite uncertainty about its edges. In the standard setting, to cope with this uncertainty, the algorithm can query any edge of G to learn if the edge exists in G∗ , 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∗ (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 nonstochastic 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 maxi¯ mum matching, and a single round suffices for an O(log ∆)-approximation algorithm for ¯ minimum dominating set, where ∆ is the maximum expected degree of G∗ . 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 − ϵ)-approximation and a (0.73 − ϵ)-approximation algorithms for general and bipartite graphs, respectively, running in poly(1/ϵ) rounds; and for minimum vertex cover we give a (2 + ϵ)-approximation algorithm running in poly(1/ϵ) 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 [BDH+ 15, AKL17, BR18, AB19, AKL19, BDF+ 19, BFHR19, BD20, BDH20, BBD22, DF23, DKP23, ABGR25, DS25, BBD22, DDH23, DSX25], where each edge e of a known base 1

graph G has some known probability pe of being present in a sampled realization G∗ of G, and the graph problem needs to be solved over G∗ . The challenge for a stochastic algorithm is the uncertainty about which edges of G actually get realized in G∗ . 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 pe , 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 pe 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∗ , which is a subgraph of G obtained by including every edge e ∈ E(G) in it independently with probability pe , where the values pe are known to all vertices. The uncertainty about which edges actually appear in G∗ is incorporated into the distributed model in a natural manner: each vertex v knows only the set NG∗ (v) of its neighbors in G∗ , 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 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 α-approximation refers to the ratio between the expected size of the solution and the expected size of an optimal solution (both for G∗ ). The round complexity of our algorithms is either a small constant, or a constant that depends on an approximation constant ϵ. Notably, the round complexity does not depend on n nor on 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).

2

the realization probabilities pe . In contrast, in the centralized setting it is known that that the total number of queries must depend on both (as well as on ϵ) [AKL19]. 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 p any polylogarithmic approximation needs a number of rounds that is Ω(log ∆/ log log ∆) or Ω( log n/ log log n) [KMW16]. Minimum Vertex Cover. Our most novel technical contribution is in a constant approximation for minimum vertex cover, which can be obtained without communication. Theorem 1. There is a deterministic algorithm for the distributed stochastic minimum vertex cover problem that outputs a 3.44-approximation and requires no communication between vertices. Our algorithm, given in Section 2, associates each edge uv of G with its endpoint, u or v, that has the larger conditional probability of being in the optimal vertex cover of G∗ , given that uv is realized. (These probabilities can be computed from G and the edge realization probabilities in a preprocessing phase.) Note that the larger of these two probabilities must be at least 1/2. A vertex is then included in the vertex cover if and only if at least one of its associated edges is realized. For intuition, suppose that all edges have the same realization probability p, and let Ev denote the set of edges associated with vertex v. The probability that v is in the optimal vertex cover is bounded from below by the minimum probability with which v must be in a vertex cover to ensure that for each of the (independently realized) edges e ∈ Ev , v covers e with probability at least 1/2. This minimum probability can be computed using properties of the binomial distribution. It is at most a constant factor smaller than the probability 1 − (1 − p)|Eu | that v covers every realized edge e ∈ Ev with probability 1, which is the probability that v is in the vertex cover output by our algorithm. To handle the case of different edge realization probabilities, we use a refinement of this argument, which involves associating with each edge an independent Poisson random variable that is non-zero if and only if the edge is realized, and is used instead of a binary random variable. We also show (in Section 3) that we can obtain a (2+ϵ)-approximation within poly(1/ϵ) rounds. Theorem 2. There is a deterministic algorithm for the distributed stochastic minimum vertex cover problem that outputs a (2 + ϵ)-approximation in poly(1/ϵ) rounds of single-bit messages. To obtain this result, we follow an approach from [BBD22]. At the core of this approach is a standard algorithm that computes a fractional matching by uniformly increasing the fractional weights of all edges; an edge becomes inactive once the total weight of the edges at one of its endpoints reaches 1. This algorithm starts on the base graph G, and switches to the realized graph G∗ as soon as the maximum edge weight reaches a threshold. Adapting the approach to the distributed setting presents some technical challenges. In particular, uniformly increasing the edge weights in the first stage of the algorithm results in prohibitively large remaining vertex degrees in the second stage. We solve this problem by increasing the edge weights proportionally to the realization probabilities, rather than uniformly. This ensures that vertices have constant expected remaining degrees in the realized graph, but we still need to handle separately vertices whose actual degree is super-constant. Moreover, combining the two parts of the algorithm requires more care over the original approach in [BBD22]. We mention that paper [DDH23] gives an algorithm for centralized stochastic minimum vertex cover that obtains a (3/2 + ϵ) approximation, which is better than ours. However, we are not aware of a way to adapt the approach given there in our setting. The main obstacle is that the approach 3

needs to compute a near-optimal vertex cover in a sparse subgraph of the base graph. In our setting we can obtain the sparse subgraph, but do not know how to compute the near-optimal vertex cover efficiently. Maximum Matching. For the maximum matching problem, we can get a constant approximation in only two rounds (see Section 4). Theorem 3. There is a randomized algorithm for the distributed stochastic maximum matching problem that outputs a 0.39-approximation in two rounds of single-bit messages. If the base graph is bipartite, an improved approximation ratio of 0.63 is achieved. The algorithm for bipartite graphs is identical to an algorithm given in [BBD22] for the centralized stochastic setting: Each vertex from the one side of the bipartite graph proposes to a neighbor on the other side, chosen independently at randomly according to the matching probabilities from the optimal solution; and each vertex from the receiving side that gets at least one proposal accepts one of them. For non-bipartite graphs we essentially apply the same algorithm to a random bipartite subgraph, obtained by choosing the side of each vertex independently at random (with near uniform probability). Making sure that the proposal probabilities are independent, as in the bipartite case, requires some care in handling non-bipartite edges. We show (in Section 5) that we can achieve better constant approximations using poly(1/ϵ) rounds. Theorem 4. There is a randomized algorithm for the distributed stochastic maximum matching problem that outputs a (0.68 − ϵ)-approximation in poly(1/ϵ) rounds of O(log n)-bit messages. If the base graph is bipartite, an improved approximation ratio of (0.73 − ϵ) is achieved. Both results assume that all edges e have the same realization probability pe = p.2 To prove the above, we rely on a result from [DS25] which states that there exists a subgraph Q of G of maximum degree p−1 · poly(1/ϵ), whose realization Q∗ has expected matching size close to the matching size of G∗ .3 In our distributed setting, this subgraph Q can be computed in the preprocessing stage. For our algorithm, we assume that all edges e have the same realization probability pe = p, thus the expected degree of any vertex in Q∗ is poly(1/ϵ). If this were the case for the maximum degree of Q∗ , we could apply known distributed algorithms to obtain near optimal matching in poly(1/ϵ) rounds. However, the maximum degree in Q∗ may be higher. We overcome this issue by proving that removing vertices of higher degree decreases the matching size only marginally, and we then apply a known distributed matching algorithm on the remaining graph. Minimum Dominating Set. We show (in Section 6) that one round of communication allows an approximation that is logarithmic in the maximum expected degree of G∗ , ¯ = max E[degG∗ (v)]. ∆ v∈V

Theorem 5. There is a deterministic algorithm for the distributed stochastic minimum dominating ¯ set problem that outputs a O(log ∆)-approximation in a single round of single-bit messages. 2 3

This is the only result in this paper in which we make this assumption. In [DS25], p = mine∈E pe is the minimum realization probability of any edge.

4

Our approach is to mimic the greedy algorithm using the expected degrees in G∗ rather than the actual degrees. However, a technical challenge arises since actual degrees may differ from their expectation. It is relatively straightforward to show a bound of O(log n) on the approximation ratio. ¯ we use a careful argument that accounts for the contribution To prove the logarithmic bound on ∆ of vertices whose actual degree exceeds their expectation or falls short of the expectation. 1.1.1

An Improved 3-Approximation for Vertex Cover without Communication

A result from recent independent work [vdBGP+ 26] immediately implies a 2c-approximate distributed stochastic vertex cover algorithm without communication, where c < 8. Their result assumes pe = p for all edges e. Precisely, [vdBGP+ 26, Lemma 4.4] shows that there is a set of vertices S ⊆ V such that |S| ≤ c · E[|MVC(G∗ )|] and the number of edges in the remaining induced subgraph G[V \ S] is at most c · E[|MVC(G∗ )|]/p, where MVC(H) denotes a minimum vertex cover of any graph H. Therefore, a set containing all vertices from S plus one endpoint of each edge in G∗ [V \ S] forms a vertex cover of G∗ with an expected size of at most 2c · E[|MVC(G∗ )|]. Using the construction from [vdBGP+ 26, Lemma 4.4], we can obtain an improved 3-approximate distributed stochastic algorithm without communication. By a greedy process, the lemma constructs an ordering π = (v1 , . . . , vn ) of the vertices that satisfies the following property: Let M be a random matching of G∗ obtained by a sequential process considering the vertices in the order of π. When vertex vi is considered, if it is not already matched (to a vertex in {v1 , . . . , vi−1 }) and has at least one unmatched neighbor in {vi+1 , . . . , vn }, then vi is matched to a neighbor chosen uniformly at random from those options. Let qi be the probability that vi is matched to a vertex in {v1 , . . . , vi−1 }. The ordering π ensures that the probability of vi being matched to a vertex in {vi+1 , . . . , vn } is at least Ri (1 − 2qi ), where Ri is the probability that vi has at least one neighbor in {vi+1 , . . . , vn } in G∗ . Consider now the (random) vertex set C consisting of all vertices vi that have at least one neighbor in {vi+1 , . . . , vn } in G∗ . Note that C is a valid vertex cover of G∗ because for any realized edge (vi , vj ) with i < j, its endpoint vi is included in C. C can be constructed without PMoreover, n communication given π. Its expected size is E[|C|] = i=1 Ri . We can bound the expected size of matching M by countingPits edges via their endpoints. Counting via the higher-indexed (right) endpoints yields E[|M |] = ni=1 qi , while counting via the lower-indexed (left) endpoints yields: E[|M |] ≥

n X i=1

Ri (1 − 2qi ) ≥

n X

Ri −

i=1

n X

2qi = E[|C|] − 2 E[|M |].

i=1

Rearranging yields E[|C|] ≤ 3 E[|M |]. Since the size of any matching is a lower bound for the size of a minimum vertex cover, it follows that E[|C|] ≤ 3 E[|MVC(G∗ )|]. This result does not require the assumption that all edges have the same realization probability p.

1.2

Related Work

We restrict our attention to three areas of related work: algorithms for centralized stochastic graph problems, distributed graph algorithms for the standard Congest and related models, and distributed graph algorithms with predictions and advice. Centralized Stochastic Graph Algorithms. As mentioned earlier, the limiting resource in these works is the number edges that the algorithm needs to query (non-adaptively), in order to solve an approximate optimization problem on the realized graph. Motivated by maximizing the expected number of successful transplants in a kidney exchange problem, the pioneering 5

work of [BDH+ 15] proposed a constant-approximate stochastic matching algorithm using a number of queries per vertex that depends only on the (minimum) edge realization probability. This has led to a major line of research about improving the approximation ratio and reducing the number of queries [AKL17, BR18, AB19, AKL19, BDF+ 19, BFHR19, BD20, BDH20, BBD22, DF23, DKP23, ABGR25, DS25]. More recently, stochastic minimum vertex cover has been studied [BBD22, DDH23, DSX25, vdBGP+ 26]. Other problems that have been considered include stochastic minimum spanning trees [GV06], stochastic packing problems [MY20], and stochastic shortest path problems [Von07]. Related work in Congest and Supported Models. Exact computation of the minimum vertex cover or dominating set in the Congest model requires Ω̃(n2 ) rounds in general graphs [ACKP21, BCD+ 19]. Approximation algorithms have been extensively studied for maximum matching [Lub85, II86, ABI86, WW04, LPR09, LPP15, BCGS17, AKO18, BKS19, Fis20, FFK21, FMU22, CS22, KI22, HS23, IKY24, MS25], minimum vertex cover [KVY94, HKP01, PR01, KMW06, GKP08, KY09, ÅFP+ 09, PS09, ÅS10, BEPS12, Fis17, BCS17, BEKS18, FK20, FFK21], and minimum dominating set [JRS02, KW05, KMW06, KMW16, GK18, DKM19, CD21, MSW21, FGG+ 23, DGI24]. p However, an Ω(log ∆/ log log ∆) or Ω( log n/ log log n) lower bound is known for polylogarithmic approximations [KMW04]. For vertex cover, higher logarithmic lower bounds are known for (1 + ϵ)-approximations [GS14, FFK21]. In the Supported model [SS13], the topology of the communication graph is known in advance and a graph problem needs to be solved for an adversarially chosen subgraph [KR17, FKRS19, FHSS19, FFK21, FKP+ 21, HWZ21, KPR+ 21, BKK+ 23, ALH+ 23, AAPR23, BBBO24]. While this model also leverages processing, our setting differs in that (i) the input subgraph is random rather than adversarial, and (ii) the communication takes place only over edges of the subgraph rather than over the entire base graph (this is referred to as a passive Supported model in [FHSS19]). Distributed Graph Algorithms with Predictions and Advice. Our model can be viewed as part of a general paradigm where nodes are given extra information about the graph. In distributed algorithms with predictions, each node is also given some extra information that may (or may not) be correct, and the goal is for the algorithm to work faster when predictions are good and to not work much worse than without predictions when predictions are bad. Distributed maximal independent set algorithms with predictions, where each node is given a prediction for its output, were recently studied in [BEL25]. In distributed algorithms with advice, each node is given some additional information, as well, but this information is always correct and is chosen by the algorithm designer. The goal is to measure the improvement possible for a given advice size, or compute the minimum advice size to significantly improve performance. Distributed graph algorithms with advice have been proposed for coloring and minimum spanning trees [FGIP09, FKL10, BBK+ 25].

2

Constant Approximation for Minimum Vertex Cover without Communication

We present an algorithm that computes a constant approximation of the minimum vertex cover without requiring any communication. Theorem 1. There is a deterministic algorithm for the distributed stochastic minimum vertex cover problem that outputs a 3.44-approximation and requires no communication between vertices.

6

Let FC be any fractional vertex cover algorithm, and let F C(H) denote its output for input graph H.4 We denote by Fv the fractional weight assigned to vertex v in fractional cover FC(G∗ ) of the realized graph G∗ = (V, E ∗ ). For every edge vu of G we denote by fvu the conditional expectation of Fv given that vu is realized, fvu = E[Fv | vu ∈ E ∗ ]. Note that fvu + fuv ≥ 1 and thus max{fvu , fuv } ≥ 1/2. Distributed Algorithm 1. (Preprocessing stage) Each vertex v ∈ V computes a subset Ev of its incident edges in G, where Ev = {vu ∈ E(G) : fvu ≥ fuv }. This is the set of edges that v is ‘responsible’ for covering if realized. 2. (Distributed stage) At this stage, each v ∈ V is made aware of the set of its realized incident edges in G∗ . If at least one edge e ∈ Ev is realized, then v is added to the output vertex cover set, denoted C. Correctness follows from the fact that for each edge uv, uv ∈ Eu or uv ∈ Ev , and if uv is realized then the responsible vertex is included in the vertex cover. The approximation ratio of 3.44 follows from the next lemma. Lemma 6. For every vertex v ∈ V , the probability that v is contained in the vertex cover C computed by the distributed algorithm is P(v ∈ C) ≤ 3.44 · E[Fv ]. From Lemma 6 we get that the expected size of the vertex cover C is at most 3.44 times larger than the expected size of fractional cover F C(G∗ ), i.e., X E[|C|] ≤ 3.44 · E[Fv ]. v∈V

Proof of Lemma 6. Let e = uv. For every edge e ∈ Ev , let Xe be the indicator random variable of the event vu ∈ E ∗ , that edge vu is realized in G∗ . We associate with each edge e ∈ Ev a Poisson random variable Ye with mean λe = ln

1 , 1 − pe

such that: 1. Ye = 0 if and only if Xe = 0, 2. The random variables Ye , for e ∈ Ev , are mutually independent, and 4

A fractional vertex cover is an assignment of values in [0, 1] to the vertices such that for every edge, the sum of values of both endpoints is at least 1. The value of the cover is the sum of all vertex values. We assume a fractional vertex cover algorithm instead of an integral one, because an optimal fractional vertex cover is computable in polynomial time.

7

3. Ye is conditionally independent of Fv given Xe . The first point is feasible because 1 − ln 1−p

P(Ye = 0) = e−λe = e

e

= 1 − pe = P(Xe = 0).

All three points can be satisfied simply by drawing the values of the Ye after the realized graph G∗ and the cover FC(G∗ ) are determined, such that Ye = 0 if Xe = 0, while if Xe = 1, Ye ’s value is drawn independently from the conditional Poisson distribution of mean λe given Ye ̸= 0. Let X Yv = Ye . e∈Ev

Being the sum of independent Poisson random variables, Yv is a Poisson random variable as well, with mean X λv = λe . e∈Ev

We can express P(v ∈ C) in terms of Yv , as !

! P(v ∈ C) = P

X

Xe ̸= 0

=P

X

Ye ̸= 0

= P(Yv ̸= 0).

(1)

e∈Ev

e∈Ev

where the second equation holds because Ye = 0 if and only if Xe = 0. Next we show that E[Fv · Yv ] ≥ 21 · E[Yv ]. For any edge e = vu ∈ Ev , E[Fv · Ye ] = E[Fv · Ye | Ye ̸= 0] · P(Ye ̸= 0) = E[Fv · Ye | Xe = 1] · P(Ye ̸= 0) = E[Fv | Xe = 1] · E[Ye | Xe = 1] · P(Ye ̸= 0) = fvu · E[Ye | Ye ̸= 0] · P(Ye ̸= 0), = fvu · E[Ye ] 1 ≥ · E[Ye ], 2 where in the third line we used the conditional independence of Ye and Fv given Xe , and in the last line we used that fvu ≥ 1/2 because fvu ≥ fuv and fvu + fuv ≥ 1. It follows X 1 X 1 E[Fv · Yv ] = E[Fv · Ye ] ≥ · E[Ye ] = · E[Yv ]. (2) 2 2 e∈Ev

e∈Ev

Inequality (2) allows us to apply a property of the Poisson distribution that we show in technical Lemma 7, to obtain P(Yv ̸= 0) E[Fv ] ≥ 3.44 Combining this and (1) completes the proof of the lemma. Lemma 7 (A Property of Poisson Distribution). Let Y be a Poisson random variable, and F be a real random variable that takes values in the interval [0, 1]. The two random variables are not necessarily independent. If E[F · Y ] ≥ 21 · E[Y ] then E[F ] ≥

P(Y ̸= 0) . 3.44 8

Proof. Let λ = E[Y ] be the mean of Poisson random variable Y , and for k ≥ 0, let qk denote the probability that Y = k, λk e−λ qk = P(Y = k) = . k! Let m ≥ 1 be an integer and β ∈ (0, 1] a real such that X

kqk + β(m + 1)qm+1 =

k≤m

λ . 2

(3)

(We will see that m is the median of Y .) Let F ∗ be a random variable such that   if 0 ≤ Y ≤ m 0 ∗ F = 1 − β if Y = m + 1   1 if Y ≥ m + 2 We have that F ∗ is in [0, 1], and we will show that E[F ∗ · Y ] = λ2 . We then argue that among all random variables F that take values on [0, 1] and satisfy E[F · Y ] ≥ λ2 , random variable F ∗ has the smallest mean. I.e., E[F ∗ ] ≤ E[F ], for any random variable F that takes values on [0, 1] and E[F · Y ] ≥ λ2 . Thus, to prove the lemma it suffices to show E[F ∗ ] ≥

P(Y ̸= 0) . 3.44

We begin by showing that E[F ∗ · Y ] = λ2 : E[F ∗ · Y ] = (1 − β)(m + 1)qm+1 +

X

kqk

k≥m+2

X

= (1 − β)(m + 1)qm+1 + E[Y ] −

k · qk

k≤m+1

λ = E[Y ] − 2 λ = , 2 where the second-last line was obtained using (3). Next, we explain why E[F ∗ ] ≤ E[F ], for any F that takes values on [0, 1] and P satisfies that = E[F · 1 ] ≤ q . The constraint gives us that E[F · Y ] ≥ λ2 : For y ≥ 0, let zP y y Y =y y y · zy ≥ λ/2, and the goal is to minimize P y zy . Since y is monotonically increasing, by the rearrangement inequality, the minimum for y zy is attained by maximizing values of zy for larger y, namely, setting zy = E[F · Y ] = qy , or equivalently, setting F = 1 if y > y0 , and setting F = 0 if y < y0 , for some y0 . It remains to show P(Y ̸= 0) . E[F ∗ ] ≥ 3.44 First, notice that X X E[F ∗ ] = (1 − β)qm+1 + qk = 1 − qk − βqm+1 . (4) k≥m+2

9

k≤m

Substituting the definition of qk to (3) and simplifying gives X 1≤k≤m

λk e−λ λm+1 e−λ λ +β = , (k − 1)! m! 2

thus X k≤m−1

1 qk + βqm = . 2

(5)

Since β ∈ (0, 1], the above implies that m is the smallest integer such that the median of Y . For every i ≥ 0, let λi+1 be the value of λ that satisfies X 1 qk = ; 2

1 k≤m qk ≥ 2 , i.e., m is

P

k≤i

let also λ0 = 0. Then, for λi < λ ≤ λi+1 the median is m = i. We first use (5) to compute a loose bound on E[F ∗ ], which is however enough to prove the lemma for most values of λ. Combining (4) and (5), we obtain E[F ∗ ] =

1 1 1 − (1 − β)qm − βqm+1 = − qm + β(qm − qm+1 ) ≥ − qm , 2 2 2

where the last inequality holds because qm+1 = qm ·

λ < qm , m+1

since m ≥ λ + ln(2) [Cho94] and thus m + 1 > λ. For any i ≥ 1 and λi < λ ≤ λi+1 , the above inequality gives E[F ∗ ] ≥

1 λi e−λ 1 ii e−i 1 − qi = − ≥ − , 2 2 i! 2 i! i −i

since λi e−λ is minimized for λ = i. Note also that that term i ei! decreases as i increases. Then, for i ≥ 4, 1 44 e−4 1 E[F ∗ ] ≥ − > 0.304 > . 2 4! 3.3 Therefore the lemma holds for λ > λ4 . For the case of λ ≤ λ4 , we analyze the precise formula for E[F ∗ ]. We substitute in (4) the value of β obtained by solving (3) for β, to get   X X λ 1 E[F ∗ ] = 1 − qk − − qk  . m+1 2 k≤m

k≤m−1

For λ ≤ λ1 (and thus m = 0), we have E[F ∗ ] = 1 − λ/2. This gives E[F ∗ ] 1 − e−λ − λ/2 = , P(Y ̸= 0) 1 − e−λ which is a decreasing function on λ, thus the minimum is at the right endpoint λ1 of the interval. For λi < λ ≤ λi+1 , for each i ∈ {1, 2, 3}, we have verified that the function   P P λ 1 1 − q − − q ∗ k≤i k k≤i−1 k i+1 2 E[F ] = P(Y ̸= 0) 1 − q0 10

∗

E[F ] Figure 1: Plot of P(Y ̸=0) as a function of λ, used in the proof of Lemma 7.

is concave in each of the three intervals (the second derivative is negative), which implies the minimum lies in one of the points λi , for i ∈ {1, 2, of the function is shown in Figure 1. P3, 4}. A plot 1 Recall that λi+1 is the value of λ that satisfies k≤i qk = 2 . Solving that and substituting above 1 we obtain that the global minimum is at point λ2 = 1.678347 and the minimum value is 3.43068 .

3

Improved Approximation for Minimum Vertex Cover in poly(1/ϵ) Rounds

In this section we show that we can improve the approximation factor to 2 + ϵ at the cost of not too many communication rounds, namely, poly(1/ϵ). We give an algorithm that finds a vertex cover of G∗ with the following properties. Theorem 2. There is a deterministic algorithm for the distributed stochastic minimum vertex cover problem that outputs a (2 + ϵ)-approximation in poly(1/ϵ) rounds of single-bit messages. Our approach is based on an algorithm from [BBD22], but requires several modifications, as mentioned earlier. Throughout the algorithm we will use the following constants which we state here for convenience. Let 0 < ε ≤ 14 , and let ε1 = ε3

ε2 = ε + ε 3

ε3 = ε − ε 3

1 + ε2 1 + ε + ε3 = ε1 ε3 ε1 ε4 = ε2 + ε3 = 2ε ε5 = =ε (ε2 − ε1 )2 (2 + ε5 )(1 + ε4 ) (2 + ε)(1 + 2ε) ϵ= −2= − 2 ≤ 10ε, 1 − ε5 1−ε ξ=

where for the last inequality we used that ε ≤ 1/4. Distributed Algorithm 1. (Preprocessing Stage) Run Algorithm 1 on G = (V, E) to obtain a fractional matching ϕ = (ϕe )e∈E of G. Algorithm 1 is similar to the algorithm in [BBD22], except that the fractional 11

edge weights change proportionally to their realization probability, instead of uniformly. For P each vertex v, let ϕv = e∋v ϕe , and let F = {v ∈ V : ϕv = 1}. 2. (Distributed Phase) Let G∗ = (V, E ∗ ) denote the realized graph. Define χ = (χe )e∈E as ( ϕe , if e ∈ E ∗ χe = p e 0, if e ∈ E \ E ∗ . Let χv =

P

e∋v χe , for v ∈ V . Let the set of bad vertices be

B = {v ∈ V : χv ≥ ϕv + ε2 } . Let Q be the set of all edges of G with no endpoints in F ∪ B, Q = {e ∈ E : e ∩ (F ∪ B) = ∅}, and let Q∗ = Q ∩ E ∗ . We run Algorithm 2 in a distributed manner on graph (V, Q∗ ) with b = (ϕv )v∈V and obtain ψ = (ψe )e∈Q∗ . For convenience, we also define ψe = 0, for all e ∈ E \ Q∗ . Algorithm 2 is a discretized version of the algorithm in [BBD22]. The final output of the algorithm is the set C = F ∪ B ∪ {v ∈ V | ϕv + ψv ≥ 1} .

Algorithm 1 WaterFilling(H = (VH , EH )) 1: For all edges e, ϕe ← 0, initially 2: Call a vertex v inactive if ϕv :=

P

e∋v ϕe = 1 and active otherwise; similarly, an edge is active iff both its endpoints are active and inactive otherwise 3: while there exists an active edge and ϕe < ε1 pe for all edges e do 4: Pick minimum δ ∈ (0, 1) such that ϕe ← ϕe + δpe for all e active results in at least one new inactive vertex or ϕe = ε1 pe for some edge e 5: ϕe ← ϕe + δpe for all active edges e 6: end while

Algorithm 2 DistributedWaterFilling(H = (VH , EH ), b = (bv )v∈VH ) 1: For all edges e, ψe ← 0, initially

P

e∋v ψe ≥ 1 − bv and active otherwise; similarly, an edge is active iff both its endpoints are active and inactive otherwise 3: while there exists an active edge do 4: ψe ← ψe + εξ3 for all active edges e 5: end while

2: Call a vertex v inactive if ψv :=

We now proceed to the analysis of the algorithm. Lemma 8. C is a valid vertex cover, and the number of rounds of the distributed phase is O(ξ · 4 ε−1 3 ) = O(1/ε ). 12

Proof. Since in Algorithm 2 Line 4, we increase the weight on the edge by εξ3 in each round, the total number of rounds until a vertex becomes inactive is at most O(ξ ·ε−1 3 ). To see that C is a valid vertex cover, first observe that any edges with an end point in F ∪ B are automatically covered by C. For any e = {u, v} ∈ Q∗ , Algorithm 2 ensures that either ϕv + ψv ≥ 1 or ϕu + ψu ≥ 1. Thus, by definition of C, at least one of u or v are included in C. In the remaining of this section we bound the approximation ratio of the algorithm. Lemma 9. For all e ∈ E, ϕe ≤ ε1 · pe , and, in particular, ϕe = ε1 · pe if e ∩ F = ∅ (i.e., e is still active at the end of Algorithm 1). Proof. Let δi denote the increment δ that the algorithm uses in the ith while-loop iteration, and let t denote the total number of iterations. At the end of the loop, we have for every edge e, ϕe ≤

t X

δi · pe .

i=1

In particular, if e is still active then the above inequality holds as equality. If at the end of the algorithm there is some active edge then by the exit condition of the while loop, and by the way δ is chosen it follows that there is some active edge e satisfying ϕe = ε1 · pe . P It follows that ti=1 δi =Pε1 , in this case. If there is no active edge at the end of the loop, then we similarly conclude that ti=1 δi ≤ ε1 . In both cases the lemma follows. 2 Lemma 10. The maximum degree of subgraph (V, Q∗ ) is at most ξ = 1+ε ε1 .

Proof. If v ∈ F ∪ B then v’s degree in (V, Q∗ ) is zero. Let v ∈ V \ (F ∪ B). Let d be v’s degree in (V, Q∗ ), and let e1 , . . . , ed be its incident edges. For each 1 ≤ i ≤ d, we have ei ∩ F = ∅, thus Lemma 9 implies ϕei = ε1 · pei . Then χv =

X e∋v

χe ≥

d X

χei =

i=1

d X ϕe i=1

i

pei

= d · ε1 .

Also, since v ∈ / B we have χv < ϕv + ε2 ≤ 1 + ε2 , where the second inequality holds because ϕ is valid fractional matching of G. Combining the last 2 two equation gives d ≤ 1+ε ε1 . The statement of the next lemma is similar to [BBD22, Lemma 6.2], but several elements of the proof are different. Lemma 11. There is a fractional matching y = (ye )e∈E ∗ such that E[|C|] ≤ (2 + ϵ) E[|y|], where ϵ ≤ 10ε.

13

(6)

We start with defining our candidate fractional matching y. Let ε4 = ε2 + ε3 . For each e ∈ E ∗ , ye = (χe + ψe ) ·

1 ·1 . 1 + ε4 e∩B=∅

e +ψe That is, ye = 0 if e has an endpoint in B and is χ1+ε otherwise. We also define ye = 0 if e ∈ E \E ∗ . 4

Lemma 12. The candidate fractional matching y is a valid fractional matching. Proof. For all v ∈ B, we have yv = 0, thus satisfying the fractional matching constraints trivially. Let v ∈ / B. Then X χe + ψ e χv + ψv yv ≤ ≤ . 1 + ε4 1 + ε4 e∋v From Algorithm 2, we have that ψv ≤ 1 − ϕv while v is still active, and if v becomes inactive, then in the iteration when v first becomes inactive, ψv increases by at most εξ3 times the degree of v in (V, Q∗ ), which is at most ξ, from Lemma 10. Thus, at the end of Algorithm 2, ψv ≤ 1 − ϕv +

ε3 · ξ = 1 − ϕv + ε 3 . ξ

Also v ∈ / B implies χv ≤ ϕv + ε2 . Substituting these two inequalities above gives yv ≤

1 + ε 2 + ε3 = 1, 1 + ε4

thus v ∈ B satisfies the fractional matching constraint, as well. We define the following set B + ⊇ B, which uses a slightly lower threshold value than B, namely ϕv + ε2 − ε1 instead of ϕv + ε2 , B + = {v ∈ V : χv ≥ ϕv + ε2 − ε1 } . The next lemma establishes a lower bound on E[|y|]. Lemma 13. (1 + ε2 ) · E[|y|] ≥ |ϕ| + E[|ψ|] − E[|B + |]. Proof. We have (1 + ε4 ) · E[|y|] = (1 + ε4 )

X

E[ye ]

e∈E

=

X

E [(χe + ψe ) · 1e∩B=∅ · 1e∈E ∗ ]

e∈E

=

X

χe · P(e ∩ B = ∅ ∧ e ∈ E ∗ ) +

e∈E

=

X X

E [ψe · 1e∩B=∅ · 1e∈E ∗ ]

e∈E ∗

χe · pe · P(e ∩ B = ∅ | e ∈ E ) +

e∈E

=

X

X

E [ψe ]

e∈E

ϕe · (1 − P(e ∩ B ̸= ∅ | e ∈ E ∗ )) + E[|ψ|]

e∈E

= |ϕ| −

X

ϕe · P(e ∩ B ̸= ∅ | e ∈ E ∗ ) + E[|ψ|].

e∈E

14

Next we will use that if e ∋ v then P(v ∈ B | e ∈ E ∗ ) ≤ P(v ∈ B + ), because by Lemma 9, a single edge e can contribute at most ε1 to χv , in the definition of B and B + . We bound the sum in the last line above as follows, X XX ϕe · P(v ∈ B | e ∈ E ∗ ) ϕe · P(e ∩ B ̸= ∅ | e ∈ E ∗ ) ≤ v∈V e∋v

e∈E

≤

XX

ϕe · P(v ∈ B + )

v∈V e∋v

=

X

P(v ∈ B + ) ·

X

ϕe

e∋v

v∈V

≤

X

P(v ∈ B + ) · 1

v∈V

≤ E[|B + |]. Substituting this above completes the proof. We now give an upper bound on E[|C|]. Lemma 14. E[|C|] ≤ 2|ϕ| + 2 E[|ψ|] + E[|B|]. Proof. Recall C = F ∪ B ∪ {v ∈ V : ϕv + ψv ≥ 1}. We have E[|C|] = |F | + E[|B \ F |] + E[|C \ (F ∪ B)|] ≤ |F | + E[|B|] + E[|C \ F |]. Also, from the definition of C it follows X

E[|C \ F |] ≤

E[ϕv + ψv ]

v∈V \F

X

=

ϕv −

v∈V

X

ϕv +

v∈F

X

E[ψv ]

v∈V

= 2|ϕ| − |F | + 2 E[|ψ|]. Substituting this above completes the proof. ε1 Finally, we show an upper bound on E[|B + |]. Recall ε5 = (ε2 −ε 2. 1)

Lemma 15. E[|B|] ≤ E[|B + |] ≤ ε5 · |ϕ|. Proof. The first inequality is immediate from the definition of the two sets. We prove the second inequality. Consider any vertex v ∈ V . Let d be the degree of v in the base graph G, and let e1 , . . . , ed be its incident edges. For 1 ≤ i ≤ d, E[χei ] = and  Var[χei ] =

ϕe i pei

ϕe i · pei = ϕei , pei

2 pei (1 − pei ) ≤

15

ϕ2ei ≤ ε1 ϕei , pei

where the last inequality is obtained using Lemma 9. It follows that E[χv ] = ϕv , and Var[χv ] =

d X

Var[χei ] ≤

i=1

d X

ε1 ϕei = ε1 ϕv .

i=1

Then the probability that vertex v is in B + is P(v ∈ B + ) = P(χv > ϕv + ε2 − ε1 ) ≤ P(|χv − ϕv | > ε2 − ε1 ) Var[χv ] ≤ (ε2 − ε1 )2 ε1 ϕ v ≤ . (ε2 − ε1 )2 Finally, E[|B + |] =

X

P(v ∈ B + ) ≤

v∈V

ε1 · |ϕ| . (ε2 − ε1 )2

From Lemmas 13 and 15, (1 + ε4 ) · E[|y|] ≥ |ϕ| + E[|ψ|] − E[|B + |] ≥ (1 − ε5 ) · |ϕ| + E[|ψ|] ≥ (1 − ε5 ) · (|ϕ| + E[|ψ|]). Similarly, from Lemmas 14 and 15, E[|C|] ≤ 2|ϕ| + 2 E[|ψ|] + E[|B|] ≤ (2 + ε5 ) · (|ϕ| + E[|ψ|]). Combining the two inequalities yields E[|C|] ≤ (2 + ε5 ) ·

1 + ε4 · E[|y|], 1 − ε5

5 )(1+ε4 ) which implies (6), for ϵ = (2+ε1−ε − 2. This completes the proof of Lemma 11. From Lemma 11, 5 it follows that C is a (2 + ϵ)-approximation of the optimal matching of G∗ as argued in [BBD22], since any fractional matching is smaller than the minimum vertex cover.

4

Constant Approximation for Maximum Matching in 2 Rounds

We give an algorithm that finds a matching of G∗ with the following properties. Theorem 3. There is a randomized algorithm for the distributed stochastic maximum matching problem that outputs a 0.39-approximation in two rounds of single-bit messages. If the base graph is bipartite, an improved approximation ratio of 0.63 is achieved. The algorithm takes a matching algorithm proposed in [BBD22] for bipartite graphs and extends it to general graphs. The approximation ratio of that algorithm is 1 − 1/e = 0.63212. Let M be any matching algorithm, and let M(H) denote the output of the algorithm on input graph H. For an edge e = uv, we use notation e − u to denote v. 16

Distributed Algorithm 1. (Preprocessing Stage) The following two tasks are performed by each v ∈ V . (The value of α will be picked suitably later.) (a) Vertex v chooses to be active with probability α, or passive with probability 1 − α. We denote the set of active vertices by A and the set of passive vertices by P . (b) Each v ∈ V communicates its choice to its neighbors in G, and thus it learns its set of active and passive neighbors in G. 2. (First Round) At this stage, each v ∈ V is made aware of NG∗ (v). If v ∈ A, then it may ‘propose’ to at most one neighbor: (a) Each vertex v ∈ A generates a random hallucination G∗v of G as follows. For every edge vu ∈ E(G) where u is passive, vu ∈ E(G∗v ) if and only if vu ∈ E(G∗ ); for every other e ∈ E(G), edge e is added to E(G∗v ) independently with probability pe . (b) Next each v ∈ A locally computes M(G∗v ), and if vu ∈ M(G∗v ) for some u ∈ NG∗ (v), then v sends a proposal to u. 3. (Second Round) In this round, vertices accept or reject proposals they receive: (a) If v ∈ A, then v rejects all proposals it receives. (b) If v ∈ P and v received at least one proposal in the first round, then it accepts an arbitrary one among the proposals, and notifies the sender u. Edge vu is added to the matching M output by the algorithm (and is reported by v and u). The algorithm clearly outputs a matching since each v ∈ A makes a single proposal and rejects all proposals made to it; and each each v ∈ P accepts an arbitrary proposal. Next we analyze the approximation ratio. Although in the algorithm only active vertices v ∈ A hallucinate a graph G∗v , for the analysis we will assume that passive vertices do that as well. Precisely, we assume each v ∈ P generates a random hallucination G∗v by adding each edge e ∈ E(G) to G∗v independently with probability pe . We define now some relevant random variables associated with the algorithm. Definition 16 (Random Variables). We will use the following random variables: 1. For each u ∈ V let Su be the indicator random variable that is 1 if u ∈ A and 0 if u ∈ P . 2. For each e ∈ E(G) let Re be the random variable that is 1 if e is realized in G∗ and 0 otherwise. 3. For each e ∈ E(G) and v ∈ V let Rev be the random variable that is 1 if e is realized in G∗v and 0 otherwise. Lemma 17. All hallucinations G∗v , for v ∈ V , are mutually independent and also independent of the set A of active vertices. Proof. For v ∈ A, consider G∗v . The edges vw ∈ E(G) are of two types: w ∈ P or w ∈ A. In the former case, vw is realized consistently with its status in G∗ . However, G∗ is independent of A and P . Similarly, in the latter case, vw is realized independently with probability pvw . Thus, for all such v ∈ A, G∗v is independent of A. The argument for v ∈ P is similar. In this case, all edges vw ∈ G are realized independently with probability pvw . Thus for all such v ∈ P , G∗v is independent of A. To argue about mutual independence of all G∗v for v ∈ V , we observe the following: 17

• For v ∈ A, E(G∗v ) is determined by {Re }e∈NG∗ (v),e−v∈P and {Rev }e∈NG∗ (v),e−v∈A . • For v ∈ P , E(G∗v ) is determined by {Rev }e∈NG∗ (v) . Thus, each v ∈ V uses disjoint random bits to sample G∗v . Therefore, we can conclude that all G∗v are mutually independent. Lemma 18. The expected size of the matching M computed by the distributed algorithm is E[|M |] ≥ 2(1 − α) · (1 − e−α ) · E[|M(G∗ )|]. Proof. For every vertex v ∈ V , let Ev be the event that v is passive and receives at least one proposal. Then X E[|M |] = P(Ev ). v∈V

For every pair u, v ∈ V , let Xu,v be the indicator random variable of the event u ∈ A ∧ uv ∈ M(G∗u ). Note that the event Ev is the same as the event X v∈P ∧ Xu,v > 0. u∈NG (v)

We have that P(Xu,v = 0) = 1 − P(Xu,v = 1) = 1 − P(u ∈ A ∧ uv ∈ M(G∗u )) = 1 − P(u ∈ A) · P(uv ∈ M(G∗u )) = 1 − α · P(uv ∈ M(G∗ )) ∗

≤ e−α·P(uv∈M(G )) , where in the third line we used that G∗u is independent of A by Lemma 17, and in the fourth line we used that G∗ and G∗u have the same distribution. Moreover, since Xu,v depends only on Su , G∗u , Lemma 17 implies that the random variables Xu,v , for u ∈ NG (v), are mutually independent, and also independent of Sv . Then for every v ∈ V ,   X P(Ev ) = Pv ∈ P ∧ Xu,v > 0 u∈NG (v)



 X

= P(v ∈ P ) · P

Xu,v > 0

u∈NG (v)





= (1 − α) · 1 − P

 X

Xu,v = 0

u∈NG (v)



 Y

= (1 − α) · 1 − 

P(Xu,v = 0)

u∈NG (v) P −α· u∈N

≥ (1 − α) · 1 − e

18

G (v)

P(uv∈M(G∗ ))



,

where in the third line we used that the Xu,v are independent of Sv ; in the second-last line we used that the Xu,v , for u ∈ NG (v), are mutually independent; and in the last line we applied the previous inequality. The sum in the exponent in the last line above equals the probability cv that v is matched in M(G∗ ).Thus,
1 − e−αcv ≥ (1 − α) · cv · (1 − e−α ), P(Ev ) ≥ (1 − α) · 1 − e−αcv = (1 − α) · cv · cv −αx

since the function 1−ex E[|M |] =

X

is decreasing and cv ≤ 1. Thus we have,

P(Ev ) ≥ (1 − α) · (1 − e−α ) ·

v∈V

X

cv = 2(1 − α) · (1 − e−α ) · E[|M(G∗ )|].

v∈V

For α = 1/2, Lemma 18 gives an approximation ratio of 1 − e−1/2 ≈ 0.393469. The optimal choice for α is α = 0.442854, which gives a slightly better approximation ratio 2(1 − α)(1 − e−α ) ≈ 0.398693, which proves Theorem 3.

5

Improved Approximation for Maximum Matching in poly(1/ϵ) Rounds

We give a poly(1/ϵ)-round algorithm that computes a (0.68 − ϵ)-approximation when G is an arbitrary graph. For the case of bipartite graphs, we give a better poly(1/ϵ)-round algorithm that computes a (0.73 − ϵ)-approximation. Theorem 4. There is a randomized algorithm for the distributed stochastic maximum matching problem that outputs a (0.68 − ϵ)-approximation in poly(1/ϵ) rounds of O(log n)-bit messages. If the base graph is bipartite, an improved approximation ratio of (0.73 − ϵ) is achieved. Both results assume that all edges e have the same realization probability pe = p.5 We will use an existing result on distributed algorithms for (1 − δ)-approximate maximum matching. Lemma 19 ([BCGS17]). There is a Congest algorithm B that computes a (1 − δ)-approximation to the maximum matching on any given graph G with maximum degree ∆, in O(poly(1/δ) · logloglog∆∆ ) rounds. We will also use the following statement from [DS25]. Lemma 20 ([DS25, Theorem 1]). Let M be any (potentially randomized) maximum matching algorithm. There exists an algorithm A that picks a subgraph Q of G with maximum degree O( ϵ51p ) such that, E[|M(Q∗ )|] ≥ (0.68 − ϵ) · E[|M(G∗ )|]. For the case when G is bipartite, we can get an improved algorithm A′ that picks a subgraph Q of G with maximum degree O( ϵ51p ) such that E[|M(Q∗ )|] ≥ (0.73 − ϵ) · E[|M(G∗ )|]. 5

This is the only result in this paper in which we make this assumption.

19

We now describe our algorithm ALG which obtains a (0.68 − ϵ)-approximation to E[|M(G∗ )|] in poly(1/ϵ) rounds when G is a general graph. Additionally, ALG obtains a (0.73 − ϵ)-approximation in poly(1/ϵ) when G is bipartite. 1. (Preprocessing Stage) We use A from Lemma 20 to get a subgraph Q of G satisfying the statement of the lemma if A is non-bipartite. Otherwise, we use A′ to pick Q.  1 2. (Distributed Stage) We consider Q∗ , drop all vertices Vbad = v ∈ V | degQ∗ (v) ≥ ϵ10 and ϵ ∗ proceed to run B (guaranteed by Lemma 19) with δ = 2 on Q [V \ Vbad ]. Then, we output the matching M computed by B. Note that E[|M(Q∗ )|] is large compared to E[|M(G∗ )|], but we compute a matching in graph \ Vbad ] to ensure a round complexity that is independent of p. It remains to argue that E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ϵ) · E[|M(Q∗ )|]. This will be the focus of the subsequent lemma. Let 1 θ = ϵ10 . Q∗ [V

Lemma 21. Let ϵ < 21 and let Q be a subgraph of G such that maximum degree of Q is upper bounded by O( ϵ51p ). Suppose Vbad :=

  1 v ∈ V : degQ∗ (v) ≥ 10 . ϵ

Let Xv := degQ∗ (v), for v ∈ V . Then E [|Q∗ [V \ Vbad ]|] ≥ Proof. Note that E[|Q∗ |] = can conclude that

P

v∈V

P

v∈V

E[Xv ] · 2

1 − 8θ .

E[Xv ] and E[Xv ] = ϵ18 (since by Lemma 20, degQ (v) ≤ ϵ81p ). We 2

P(Xv ≥ E[Xv ] + k) ≤

E[Xv ] Var[Xv ] ≤ , 2 k k2

where the last inequality is derived from the fact that Xv is a sum of 0-1 independent random variables. With this in mind, we proceed to bound the term E[Xv · 1Xv ≥θ ]. This term is an upper bound on the expected number of edges incident on Vbad . Consequently, upper bounding this term will let us lower bound E[|Q∗ [V \ Vbad ]|]. We have, X E[Xv · 1Xv ≥θ ] = P(Xv ≥ j) j≥θ

≤

X j≥θ

E[Xv ] (j − E[Xv ])2

(by the discussion above) X E[Xv ] ≤ (j − ϵ2 θ)2 j≥θ

(since E[Xv ] ≤ ϵ2 θ) X X ≤ E[Xv ] · i≥0 j∈[2i θ,2i+1 θ]

≤ E[Xv ] ·

X i≥0

20

1 (2i − ϵ2 )2 θ2

2i θ (2i − ϵ2 )2 θ2

≤ E[Xv ] ·

X i≥0

2i (2i−1 )2 θ

1 (as ϵ < ) 2 4 · E[Xv ] ≤ . θ Thus, we can conclude that ∗

∗

E[|Q [V \ Vbad ]|] ≥ E[|Q |] −

X v∈V

 X E[Xv ]  8 . · 1− E[Xv · 1v≥θ ] ≥ 2 θ v∈V

Our second lemma gives a lower bound E[|M(Q∗ )|]. Lemma 22. Let M be an maximum matching algorithm. Let ϵ < 21 and let Q be a subgraph of G such that maximum degree of Q is upper bounded by O( ϵ51p ). Suppose   1 Vbad := v ∈ V : degQ∗ (v) ≥ 10 . ϵ Then we have that E[|M(Q∗ )|] ≥ E[|M(Q∗ [V \ Vbad ])|] ≥

P

v∈V

E[Xv ]·(1− θ8 ) . 2θ

Proof. We create a matching M of Q∗ [V \ Vbad ] with expected size being equal to the RHS as follows. Initially, M = ∅ and H = Q∗ [V \ Vbad ]. In each step, we consider an arbitrary edge e = uv ∈ H and let M ← M ∪ {e}. Additionally, we update H by removing from H the vertices u, v and all the edges incident on them. We finalize M when H = ∅. Since v ∈ V \ Vbad has P E[Xv ]·(1− θ8 ) degQ∗ (v) ≤ θ, H = ∅ after at least v∈V steps in expectation. Thus, we have, 2θ E[|M(Q∗ )|] ≥ E[|M(Q∗ [V \ Vbad ])|] ≥ E[|M |] ≥

X E[Xv ] · (1 − 8 ) θ

2θ

v∈V

.

Our next lemma bounds |Vbad |. Lemma 23. We have E[|Vbad |] ≤

P     16· v∈V E[Xv ] 32·E[|M(Q∗ )|] 1 ≤ · . 2 8 9θ 9θ 1− θ

Proof. We have P(Xv ≥ θ) ≤

Var[Xv ] E[Xv ] 16 · E[Xv ] ≤ ≤ . 2 2 2 (θ − E[Xv ]) (θ − ϵ θ) 9θ2

The last inequality follows from the fact that ϵ < 21 . Thus, we have, E[|Vbad |] =

X

E[1Xv ≥θ ] ≤

v∈V

16 ·

P

v∈V E[Xv ] ≤ 9θ2

where the last inequality follows from Lemma 22. We can conclude the following.

21



32 · E[|M(Q∗ )|] 9θ

 ·

1 1 − 8θ

! ,

Lemma 24. Let M be any maximum matching algorithm. Let ϵ < 12 and let Q be a subgraph of G such that maximum degree of Q is upper bounded by O( ϵ51p ). Suppose   1 Vbad := v ∈ V : degQ∗ (v) ≥ 10 . ϵ Then, E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ϵ7 ) · E[|M(Q∗ )|] Proof. As a consequence of Lemma 23, we have that E[|M(Q∗ [V \ Vbad ])|] ≥

32 1− · 9θ

1 1 − 8θ

!! · E[|M(Q∗ )|]

≥ 1 − 3.56ϵ10 · 1 + 16ϵ10

· E[|M(Q∗ )|]

(By definition of θ) ≥ (1 − 8ϵ10 ) · E[|M(Q∗ )|] ≥ (1 − ϵ7 ) · E[|M(Q∗ )|] 1 (As ϵ < ). 2 The above completes the proof of our algorithm, as follows. Proof of Theorem 4 (General Graphs). Let ALG be the candidate algorithm. If G is a non-bipartite graph ALG uses A to pick Q, which satisfies the premise of Lemma 24. Thus, we have that E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ϵ7 ) · E[|M(Q∗ )|] Since we run B on Q∗ [V \ Vbad ], with the goal of obtaining a (1 − ϵ/2)-approximate matching, we have, ϵ ϵ E[|M |] ≥ (1 − ) · E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ) · (1 − ϵ7 ) · E[|M(Q∗ )|] ≥ (1 − ϵ) · E[|M(Q∗ )|]. 2 2 By the guarantees on E[|M(Q∗ )|] (from Lemma 20), the approximation ratio follows. The round complexity of the algorithm is O(poly(1/ϵ)). This is implied by the fact that we run algorithm B 1 . (from Lemma 19) on Q∗ [V \ Vbad ] with δ = 2ϵ and Q∗ [V \ Vbad ] has maximum degree ϵ10 Proof of Theorem 4 (Bipartite Graphs). Let ALG be the candidate algorithm. If G is bipartite graph, then ALG runs A′ to pick Q, which satisfies the premise of Lemma 24 and has an approximation guarantee of 0.73 − ϵ. Thus, we have that E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ϵ7 ) · E[|M(Q∗ )|] Since we run B on Q∗ [V \ Vbad ], with the goal of obtaining a (1 − ϵ/2)-approximate matching, we have, ϵ ϵ E[|M |] ≥ (1 − ) · E[|M(Q∗ [V \ Vbad ])|] ≥ (1 − ) · (1 − ϵ7 ) · E[|M(Q∗ )|] ≥ (1 − ϵ) · E[|M(Q∗ )|]. 2 2 By the guarantees on E[|M(Q∗ )|] (from Lemma 20 and using the fact that G is bipartite), the approximation ratio follows. The round complexity of the algorithm is O(poly(1/ϵ)). This is implied by the fact that we run algorithm B (from Lemma 19) on Q∗ [V \ Vbad ] with δ = 2ϵ and 1 Q∗ [V \ Vbad ] has maximum degree ϵ10 . 22

6

Logarithmic Approximation for Minimum Dominating Set

¯ be the maximum expected degree of G∗ , Let ∆ be the maximum degree of base graph G and let ∆ ¯ = max E[degG∗ (v)]. ∆ v

¯ is smaller than the expected maximum degree E[maxv degG∗ (v)]. Note that ∆ ¯ We give an algorithm that finds a dominating set S of G∗ , whose expected size is an O(log ∆)∗ ∗ approximation to that of the optimal solution S for G . Theorem 5. There is a deterministic algorithm for the distributed stochastic minimum dominating ¯ set problem that outputs a O(log ∆)-approximation in a single round of single-bit messages. At a high level, our aim is to mimic the standard greedy algorithm (e.g. [Joh73, Lov75]) for computing a logarithmic approximation to the minimum dominating set. The preprocessing stage computes a ranking of the vertices, such that the ith vertex in the ranking, denoted vi , is the one that in expectation covers the largest number of vertices in G∗ not already covered by the previous i − 1 vertices, v1 , . . . , vi−1 . Then, after G∗ is realized, each vertex chooses its neighbor in G∗ (or itself) with the highest rank, and the set of all chosen vertices is the output of the algorithm. Recall that the textbook analysis of the standard greedy algorithm for a deterministic graph assigns to every vertex covered by the ith vertex u in the greedy dominating set a cost of 1/di , where di is the total number of vertices that u covers (and were not previously covered). Then it is shown that for each vertex v in the optimal dominating set S ∗ , the sum of costs of all vertices Pdeg(v)+1 adjacent to v and including v is at most j=1 = ln deg(v) + O(1). In our algorithm, vertices are ranked according to the expected number of vertices they cover (rather than the actual number). This presents two challenges. On the one hand, there are vertices for which the actual number of vertices they cover is much smaller than expected (thus they have a higher rank than they should); we call such vertices bad. On the other hand, there are vertices for which the actual number of vertices they cover is much larger than expected (thus they have a lower rank than they should); we call such vertices costly. We deal with bad vertices by assigning a cost of zero to the vertices they cover, and showing that the total number of such bad vertices is small (compared to the optimal dominating set size). We deal with costly vertices by assigning a cost of 1 to the vertices they cover, and showing that the total number of vertices covered by costly vertices is small. Below we formally present the algorithm and its analysis. Distributed Algorithm. 1. (Preprocessing stage) Order the vertices of V inductively, as follows. Let V0 = ∅ and for every i = 1, . . . , n let Vi = {v1 , . . . , vi }. Let G̃ be a random hallucination of G. For every i = 1, . . . , n and vertex v, let W̃i (v) be a random variable that represents the set of vertices in G̃ that are covered by v which are not already Q covered by vertices in Vi−1 . The probability of a vertex u ∈ NG (v) to be in W̃i (v) is puv · w∈NG (u)∩Vi−1 (1 − puw ), since we need its edge to v to get sampled in G̃ and its edges toQ any other vertex in Vi to not get sampled. Similarly, the probability of v to be in W̃i (v) is w∈NG (v)∩Vi−1 (1 − pvw ). Let w̃i (v) = E[|W̃i (v)|]. Then Y X Y w̃i (v) = (1 − pvw ) + puv · (1 − puw ). w∈NG (v)∩Vi−1

u∈NG (v)\Vi−1

23

w∈NG (u)∩Vi−1

Let vi be a vertex v that maximizes w̃i (v).6 We say that i is the rank of vertex vi . Note that if i < i′ then w̃i (vi ) ≥ w̃i (vi′ ) ≥ w̃i′ (vi′ ). 2. (Communication round) Each vertex v selects the vertex u ∈ NG∗ (v) ∪ {v} whose rank is minimal and informs u that it is selected. All selected vertices join the dominated set S that the algorithm outputs. It is immediate that S is indeed a dominating set of G∗ , and that the algorithm has the round and message complexity stated in Theorem 5. Next we bound the approximation ratio. For every vertex v ∈ V , let Wi (v) be the set of vertices in G∗ that are covered by v which are not already covered by vertices in Vi−1 = {v1 , . . . , vi−1 }, and let wi (v) = |Wi (v)|. ¯ is larger than a sufficiently large In the following we assume without loss of generality that ∆ ¯ ¯ leaves and constant (as we can artificially increase ∆ by adding to G a disjoint star graphs with ∆ edge realization probabilities that are equal to 1). Definition 25 (Bad Vertices and Costly Vertices). We say that vertex vi is bad if ¯ wi (vi ) < (w̃i (vi ) − 8 ln ∆)/4. We say that vi is costly if there is i′ < i such that ¯ . wi′ (vi ) > 6 · (⌈w̃i′ (vi′ )⌉ + log ∆),

(7)

and denote νi the smallest such i′ . Let B and C denote the set of bad vertices and the set of costly vertices, respectively. First we show that the expected number of bad vertices is small. Lemma 26 (There are not Many Bad Vertices). ¯ 2. E[|B|] ≤ n/∆ ¯ ¯ Proof. Recall that vertex vi is bad if wi (vi ) < (w̃i (vi )−8 ln ∆)/4. Suppose first that w̃i (vi ) ≥ 8 ln ∆. By a Chernoff bound ¯ P(wi (vi ) < (w̃i (vi ) − 8 ln ∆)/4) ≤ P(wi (vi ) < w̃i (vi )/4) 2

≤ e−(3/4) w̃i (vi )/2 ¯ 2, < 1/∆ ¯ If w̃i (vi ) < 8 ln ∆, ¯ the above inequality holds trivially. Thus, it follows that since w̃i (vi ) ≥ 8 ln ∆. 2 ¯ . E[|B|] ≤ n/∆ Next we show that costly vertices do not cover many vertices in expectation. Lemma 27 (Costly Vertices do not Cover Many Vertices). Let dv = degG∗ (v) for any v ∈ V . " # X ¯ 3. E dv ≤ n/∆ v∈C 6

Throughout the algorithm and analysis, we break ties in any arbitrary consistent manner, say, by vertex identifiers.

24

Proof. We define the set ¯ K = {⌈w̃i (vi )⌉ : 1 ≤ i ≤ n} ⊆ {1, . . . , ⌈∆⌉}, ¯ ∈ K and and for each k ∈ K we let jk be the smallest i with ⌈w̃i (vi )⌉ = k. Note that ⌈∆⌉ j⌈∆⌉ ¯ = 1. Observe also that if vi ∈ C then νi = jk for some k ∈ K. Indeed, νi cannot take a value i′ ∈ / {jk : k ∈ K}, since otherwise for the k such that ⌈w̃i′ (vi′ )⌉ = k, we have that jk < i′ and jk also satisfies (7), as replacing i′ by jk leaves the right side of inequality (7) unchanged and can only increase the left side. To simplify notation, we define νi = 0 if vi ∈ / C, so that now each vi ∈ V is associated with a value νi . We have   X X E dvi  = E [dvi · 1vi ∈C ] . vi ∈C

vi ∈V

For each vi ∈ V , X

E [dvi · 1vi ∈C ] =

E[dvi · 1νi =jk ].

k∈K : k≥w̃i (vi )

¯ with k ≥ w̃i (vi ), For any k ∈ K \ {⌈∆⌉} E[dvi · 1νi =jk ] = E[dvi | νi = jk ] · P(νi = jk ) ¯ + log ∆) ¯ · P(νi = jk ) ≤ 6(⌈∆⌉ ¯ + log ∆) ¯ · P(wj (vi ) > 6(k + log ∆)), ¯ ≤ 6(⌈∆⌉ k ¯ imply dv = w1 (vi ) ≤ 6(⌈∆⌉ ¯ + log ∆), ¯ where the first inequality holds because νi = jk and k ̸= ⌈∆⌉ i ¯ and the second inequality holds because νi = jk implies wjk (vi ) > 6(k + log ∆). Similarly, for ¯ k = ⌈∆⌉, we have jk = 1 and E[dvi · 1νi =jk ] = E[dvi · 1dv >6(⌈∆⌉+log ¯ ¯ ] ∆) X i ¯ + log ∆) ¯ · P(dv ≥ 6(⌈∆⌉ ¯ + log ∆)), ¯ ≤ P(dvi > j) + 6(⌈∆⌉ i ¯ ¯ j≥6(⌈∆⌉+log ∆)

¯ + log ∆), ¯ and the where the first equation holds because νi = jk = 1 implies dv1 = w1 (vi ) > 6(⌈∆⌉ second equation is obtained using Lemma 28. Next we bound the probabilities quantities in the last two equation above. We have E[wjk (vi )] ≤ ¯ > 6 · E[wj (vi )], a Chernoff bound gives w̃jk (vjk ) ≤ k, thus for any j ≥ 6(k + log ∆) k P(wjk (vi ) ≥ j) ≤ 2−j . ¯ the above yields a bound for P(dv ≥ j). Substituting to the previous In particular, for k = ⌈∆⌉ i two equations (and performing some simple calculations) gives ¯ 4, E[dvi · 1νi =jk ] < 1/∆ ¯ for both cases, for large enough ∆. Finally, combining the above we obtain   X X E dvi  = E [dvi · 1vi ∈C ] . vi ∈C

vi ∈V

25

=

X

X

E[dvi · 1νi =jk ]

vi ∈V k∈K : k≥w̃i (vi )

¯ · 1/∆ ¯4 ≤ n · ⌈∆⌉ ¯ 3. < n/∆ This completes the proof of Lemma 27. We can now prove the approximation guarantee stated in Theorem 5. Proof of Theorem 5. As mentioned earlier, S is a dominating set of G∗ by construction, and the algorithm has the desired round and message complexity. It remains to analyze the size of S. Let S ∗ be an optimal solution for G∗ . We will show that ¯ · E[|S ∗ |]. E[|S|] = O(log ∆) As in the textbook analysis of the greedy algorithm, we assign to each vertex a cost for covering it by S, but we use a slightly different cost function. We denote by cost(u) the cost for covering a given vertex u. Let vi be the vertex in S that covers u, i.e., vi has the minimum rank i among all vertices in NG∗ (u) ∪ {u}. Then ( 1 if vi ∈ /B wi (vi ) , cost(u) = 0, if vi ∈ B. Then |S| ≤ |B| +

X

cost(v).

(8)

v∈V

Next we lower bound |S ∗ | in terms of the costs, by distinguishing between non-costly and costly vertices. For each vertex v ∈ S ∗ \ C, by similar reasoning as in the standard proof, we get X

X

cost(u) ≤

u∈NG∗ (v)∪{v}

1≤j≤|NG∗ (v)|+1

1 ¯ max{1, (j − 8 ln ∆)/2}

¯ = O(log(|NG∗ (v)| + 1) + log ∆) ¯ = O(log ∆), ¯ since v ∈ / C. For any vertex v ∈ S ∗ ∩ C, where for the last equation we used that |NG∗ (v)| = O(∆) we use the trivial bound X cost(u) ≤ degG∗ (v) + 1. u∈NG∗ (v)∪{v}

Combining the above two cases yields X X cost(u) ≤ v∈S ∗ u∈NG∗ (v)∪{v}

X

¯ (degG∗ (v) + 1) + |S ∗ | · O(log ∆).

v∈S ∗ ∩C

From that and the bound on |S| we computed earlier in (8), we have X |S| ≤ |B| + cost(v) v∈V

26

≤ |B| +

X

X

cost(u)

v∈S ∗ u∈NG∗ (v)∪{v}

≤ |B| +

X

¯ (degG∗ (v) + 1) + |S ∗ | · O(log ∆),

v∈S ∗ ∩C

where the second inequality holds because S ∗ is a dominating set and thus must cover all vertices. Taking the expectation and applying Lemmas 26 and 27 gives ¯ 2 + 2n/∆ ¯ 3 + E[|S ∗ |] · O(log ∆). ¯ E[|S|] ≤ n/∆ To complete the proof we observe that P n n − v∈S ∗ ∩C (degG∗ (v) + 1) ∗ E[|S |] ≥ = Ω ¯ + log ∆) ¯ , 6(⌈∆⌉ ∆ where the first inequality holds because all vertices not covered by costly vertices in S ∗ must be ¯ + log ∆); and to obtain the second equation we apply covered by vertices of degree at most 6(⌈∆⌉ ¯ again Lemma 27. Combining the last two equations gives E[|S|] ≤ E[|S ∗ |] · O(log ∆).

Acknowledgments The authors are grateful to Dimitrios Los for several valuable discussions during the course of this work. The authors also thank the organizers of Dagstuhl Seminar 24471 “Graph Algorithms: Distributed Meets Dynamic”, where preliminary discussions regarding this work took place. Keren Censor-Hillel was supported in part by the Israel Science Foundation, grant No. 529/23. Aditi Dudeja was supported by the Austrian Science Fund (FWF): P 32863-N. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 947702). The project has also received funding from the Inria Associate Team DAME.

References [AAPR23]

Akanksha Agrawal, John Augustine, David Peleg, and Srikkanth Ramachandran. Local recurrent problems in the SUPPORTED model. In 27th International Conference on Principles of Distributed Systems, OPODIS, pages 22:1–22:19, 2023. doi:10.4230/LIPICS.OPODIS.2023. 22.

[AB19]

Sepehr Assadi and Aaron Bernstein. Towards a unified theory of sparsification for matching problems. In 2nd Symposium on Simplicity in Algorithms, SOSA, pages 11:1–11:20, 2019. doi:10.4230/OASICS.SOSA.2019.11.

[ABGR25]

Amir Azarmehr, Soheil Behnezhad, Alma Ghafari, and Ronitt Rubinfeld. Stochastic matching via in-n-out local computation algorithms. In 57th ACM Symposium on Theory of Computing, STOC, pages 1055–1066, 2025. doi:10.1145/3717823.3718279.

[ABI86]

Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms, 7(4):567–583, 1986. doi:10.1016/ 0196-6774(86)90019-2.

[ACKP21]

Amir Abboud, Keren Censor-Hillel, Seri Khoury, and Ami Paz. Smaller cuts, higher lower bounds. ACM Trans. Algorithms, 17(4):30:1–30:40, 2021. doi:10.1145/3469834.

[ÅFP+ 09]

Matti Åstrand, Patrik Floréen, Valentin Polishchuk, Joel Rybicki, Jukka Suomela, and Jara Uitto. A local 2-approximation algorithm for the vertex cover problem. In 23rd International Symposium on Distributed Computing, DISC, pages 191–205, 2009. doi:10.1007/ 978-3-642-04355-0\_21.

27

[AKL17]

Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem: Beating half with a non-adaptive algorithm. In 2017 ACM Conference on Economics and Computation, EC, pages 99–116, 2017. doi:10.1145/3033274.3085146.

[AKL19]

Sepehr Assadi, Sanjeev Khanna, and Yang Li. The stochastic matching problem with (very) few queries. ACM Trans. Economics and Comput., 7(3):16:1–16:19, 2019. doi:10.1145/3355903.

[AKO18]

Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. Distributed approximate maximum matching in the CONGEST model. In 32nd International Symposium on Distributed Computing, DISC, pages 6:1–6:17, 2018. doi:10.4230/LIPICS.DISC.2018.6.

[ALH+ 23]

Ioannis Anagnostides, Christoph Lenzen, Bernhard Haeupler, Goran Zuzic, and Themis Gouleakis. Almost universally optimal distributed laplacian solvers via low-congestion shortcuts. Distributed Comput., 36(4):475–499, 2023. doi:10.1007/S00446-023-00454-0.

[ÅS10]

Matti Åstrand and Jukka Suomela. Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In 22nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pages 294–302, 2010. doi:10.1145/1810479.1810533.

[BBBO24]

Alkida Balliu, Thomas Boudier, Sebastian Brandt, and Dennis Olivetti. Tight lower bounds in the supported LOCAL model. In 43rd ACM Symposium on Principles of Distributed Computing, PODC, pages 95–105, 2024. doi:10.1145/3662158.3662798.

[BBD22]

Soheil Behnezhad, Avrim Blum, and Mahsa Derakhshan. Stochastic vertex cover with few queries. In 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1808–1846, 2022. doi:10.1137/1.9781611977073.73.

[BBK+ 25]

Alkida Balliu, Sebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, and Jukka Suomela. Distributed computation with local advice. In 39th International Symposium on Distributed Computing, DISC, pages 12:1–12:19, 2025. doi: 10.4230/LIPICS.DISC.2025.12.

[BCD+ 19]

Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf, and Ami Paz. Hardness of distributed optimization. In 2019 ACM Symposium on Principles of Distributed Computing, PODC, pages 238–247, 2019. doi:10.1145/3293611.3331597.

[BCGS17]

Reuven Bar-Yehuda, Keren Censor-Hillel, Mohsen Ghaffari, and Gregory Schwartzman. Distributed approximation of maximum independent set and maximum matching. In ACM Symposium on Principles of Distributed Computing, PODC, pages 165–174, 2017. doi: 10.1145/3087801.3087806.

[BCS17]

Reuven Bar-Yehuda, Keren Censor-Hillel, and Gregory Schwartzman. A Distributed (2 + ϵ)Approximation for Vertex Cover in O(log ∆ / ϵ log log ∆) Rounds. J. ACM, 64(3):23:1–23:11, 2017. doi:10.1145/3060294.

[BD20]

Soheil Behnezhad and Mahsa Derakhshan. Stochastic weighted matching: (1-ϵ) approximation. In 61st IEEE Symposium on Foundations of Computer Science, FOCS, pages 1392–1403, 2020. doi:10.1109/FOCS46700.2020.00131.

[BDF+ 19]

Soheil Behnezhad, Mahsa Derakhshan, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic matching on uniformly sparse graphs. In 12th International Symposium on Algorithmic Game Theory, SAGT, pages 357–373, 2019. doi:10.1007/ 978-3-030-30473-7\_24.

[BDH+ 15]

Avrim Blum, John P. Dickerson, Nika Haghtalab, Ariel D. Procaccia, Tuomas Sandholm, and Ankit Sharma. Ignorance is almost bliss: Near-optimal stochastic matching with few queries. In Sixteenth ACM Conference on Economics and Computation, EC, pages 325–342, 2015. doi:10.1145/2764468.2764479.

[BDH20]

Soheil Behnezhad, Mahsa Derakhshan, and MohammadTaghi Hajiaghayi. Stochastic matching with few queries: (1-ϵ) approximation. In 52nd ACM SIGACT Symposium on Theory of Computing, STOC, pages 1111–1124, 2020. doi:10.1145/3357713.3384340.

28

[BEKS18]

Ran Ben-Basat, Guy Even, Ken-ichi Kawarabayashi, and Gregory Schwartzman. A deterministic distributed 2-approximation for weighted vertex cover in O(log n log ∆/ log2 log ∆) rounds. In 25th International Colloquium on Structural Information and Communication Complexity, SIROCCO, pages 226–236, 2018. doi:10.1007/978-3-030-01325-7\_21.

[BEL25]

Joan Boyar, Faith Ellen, and Kim S. Larsen. Distributed graph algorithms with predictions. CoRR, abs/2501.05267, 2025. arXiv:2501.05267, doi:10.48550/ARXIV.2501.05267.

[BEPS12]

Leonid Barenboim, Michael Elkin, Seth Pettie, and Johannes Schneider. The locality of distributed symmetry breaking. In 53rd IEEE Symposium on Foundations of Computer Science, FOCS, pages 321–330, 2012. doi:10.1109/FOCS.2012.60.

[BFHR19]

Soheil Behnezhad, Alireza Farhadi, MohammadTaghi Hajiaghayi, and Nima Reyhani. Stochastic matching with few queries: New algorithms and tools. In Thirtieth ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 2855–2874, 2019. doi:10.1137/1.9781611975482.177.

[BKK+ 23]

Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, and Jara Uitto. Sinkless orientation made simple. In 2023 Symposium on Simplicity in Algorithms, SOSA, pages 175–191, 2023. doi:10.1137/1.9781611977585.CH17.

[BKS19]

Ran Ben-Basat, Ken-ichi Kawarabayashi, and Gregory Schwartzman. Parameterized distributed algorithms. In 33rd International Symposium on Distributed Computing, DISC, pages 6:1–6:16, 2019. doi:10.4230/LIPICS.DISC.2019.6.

[BR18]

Soheil Behnezhad and Nima Reyhani. Almost optimal stochastic weighted matching with few queries. In 2018 ACM Conference on Economics and Computation, EC, pages 235–249, 2018. doi:10.1145/3219166.3219226.

[CD21]

Keren Censor-Hillel and Michal Dory. Distributed spanner approximation. SIAM J. Comput., 50(3):1103–1147, 2021. doi:10.1137/20M1312630.

[Cho94]

Kwok P. Choi. On the medians of gamma distributions and an equation of Ramanujan. Proceedings of the American Mathematical Society, 121(1):245–251, 1994. doi:10.1090/ S0002-9939-1994-1195477-8.

[CS22]

Yi-Jun Chang and Hsin-Hao Su. Narrowing the LOCAL-CONGEST gaps in sparse networks via expander decompositions. In 2022 ACM Symposium on Principles of Distributed Computing, PODC, pages 301–312, 2022. doi:10.1145/3519270.3538423.

[DDH23]

Mahsa Derakhshan, Naveen Durvasula, and Nika Haghtalab. Stochastic minimum vertex cover in general graphs: A 3/2-approximation. In 55th ACM Symposium on Theory of Computing, STOC, pages 242–253, 2023. doi:10.1145/3564246.3585230.

[DF23]

Mahsa Derakhshan and Alireza Farhadi. Beating (1 - 1/e)-approximation for weighted stochastic matching. In 2023 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 1931– 1961, 2023. doi:10.1137/1.9781611977554.CH74.

[DGI24]

Michal Dory, Mohsen Ghaffari, and Saeed Ilchi. Near-optimal distributed dominating set in bounded arboricity graphs. Distributed Comput., 37(4):387–398, 2024. doi:10.1007/ S00446-023-00447-Z.

[DKM19]

Janosch Deurer, Fabian Kuhn, and Yannic Maus. Deterministic distributed dominating set approximation in the CONGEST model. In 2019 ACM Symposium on Principles of Distributed Computing, PODC, pages 94–103, 2019. doi:10.1145/3293611.3331626.

[DKP23]

Shaddin Dughmi, Yusuf Hakan Kalayci, and Neel Patel. On sparsification of stochastic packing problems. In 50th International Colloquium on Automata, Languages, and Programming, ICALP, pages 51:1–51:17, 2023. doi:10.4230/LIPICS.ICALP.2023.51.

[DS25]

Mahsa Derakhshan and Mohammad Saneian. Query efficient weighted stochastic matching. In 52nd International Colloquium on Automata, Languages, and Programming, ICALP, pages 67:1–67:20, 2025. doi:10.4230/LIPICS.ICALP.2025.67.

29

[DSX25]

Mahsa Derakhshan, Mohammad Saneian, and Zhiyang Xun. Query complexity of stochastic minimum vertex cover. In 16th Innovations in Theoretical Computer Science Conference, ITCS, pages 41:1–41:12, 2025. doi:10.4230/LIPICS.ITCS.2025.41.

[FFK21]

Salwa Faour, Marc Fuchs, and Fabian Kuhn. Distributed CONGEST approximation of weighted vertex covers and matchings. In 25th International Conference on Principles of Distributed Systems, OPODIS, pages 17:1–17:20, 2021. doi:10.4230/LIPICS.OPODIS.2021.17.

[FGG+ 23]

Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and Václav Rozhon. Local distributed rounding: Generalized to mis, matching, set cover, and beyond. In 2023 ACMSIAM Symposium on Discrete Algorithms, SODA, pages 4409–4447, 2023. doi:10.1137/1. 9781611977554.CH168.

[FGIP09]

Pierre Fraigniaud, Cyril Gavoille, David Ilcinkas, and Andrzej Pelc. Distributed computing with advice: information sensitivity of graph coloring. Distributed Comput., 21(6):395–403, 2009. doi:10.1007/S00446-008-0076-Y.

[FHSS19]

Klaus-Tycho Foerster, Juho Hirvonen, Stefan Schmid, and Jukka Suomela. On the power of preprocessing in decentralized network optimization. In 2019 IEEE Conference on Computer Communications, INFOCOM, pages 1450–1458, 2019. doi:10.1109/INFOCOM.2019.8737382.

[Fis17]

Manuela Fischer. Improved deterministic distributed matching via rounding. In 31st International Symposium on Distributed Computing, DISC, pages 17:1–17:15, 2017. doi: 10.4230/LIPICS.DISC.2017.17.

[Fis20]

Manuela Fischer. Improved deterministic distributed matching via rounding. Distributed Comput., 33(3-4):279–291, 2020. doi:10.1007/S00446-018-0344-4.

[FK20]

Salwa Faour and Fabian Kuhn. Approximating bipartite minimum vertex cover in the CONGEST model. In 24th International Conference on Principles of Distributed Systems, OPODIS, pages 29:1–29:16, 2020. doi:10.4230/LIPICS.OPODIS.2020.29.

[FKL10]

Pierre Fraigniaud, Amos Korman, and Emmanuelle Lebhar. Local MST computation with short advice. Theory Comput. Syst., 47(4):920–933, 2010. doi:10.1007/S00224-010-9280-9.

[FKP+ 21]

Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid. Inputdynamic distributed algorithms for communication networks. Proc. ACM Meas. Anal. Comput. Syst., 5(1):06:1–06:33, 2021. doi:10.1145/3447384.

[FKRS19]

Klaus-Tycho Foerster, Janne H. Korhonen, Joel Rybicki, and Stefan Schmid. Does preprocessing help under congestion? In 2019 ACM Symposium on Principles of Distributed Computing, PODC, pages 259–261, 2019. doi:10.1145/3293611.3331581.

[FMU22]

Manuela Fischer, Slobodan Mitrovic, and Jara Uitto. Deterministic (1+ϵ)-approximate maximum matching with poly(1/ϵ) passes in the semi-streaming model and beyond. In 54th ACM SIGACT Symposium on Theory of Computing, STOC, pages 248–260, 2022. doi: 10.1145/3519935.3520039.

[GK18]

Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing, DISC, pages 29:1–29:17, 2018. doi:10.4230/LIPICS.DISC.2018.29.

[GKP08]

Fabrizio Grandoni, Jochen Könemann, and Alessandro Panconesi. Distributed weighted vertex cover via maximal matchings. ACM Trans. Algorithms, 5(1):6:1–6:12, 2008. doi:10.1145/ 1435375.1435381.

[GS14]

Mika Göös and Jukka Suomela. No sublogarithmic-time approximation scheme for bipartite vertex cover. Distributed Comput., 27(6):435–443, 2014. doi:10.1007/S00446-013-0194-Z.

[GV06]

Michel X. Goemans and Jan Vondrák. Covering minimum spanning trees of random subgraphs. Random Struct. Algorithms, 29(3):257–276, 2006. doi:10.1002/RSA.20115.

30

[HKP01]

Michal Hanckowiak, Michal Karonski, and Alessandro Panconesi. On the distributed complexity of computing maximal matchings. SIAM J. Discret. Math., 15(1):41–57, 2001. doi:10.1137/S0895480100373121.

[HS23]

Shang-En Huang and Hsin-Hao Su. (1-ϵ)-approximate maximum weighted matching in poly(1/ϵ, log n) time in the distributed and parallel settings. In 2023 ACM Symposium on Principles of Distributed Computing, PODC, pages 44–54, 2023. doi:10.1145/3583668.3594570.

[HWZ21]

Bernhard Haeupler, David Wajc, and Goran Zuzic. Universally-optimal distributed algorithms for known topologies. In 53rd ACM SIGACT Symposium on Theory of Computing, STOC, pages 1166–1179, 2021. doi:10.1145/3406325.3451081.

[II86]

Amos Israeli and Alon Itai. A fast and simple randomized parallel algorithm for maximal matching. Inf. Process. Lett., 22(2):77–80, 1986. doi:10.1016/0020-0190(86)90144-4.

[IKY24]

Taisuke Izumi, Naoki Kitamura, and Yutaro Yamaguchi. A nearly linear-time distributed algorithm for exact maximum matching. In 2024 ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 4062–4082, 2024. doi:10.1137/1.9781611977912.141.

[Joh73]

David S. Johnson. Approximation algorithms for combinatorial problems. In 5th ACM Symposium on Theory of Computing, STOC, pages 38–49. ACM, 1973. doi:10.1145/800125. 804034.

[JRS02]

Lujun Jia, Rajmohan Rajaraman, and Torsten Suel. An efficient distributed algorithm for constructing small dominating sets. Distributed Comput., 15(4):193–205, 2002. doi:10.1007/ S00446-002-0078-0.

[KI22]

Naoki Kitamura and Taisuke Izumi. A subquadratic-time distributed algorithm for exact maximum matching. IEICE Trans. Inf. Syst., 105-D(3):634–645, 2022. doi:10.1587/TRANSINF. 2021EDP7083.

[KMW04]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. What cannot be computed locally! In Twenty-Third ACM Symposium on Principles of Distributed Computing, PODC, pages 300– 309, 2004. doi:10.1145/1011767.1011811.

[KMW06]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. The price of being near-sighted. In Seventeenth ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 980–989, 2006. doi:10.1145/1109557.1109666.

[KMW16]

Fabian Kuhn, Thomas Moscibroda, and Roger Wattenhofer. Local computation: Lower and upper bounds. J. ACM, 63(2):17:1–17:44, 2016. doi:10.1145/2742012.

[KPR+ 21]

Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela. Brief announcement: Sinkless orientation is hard also in the supported LOCAL model. In 35th International Symposium on Distributed Computing, DISC, pages 58:1–58:4, 2021. doi: 10.4230/LIPICS.DISC.2021.58.

[KR17]

Janne H. Korhonen and Joel Rybicki. Deterministic subgraph detection in broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems, OPODIS, pages 4:1–4:16, 2017. doi:10.4230/LIPICS.OPODIS.2017.4.

[KVY94]

Samir Khuller, Uzi Vishkin, and Neal E. Young. A primal-dual parallel approximation technique applied to weighted set and vertex covers. J. Algorithms, 17(2):280–289, 1994. doi:10.1006/JAGM.1994.1036.

[KW05]

Fabian Kuhn and Roger Wattenhofer. Constant-time distributed dominating set approximation. Distributed Comput., 17(4):303–310, 2005. doi:10.1007/S00446-004-0112-5.

[KY09]

Christos Koufogiannakis and Neal E. Young. Distributed and parallel algorithms for weighted vertex cover and other covering problems. In 28th ACM Symposium on Principles of Distributed Computing, PODC, pages 171–179, 2009. doi:10.1145/1582716.1582746.

31

[Lov75]

László Lovász. On the ratio of optimal integral and fractional covers. Discret. Math., 13(4):383– 390, 1975. doi:10.1016/0012-365X(75)90058-8.

[LPP15]

Zvi Lotker, Boaz Patt-Shamir, and Seth Pettie. Improved distributed approximate matching. J. ACM, 62(5):38:1–38:17, 2015. doi:10.1145/2786753.

[LPR09]

Zvi Lotker, Boaz Patt-Shamir, and Adi Rosén. Distributed approximate matching. SIAM J. Comput., 39(2):445–460, 2009. doi:10.1137/080714403.

[Lub85]

Michael Luby. A simple parallel algorithm for the maximal independent set problem. In 17th ACM Symposium on Theory of Computing, STOC, pages 1–10, 1985. doi:10.1145/22145. 22146.

[MS25]

Slobodan Mitrovic and Wen-Horng Sheu. A framework for boosting matching approximation: parallel, distributed, and dynamic. CoRR, abs/2503.01147, 2025. doi:10.48550/ARXIV.2503. 01147.

[MSW21]

Adir Morgan, Shay Solomon, and Nicole Wein. Algorithms for the minimum dominating set problem in bounded arboricity graphs: Simpler, faster, and combinatorial. In 35th International Symposium on Distributed Computing, DISC, pages 33:1–33:19, 2021. doi: 10.4230/LIPICS.DISC.2021.33.

[MY20]

Takanori Maehara and Yutaro Yamaguchi. Stochastic packing integer programs with few queries. Math. Program., 182(1):141–174, 2020. doi:10.1007/S10107-019-01388-X.

[PR01]

Alessandro Panconesi and Romeo Rizzi. Some simple distributed algorithms for sparse networks. Distributed Comput., 14(2):97–100, 2001. doi:10.1007/PL00008932.

[PS09]

Valentin Polishchuk and Jukka Suomela. A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett., 109(12):642–645, 2009. doi:10.1016/J.IPL.2009.02.017.

[SS13]

Stefan Schmid and Jukka Suomela. Exploiting locality in distributed SDN control. In Second ACM SIGCOMM Workshop on Hot Topics in Software Defined Networking, HotSDN 2013, pages 121–126, 2013. doi:10.1145/2491185.2491198.

[vdBGP+ 26] Jan van den Brand, Inge Li Gørtz, Chirag Pabbaraju, Debmalya Panigrahi, Clifford Stein, Miltiadis Stouras, Ola Svensson, and Ali Vakilian. An optimal algorithm for stochastic vertex cover. CoRR, abs/2603.27795, 2026. doi:10.48550/arXiv.2603.27795. [Von07]

Jan Vondrák. Shortest-path metric approximation for random subgraphs. Random Struct. Algorithms, 30(1-2):95–104, 2007. doi:10.1002/RSA.20150.

[WW04]

Mirjam Wattenhofer and Roger Wattenhofer. Distributed weighted matching. In 18th International Symposium on Distributed Computing, DISC, pages 335–348, 2004. doi:10.1007/ 978-3-540-30186-8\_24.

A

Appendix

The following is a simple generalization of a standard formula for the expectation on an integer non-negative random variable. Lemma 28. If X is a non-negative integer random variable and ℓ a non-negative integer then X E[X · 1X≥ℓ ] = P(X > ℓ′ ) + ℓ · P(X ≥ ℓ). ℓ′ ≥ℓ

32