CS Paper Radar

Amplified Pruning and Path Selectors for Deterministic Radio Gossiping

Qin Xin

cs.DS cs.CCcs.DC ·submitted 2026-10-20 21:07 UTC · v3

Abstract

We study deterministic gossiping in unknown strongly connected directed radio networks with $n$ vertices, $m$ arcs, and distinct identifiers in $[N]$, where $N=n^{\mathcal O(1)}$. Messages are unrestricted and collision detection is unavailable. Our neighborhood-clearing procedure reuses an elected receiver to secure its entire closed in-neighborhood in $\mathcal O(n\log^2n\log\log n)$ rounds. Charging each distinct closed neighborhood once yields $\mathcal O(m\log^2n\log\log n)$ rounds under an explicit degree-concentration condition, for every polynomial identifier range. A complementary adaptive-pruning procedure combines quadratic contraction with completion sensitive to the number of unsecured sources. If $a\ge1$ sources remain at completion entry, permutation selectors reduce the balanced completion budget by a factor of $\log^{2/3}(a+1)$ relative to interleaved path selectors. A geometric execution attains $\widetilde{\mathcal O}(k^2+nτ+\min\{u^2,(nu)^{2/3}\})$ for a path cover of scale $k$, weight $τ$, and $u$ exceptions. For directed graphs with common in- and out-degree $Δ$, the portfolio achieves $\widetilde{\mathcal O}(\min\{n\sqrtΔ,n^2/Δ\})$. Every graph also admits $\widetilde{\mathcal O}(\min\{n^{4/3},N+(mn)^{3/5}\})$ rounds. Only $n,N$ are inputs; degrees, covers, and structural constants are used solely in the analysis. The unrestricted polynomial-identifier density extension remains open.

Comment
29 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Locality Meets Interference: Structure and Scheduling in Radio Multicasting

cs.DC cs.DS ·2026-11-12 ·Qin Xin
theory similarity 0.61
Abstract · 21 pages

We study multipoint-to-multipoint multicasting in synchronous radio networks with unknown participant locations and unrestricted message aggregation. Let $n$ be the network size, $k$ the number of participants, and $d$ their hop diameter. A supplied distance-two coloring with $C$ colors yields completion within $(C-1)d+1$ slots and at most $nk$ transmissions. In unit disk graphs, coordinates, one-hop neighbor data, and a common degree bound $Δ_0$ suffice for a $15(Δ_0+1)$-color schedule. A known fixed separation bound permits optimal deterministic $Θ(d)$ completion from coordinates alone. Without geometric data, strong selectivity gives $O(d\min\{n,(Δ_0+1)^2\log n\})$ slots when $n$ is known. Independent random transmission gives $O((Δ_0+1)(d+\log(k/η)))$ slots with failure probability at most $η$; for fixed $Δ_0$, this simplifies to $O(d+\log(1/η))$. A star construction shows that the logarithmic term is necessary for this random rule when the degree grows. We extend color schedules to fixed deletions and subgraphs connected over bounded windows of cycles. Separate conditional reductions preserve additive costs under diameter guessing and control parameter-table and cluster preprocessing. Finally, a counterexample shows that pruning and reranking a breadth-first tree can destroy interference-free delivery. For one-hop designated delivery with receiver degree at most $b$, we prove that the optimal schedule length equals the chromatic number of an associated conflict graph and is at most $2b-1$, with matching examples.

0.29

Settling Nondeterministic Communication Complexity of Graph Connectivity

cs.CC ·2026-10-23 ·Zhijun Zhang
publishedtheory similarity 0.61
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 Streaming Lower Bounds for Approximate Maximum Clique and Maximum Independent Set

cs.DS ·2026-09-16 ·Adithya Diddapur
theory similarity 0.60
Abstract · 25 pages, 1 figure

