CS Paper Radar

Counting in Population Protocols on Graphs

Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Thorsten Götte, Lukas Hintze, Dominik Kaaser

cs.DC ·submitted 2026-08-18 09:53 UTC · v1
published

Abstract

We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph $G=(V,E)$ with $|V|=n$ nodes. In each step, a random scheduler selects an edge uniformly at random, and the incident nodes make a state transition. As per standard assumptions, agents are identical and anonymous, that is, have no identifiers. To break symmetry, in each interaction one of the agents is declared as the initiator uniformly at random. Our size counting protocol uses $\tilde O(n)$ states and stabilizes in $O( B(G) \cdot \log^2(n) + L(G) \cdot \log(n))$ interactions with high probability, where $B(G)$ is the broadcast time and $L(G)$ is the load balancing time. Our protocol is based on novel protocols for sampling independent random bits (given that the scheduler determines an initiator and responder) and approximating $\log n$ up to an additive error of $O(\log \log n)$ with high probability. The latter uses $O(poly\log(n))$ states and $O(B(G)\cdot\log^2 n)$ interactions. Both results may be of independent interest. The main protocol for exact counting requires the presence of a unique leader, the other two do not. None of the protocols requires any knowledge about the graph $G$. We conclude with impossibility results for terminating uniform population protocols that compute graph-size properties (like counting nodes or determining parity) with and without a leader.

Comment
Accepted to DISC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise Intractability

cs.DC ·2026-11-01 ·Giuseppe A. Di Luna, Giovanni Viglietta
theory similarity 0.67
Abstract · 37 pages, 3 figures

We determine the exact round complexity of Counting in anonymous directed dynamic networks. Agents have no identifiers, but $\ell\geq1$ of them are designated as leaders. Every agent knows $\ell$ and its own leader status, while the population size $n$ is unknown and has to be determined by the agents. Communication proceeds in synchronous rounds; the directed communication graph may change arbitrarily and unpredictably from one round to the next, but is assumed to remain strongly connected. We solve Counting with a distributed algorithm that makes every agent output $n$ and halt after a number of rounds equal to $\begin{cases} n&\text{if }n=\ell\\ 2n-1&\text{if }n>\ell\text{ and }\ell=1\\ 2n-2&\text{if }n>\ell\text{ and }\ell\geq2. \end{cases}$ The algorithm works even for networks with loops and parallel arcs and even when agents learn their outdegree only after sending. We prove that this bound is worst-case tight over directed multigraphs for every $n$ and $\ell$ with $1\leq\ell\leq n$. Moreover, the local computation is polynomial (provided that each communication multigraph has at most $2^{\operatorname{poly}(n)}$ arcs): in every round, each agent solves at most one linear system with up to $n$ variables. By standard techniques, solving Counting also enables the evaluation of any computable function of the multiset of agents' input values within $2n-1$ communication rounds. The bound above optimizes the worst case over all networks. For an individual network, we show that even deciding whether an agent already has enough local information to determine $n$ is $\mathsf{coNP}$-complete (provided that the numbers of parallel arcs are encoded in binary). Thus, worst-case-optimal Counting admits polynomial local computation, whereas exact network-wise optimization is intractable under standard complexity assumptions.

0.21

A Few Shared Random Bits Suffice for Constant-Round Almost Stable Matching

cs.DC ·2026-08-25 ·Yi-Jun Chang, Kushagra Chatterjee
similarity 0.66
Abstract

We show that almost stable matching can be solved in constant distributed rounds on general bipartite graphs $G=(V,E)$ using only a few shared random bits. Specifically, in the $\congest$ model, we compute a matching whose expected number of blocking pairs is at most $\varepsilon |E|$ in $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$ rounds using $O\left(\log(1/\varepsilon)\right)$ shared random bits. Thus, for every constant $\varepsilon>0$, the round complexity is $O(1)$, independent of the number of vertices and the maximum degree. Previous algorithms achieve constant round complexity only for bounded-degree or almost-regular graphs; on general graphs, their round complexity depends polylogarithmically on $n$. Our main technical idea is a degree-guarded freezing rule that allows widely varying degrees to be handled by a single global charging argument, avoiding the $Θ(\log n)$ successive degree thresholds used in previous work. The shared random bits are used only to select a common random output iteration. As consequences, we obtain an $O\left( \frac{\log(1/\varepsilon)}{\varepsilon^4} + \frac{\log n}{\varepsilon} \right)$-round $\congest$ algorithm without pre-shared randomness, via a low-diameter decomposition, and an $O\left(\frac{\log(1/\varepsilon)}{\varepsilon^4}\right)$-round algorithm in the fully-scalable Massively Parallel Computation ($\mpc$) model with linear total memory.