We study the canonical \textsf{Maximum Clique} and \textsf{Maximum Independent Set} problems in the one-pass edge-arrival graph streaming setting. Here, the edges of some input graph $G = (V,E)$ are presented one at a time (possibly including deletions), before an algorithm needs to produce either a large clique or independent set at the end of the stream, with the focus being on space complexity. We are interested in finding $β$-approximate solutions, for any $β\geq 1$. Previous work gave an algorithm using $\tilde{O}\left(n^2/β^2\right)$ bits of space, together with a corresponding $\tildeΩ\left(n^2/β^2\right)$ two-party communication lower bound [Halldórsson et al., ICALP'12], seeming to resolve the problem. However, their algorithm crucially relies on randomness, and the best known deterministic algorithm remains a folklore derandomisation using $O\left(n^2/β\right)$ bits of space, leaving a (deterministic) gap of size $\tilde{O}(β)$. We make progress towards this gap with a strong lower bound for a restricted range of $β$: whenever $β\leq \sqrt{n}/36\log n$, any deterministic algorithm for either problem must use $Ω\left(\frac{n^2}{β\cdot\log n}\right)$ bits of space. Our proof is via a two-party one-way communication lower bound, and highlights the power of randomness when approaching either of these problems.

0.30

Incremental Exact Vertex Connectivity

cs.DS ·2026-10-15 ·Felix Adena, Monika Henzinger, Christoph Kern, Daniel Rutschmann
top venuetheory similarity 0.60
Abstract · To appear at SODA 2027. Added missing literature

We study the problem of maintaining the vertex connectivity $κ$ of a graph under edge insertions. For undirected graphs, our algorithm uses $O(κ^4 \log^2 n)$ amortized time per edge insertion. After each edge insertion, the algorithm outputs the current value of $κ$, plus a set of $κ$ vertices whose removal disconnects the graph. Our algorithm is Monte-Carlo randomized and works with a randomness-adaptive adversary. The algorithm also works on directed graphs against an oblivious adversary, which is equivalent to an output-adaptive adversary if we only have to output the current value of $κ$. Previously, algorithms using SPQR trees could maintain the vertex connectivity in undirected graphs with $O(\log n)$ time per edge insertion for $κ\le 3$, but no algorithm with $o(n)$ time per edge insertion was known for $κ\ge 4$. Moreover, for $κ\ge 4$, on general directed graphs or sparse undirected graphs, no algorithm faster than recomputation from scratch was known. We complement our algorithm with a conditional lower bound: Under the OMv conjecture, any insertions-only algorithm that outputs the current value of $κ$ after every insertion needs $Ω(n^{1-\varepsilon})$ amortized time per edge insertion for $κ= Θ(n)$. Previous conditional lower bounds for this problem only apply to worst case running time, or algorithms that support both edge insertions and edge deletions.

0.65

Connectivity Oracles Under Vertex Failures via a Simple and Fast Low-Degree Steiner Forest Decomposition

cs.DS ·2026-09-02 ·Sayan Bhattacharya, Ermiya Farokhnejad, Thatchaphol Saranurak, Haoze Wang
theory similarity 0.59
Abstract

We study the low-degree Steiner forest decomposition. Given a graph $G=(V,E)$ and a terminal set $U\subseteq V$, the standard decomposition returns a set $X\subseteq V$ of size at most $|U|/2$ and a forest $T\subseteq G-X$ of maximum degree $Δ$ such that, for every connected component $C$ of $G-X$, some connected component of $T$ contains all terminals in $U\cap V(C)$. This is the central decomposition behind several connectivity oracles under vertex failures [DP20, LS22, LW24]. The state-of-the-art algorithms either take $O(mn\log n)$ time with degree bound $4$ [DP20], or take $m^{1+o(1)}$ time with the weaker degree bound $O(\log^{2}n)$ [LW24]. We show that if $T$ is allowed to contain vertices of $X$, then a degree-$4$ decomposition can be computed by a very simple algorithm in $O(mα(n))$ time. Further, we show that this relaxed decomposition is equally useful for constructing connectivity oracles under vertex failures. As a consequence, we obtain a deterministic connectivity oracle under $d$ vertex failures with $\tilde{O}(m)$ space, $\tilde{O}(md_\star)$ preprocessing time ($d_\star$ is an upper bound on the number of failed vertices), $\tilde{O}(d^{2})$ update time, and $O(d)$ query time. Up to polylogarithmic factors, this oracle strictly improves all known oracles; in particular, it removes the $n^{o(1)}$ factors from the preprocessing and update times of [LS22, LW24].

0.24

Counting in Population Protocols on Graphs

cs.DC ·2026-08-18 ·Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Thorsten Götte, Lukas Hintze +1 more
published similarity 0.59
Abstract · Accepted to DISC 2026

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.

0.46

Approximation Algorithms for Directed Telephone Multicast

cs.DS ·2026-10-20 ·Shahin Kamali, Seyed-Mohammad Seyed-Javadi
similarity 0.59
Abstract

Telephone multicast is a classical problem in information dissemination. In the directed setting, a message starts at a source in an $n$-vertex digraph, and each informed vertex may call one out-neighbour per round. The goal is to inform a given set of $k$ terminals in the fewest rounds. Despite previous work on telephone multicast, a substantial approximation gap remained in the directed setting: approximating the problem within a factor of $o(\log k)$ is NP-hard, while the best existing polynomial-time approximation guarantee depending only on $k$ was $\widetilde O(\sqrt{k})$. For every integer $\ell\ge2$, we give a deterministic combinatorial algorithm that runs in $n^{O(\ell)}$ time and returns a schedule of length $O(\ell^3\log k)(OPT+k^{1/\ell})$, where $OPT$ is the optimum number of rounds. This yields an $O(k^ε)$ approximation in time $n^{O(1/ε)}$ for every fixed $ε>0$, and an $O(\log^4 k)$ approximation in quasi-polynomial time. The same algorithm gives an $O(\log k)$ approximation whenever $OPT\ge k^ε$ for a fixed $ε\in(0,1)$, which is optimal up to a constant factor unless $\mathrm{P}=\mathrm{NP}$. On planar digraphs, we obtain a deterministic polynomial-time $O(\log^2 k)$ approximation. More generally, we give an $O(p\log^2 k)$ approximation for minor-closed graph classes with the following separator property. Given any rooted spanning tree, a balanced separator can be computed in polynomial time as the union of all vertices on at most $p$ tree paths from the root to chosen vertices. Classes of bounded treewidth satisfy this property. We also strengthen the known logarithmic approximation hardness for directed telephone multicast, extending it from instances with a polynomially large optimum to instances with $OPT=O(\log k)$.

0.25

Faster Dynamic Maximal Independent Set against Adaptive Adversaries

cs.DS ·2026-11-04 ·Hongyi Chen, Shuyan Fan, Tianyi Zhang
similarity 0.58
Abstract

We study the fully dynamic maximal independent set (MIS) problem: maintaining an MIS in an undirected graph on $n$ vertices with at most $m$ edges under edge insertions and deletions. Against an oblivious adversary, which fixes the edge update sequence in advance, the randomized algorithms of Behnezhad et al. (2019) and Chechik and Zhang (2019) achieve polylogarithmic update time. Against an adaptive adversary, which may choose each update after observing the previously reported MISs, the best previously known update bound was $O(m^{2/3})$, given by the deterministic algorithm of Gupta and Khan (2018, 2021). Assuming the combinatorial Boolean matrix multiplication hypothesis, Bernstein et al. (2026) proved that any combinatorial algorithm against an adaptive adversary requires at least $m^{1/2-o(1)}$ update time even under edge insertions alone, leaving a polynomial gap between upper and lower bounds. We present a randomized fully dynamic MIS algorithm with $\widetilde O(m^{5/8})=\widetilde O(m^{2/3-1/24})$ update time against adaptive adversaries. This gives the first polynomial improvement over the $m^{2/3}$ bound for adaptive fully dynamic MIS.

0.20