0.08

Contention Resolution Against an Adversarial Scheduler

cs.DS ·2026-11-06 ·Michael A. Bender, Martín Farach-Colton, Andrew Krapivin, Pritom Kundu, John Kuszmaul +3 more
theory similarity 0.64
Abstract · 15 pages

In the classical contention-resolution problem, a set of players share a broadcast channel, and a player succeeds in a given time step if it is the only player to broadcast during that step. Implicit in the classical problem is the assumption that every player is free to act on every step: once a player arrives, it participates until it succeeds. We study what happens when that assumption is removed. In our model, an adversarial \emph{scheduler} decides, on each step, which subset of the players gets scheduled to participate in the step. An unscheduled player simply sleeps through the step. We measure a protocol by its \emph{efficiency}: the number of players divided by the expected number of steps in which at least one player was active. Our first result says that, so long as the players are given access to a global clock and to shared randomness, they can achieve efficiency $Ω(1/\log n)$. The players are able to achieve this bound without requiring any channel feedback, and even if the adversarial scheduler is adaptive. We also give a matching lower bound of $O(1 / \log n)$, which holds even with channel feedback, and even for an oblivious scheduler. Our upper bounds all require the players to have access to a shared global clock and to shared randomness. Our final result says that this type of implicit shared state is necessary. If the players have neither a global clock nor shared randomness, then no protocol can achieve efficiency better than $O(\log n / n)$; and this holds even if the other aspects of the problem are designed to be as favorable for the players as possible (the channel gives ternary feedback and the adversary is oblivious).

0.26

Fast Distributed $(Δ+ 1)$-Edge Coloring in Bipartite Graphs

cs.DC cs.DS ·2026-10-15 ·Yann Bourreau, Sebastian Brandt, Ananth Narayanan
theoryhot direction similarity 0.64
Abstract

We show that, on bipartite $n$-vertex graphs in the LOCAL model of distributed computation, $(Δ+ 1)$-edge coloring can be solved deterministically in $O(f(Δ) \log n)$ rounds for some function $f$. In particular this implies a deterministic $O(\log n)$-round upper bound for $(Δ+ 1)$-edge coloring on bipartite constant-degree graphs. Our results improve on the previous state-of-the-art bounds (which hold already on general graphs) whose $n$-dependencies are $\widetilde{O}(\log^5 n)$ rounds deterministically and $\widetilde{O}(\log^2 n)$ rounds randomized [Bernshteyn and Dhawan, J.\ Comb.\ Theory 2025]. In fact, we obtain the aforementioned results already for a more restrictive version of $(Δ+ 1)$-edge coloring that corresponds to a \emph{local-palette} strengthening of Vizing's theorem shown recently to hold [Christiansen, STOC 2023]. In this version, every edge $\{u, v\}$ has to be colored with a color from $\{1, \dots, \max(\operatorname{deg}(u), \operatorname{deg}(v))+ 1\}$. For all of our results, the vertices do not need to know on which side of the bipartition they lie---the structural promise of bipartiteness suffices.

0.21

Settling Nondeterministic Communication Complexity of Graph Connectivity

cs.CC ·2026-10-23 ·Zhijun Zhang
publishedtheory similarity 0.62
Abstract

Determining the communication complexity of graph connectivity has been one of the longest standing open problems in communication complexity since the seminal work of Babai, Frankl, and Simon [FOCS'86]. A simple protocol transmits a spanning forest using $O(N\log N)$ communication on $N$-vertex graphs. While this was shown optimal for deterministic protocols by Hajnal, Maass, and Turán [STOC'88], the optimal nondeterministic and randomized complexities have remained unresolved for decades. We settle the nondeterministic communication complexity of graph connectivity by proving an optimal $Ω(N\log N)$ lower bound. The best prior bound was $Ω(N\log\log N)$ due to Raz and Spieker [Combinatorica'95]. Our bound is shown by upper bounding the maximum size of $1$-monochromatic rectangles. Generalizing our techniques to weighted, almost $1$-monochromatic rectangles yields an $Ω(N \cdot \log(\min(1/\varepsilon,N)))$ lower bound for randomized protocols with error probability $\varepsilon$. In particular, this bound is optimal for any polynomially small $\varepsilon$. For constant error probability, we also prove that any $r$-round protocol requires $Ω(N/r \cdot \log N)$ communication, which is optimal for every constant $r$. Previously, optimal $Ω(N\log N)$ lower bounds for graph connectivity were known only for $1$-round [Sun, Woodruff; APPROX/RANDOM'15] and $2$-round protocols [Radhakrishnan, Reddy, Venkat; ITCS'26]. Our proof introduces a new communication problem which can be viewed as a composition of inner product and pointer chasing problems. Our lower bounds can be extended to other fundamental graph properties, and also imply optimality of known query and streaming algorithms for related problems.

0.31

Deterministic Connectivity Sketches Under Edge Deletions

cs.DS ·2026-11-04 ·Sanjeev Khanna, Aaron Putterman, Madhu Sudan
theory similarity 0.62
Abstract

How much information about a graph is needed to determine its connectivity after arbitrary valid edge deletions? This question is at the heart of designing deterministic dynamic streaming algorithms for graph connectivity. Towards answering this question, we study the deterministic one-way communication problem in which Alice holds a graph $G_A = (V, E_A)$ on $n$ vertices, Bob holds a graph $G_B = (V, E_B)$ with $E_B \subseteq E_A$, and Alice sends a message $M \in \{0,1\}^m$ that allows Bob to decide whether $G_A - G_B$ is connected. Randomized sketches solve this problem using $\tilde O(n)$ bits, whereas deterministic recovery of even one surviving edge requires $Ω(n^2)$ bits. We prove an upper bound of $m = \widetilde{O}(n^{7/4})$ bits and a lower bound of $m = \widetildeΩ(n^{3/2})$ bits for deciding connectivity. Thus, connectivity admits a subquadratic deterministic representation despite the quadratic cost of edge recovery, but remains polynomially harder than its randomized counterpart. The upper bound immediately yields an $\widetilde{O}(n^{7/4})$-bit deterministic $n^2$-fault tolerant connectivity oracle, which reports the connected components of a graph $G$ after any valid set of edge deletions. We also obtain an $\tilde Ω(n f^{1/4})$-bit lower bound for deterministic $f$-fault tolerant connectivity oracles for every $f \in [1,n^2]$. Finally, we show that the separation between connectivity and edge recovery persists in deterministic single-pass dynamic streams with bounded update multiplicity. For every fixed $ε\in (0,1/3)$, our algorithm reports the connected components of the final simple graph using $\widetilde{O}(n^{15/8 + 3ε/8})$ bits (subquadratic space), provided each edge undergoes at most $n^ε$ insertion or deletion updates in total.

0.25

The Capacity of Interactive Secure Summation

cs.IT ·2026-10-21 ·Hua Sun
similarity 0.62
Abstract

In secure summation, $K$ parties each hold an input, and the sum of the inputs is computed at one party, securely against at most $T$ colluding parties. Communication typically takes one hop: each party sends one message directly to the party that computes the sum, using correlated randomness that is independent of the inputs and held in advance. We consider interactive secure summation, where every pair of parties is connected by a secure link, so that each party can send messages to every other party, each party has only independent local randomness, and the messages may depend on the inputs and on earlier messages over multiple rounds. We characterize the capacity region, the set of achievable rates of communication, counting all messages exchanged among the parties over all rounds, and of the randomness of every party, counted in symbols per symbol of the sum. For $0\le T\le K-2$, the optimal communication rate is $K(K-1)/(K-T)$, and the randomness rates form a polyhedron with, up to a relabeling of the parties, a single extreme point: $T$ parties have the randomness rates $(K+T-2t)/(K-T)$, $t=1,\ldots,T$, and the others none. In particular, the optimal total randomness rate is $T(K-1)/(K-T)$. Linear schemes achieve every extreme point together with the optimal communication rate. The same techniques give the capacity region when every party recovers the sum and when the sum is computed at a server without input.

0.27

Two choices suffice: $k$-out sampling leaves $O(n/k)$ intercomponent edges for $k\geq 2$

cs.DM cs.DSmath.CO ·2026-10-30 ·Yanyu Chen, Yu Chen
theory similarity 0.62
Abstract

Given a simple undirected graph on $n$ vertices, random $k$-out sampling forms a spanning subgraph by having each vertex independently choose $k$ incident edges uniformly with replacement. We prove that, for every integer $k\geq2$, the expected number of original edges joining distinct sampled components is $O(n/k)$. This resolves the conjecture of Holm, King, Thorup, Zamir, and Zwick in its full range, improving their logarithmic sampling requirement to the optimal threshold of two choices per vertex. The bound fails for $k=1$, and the dependence $O(n/k)$ is tight up to constant factors. Our result holds with replacement and consequently also without replacement. In particular, this implies that contracting just two independent local choices per vertex suffices to reduce an arbitrary simple graph to a quotient with $O(n)$ edges in expectation, which is crucial in reducing the instance size for many contraction-based algorithms. Our proof uses switching arguments to relate intercomponent edges to bridges and a degree-weighted component potential, whose expectation we also bound with a switching argument.

0.26