CS Paper Radar

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

Yi-Jun Chang, Kushagra Chatterjee

cs.DC ·submitted 2026-08-25 06:04 UTC · v3

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.

Closest papers

Nearest neighbours by meaning across the whole index.

Degree Stability of Parallel Greedy Matching in Random Graphs

cs.DM cs.DSmath.PR ·2026-10-18 ·Vishvajeet N, Shrinidhi Teganahally Sridhara
hot direction similarity 0.76
Abstract · 49 pages

We study a natural synchronous greedy matching process in Erdős-Rényi random graphs $\mathbb{G}(n,p)$ and give a rigorous analysis of this parallel stochastic dynamics. The process evolves as follows: in each round, every unmatched vertex proposes to a uniformly random neighbour, and mutually proposing pairs are matched and removed from the graph, after which the process repeats on the residual graph. We consider the density regime $p=Θ(\log^{1+ε} n/n)$ for any constant $ε>0$, which lies just above the threshold for the existence of a perfect matching. We show that, with high probability, for $Θ(\log^{1+ε} n)$ rounds, every unmatched vertex keeps a constant fraction of its initial degree in the residual graph, simultaneously for all vertices and all rounds. By then, the process has matched a constant fraction of the vertices. Our analysis tracks fine-grained invariants that control the evolution of individual vertex degrees, rather than directly tracking the global degree distribution. At the local level, we analyze the per-round degree loss of a vertex via a neighbourhood-exposure martingale. We show that structural sparsity of $\mathbb{G}(n,p)$ yields $O(1)$ variance and thus the per-round degree loss is strongly concentrated around its conditional expectation. At the global level, these local concentration bounds control the increments of a martingale tracking cumulative degree loss over many rounds, allowing us to show that vertex degrees remain stable for $Ω(\log^{1+ε} n)$ rounds.

0.27

Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.71
Abstract · 11 pages

We present a simple deterministic semi-streaming algorithm that computes a $(1-\varepsilon)$-approximate maximum matching in general graphs in $O(1/\varepsilon^{2})$ passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 \& TheoretiCS'25]. Our approach, which we call the \emph{budgeted price approach}, is very different from the previous $\mathrm{poly}(1/\varepsilon)$-pass semi-streaming algorithms for $(1-\varepsilon)$-approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use $O(1/\varepsilon^{19})$ passes by Fischer, Mitrović, and Uitto~[STOC'22], $O(1/\varepsilon^{6})$ passes by Mitrović, Mukherjee, Sankowski, and Sheu~[ICALP'25], and $O(1/\varepsilon^{4})$ passes by Izumi, Kitamura, and Yamaguchi~['25].

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.70
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

Distributed Lower Bounds via Automatic Self-Reduction

cs.DC cs.DS ·2026-09-28 ·Alkida Balliu, Francesco d'Amore, Dennis Olivetti
theory similarity 0.70
Abstract

The development of round elimination into a general-purpose technique [PODC 2019] marked a turning point in our understanding of the hardness of many graph problems in the distributed setting and led to several breakthrough results. However, the round elimination technique seems unable to yield randomized lower bounds of $ω(\log \log n)$ rounds as a function of the number $n$ of nodes. Very recently, Khoury and Schild [FOCS 2025] introduced a new technique called round elimination via self-reduction, which bypasses the limitations of classical round elimination. Using this approach, the authors show that any randomized algorithm for maximal matching requires $Ω(\sqrt{\log n})$ rounds in the LOCAL model. Their elegant technique is, in some respects, similar to classical round elimination while being fundamentally different in others. However, it is tailored specifically to maximal matching rather than being applicable to a broad class of problems. In this paper, we show that self-reduction is, in fact, a special case of classical round elimination, thereby turning it into a general-purpose approach. In particular, we introduce a new way to measure the error of an algorithm and show that, under this new measure, classical round elimination can indeed yield $ω(\log \log n)$ randomized lower bounds. More specifically, we identify a large class of problems for which this improvement is entirely black-box: once a problem is shown to belong to the class, stronger randomized lower bounds follow automatically from the classical round-elimination framework. As an application, we prove $Ω(\sqrt{\log n})$ randomized lower bounds for a range of graph problems, namely, maximal matching on regular $2$-colored graphs, $\frac{1}{k}$-integral matching, and maximal $H$-packing.

0.31

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree Algorithms

cs.DS cs.CCcs.DMmath.CO ·2026-10-29 ·Abhishek Dhawan, Eren C. Kızıldağ, Neeladri Maitra, Cheng Mao, Timothy L. H. Wee
theory similarity 0.70
Abstract · 32 pages plus references

For many optimization problems on random graphs, most prominently the largest independent set problem, natural algorithms reach only half the optimum, and such factor-two gaps are known to be sharp within broad algorithmic classes. We prove such a gap for finding large induced matchings in Erdős-Rényi random graphs. In the worst case, requiring a matching to be induced turns a polynomial-time solvable problem into an NP-hard one; our results reveal an average-case counterpart. In $G(n,p)$ with $C/n\le p\le 1-κ$, the largest induced matching has size $(1+o(1))L$ with high probability, where $L=\log_{1/(1-p)}(np)$. A simple online greedy algorithm finds an induced matching of size $(1/2-ε)L$, while no online algorithm, even with adaptive inspection order and unbounded computation, finds one of size $(1/2+ε)L$ except with probability $\exp(-Ω(L\log(np)))$. In the sparse regime $p=d/n$, low-degree polynomial algorithms exhibit the same sharp threshold. Our guarantees rest on a maximality principle: with high probability, every maximal induced matching is half-optimal. Greedy outputs a maximal induced matching and our low-degree algorithm a near-maximal one. We bypass the delicate coupling arguments classically used to analyze greedy since Karp. For low-degree hardness, we adapt Wein's overlap gap argument, with forbidden structures that track overlaps between endpoint sets rather than edge sets, since a new edge may join two previously used endpoints and thus encounter no fresh randomness. For online hardness, we give a new and significantly simpler argument that avoids the correlated instances of prior OGP-based proofs: at a suitable stopping time, all pairs involving uninspected vertices remain unrevealed, so a direct first-moment bound suffices.

0.25

Fluid Limits and Upper Bounds for Randomized Greedy Matching

cs.DS math.CO ·2026-10-31 ·Sayan Mukherjee
theory similarity 0.69
Abstract

The Modified Randomized Greedy (MRG) algorithm [Tinhofer (1984), Aronson-Dyer-Frieze-Suen (1995)] is a classical greedy algorithm for finding approximate maximum matchings. MRG repeatedly picks a uniformly random unmatched vertex and matches it to a uniformly random unmatched neighbor, if one exists. Since 1991, the best upper bound on its approximation ratio has been $2/3$, given by the Bomb graphs of [Dyer and Frieze (1991)]. We improve this bound to $0.6569$ on general graphs and $0.6607$ on bipartite graphs. Our constructions consist of copies of small gadgets, with specified vertex classes joined completely. We track each algorithm by counting gadget copies with each possible configuration of remaining vertices. Wormald's differential equation method [Wormald (1995)] shows that these counts, scaled by the size parameter of the construction, converge to a deterministic trajectory known as the \textit{fluid limit}, which is described by ordinary differential equations. This fluid limit approximation holds while the relevant vertex classes have positive density, and so we devise a separate counting argument determines the contribution from the end of the run. Furthermore, we apply our framework to Random Decision Order (RDO), in which vertices are processed in uniformly random order and choose unmatched neighbors according to fixed adversarial preferences. On bipartite graphs, we determine the exact limiting ratio on the Double-Bomb family of [Tang-Wu-Zhang (2020)]. Its minimum is $31/48$, confirming their numerical estimate of about $0.646$.On general graphs, we improve their upper bound of $5/8$, given by the paw graph, to $0.5946$ on a new family. Finally, we give one possible explanation for why $2/3$ seemed to be optimal for MRG in the concluding remarks.

0.23

Locally Sparsified, Globally Near-Optimal: Matching under Independent Vertex Arrivals

cs.DS ·2026-09-22 ·Sara Ahmadian, Edith Cohen, Mohammad Roghani
benchmark similarity 0.67
Abstract

Resource allocation systems often restrict each request to a short list of options before coordinating assignments globally. We study this separation in stochastic bipartite matching under independent vertex arrivals. Each request draws a state from its own known distribution, determining its compatible resources, and independently retains a menu of at most $k$ edges. A maximum matching is then computed on the retained graph. We show that bounded local menus universally suffice for near-optimal matching. For every $\varepsilon>0$, there is a menu size $k_\varepsilon$ depending only on $\varepsilon$ that preserves at least a $(1-\varepsilon)$ fraction of the expected maximum-matching size of the full realized graph. Earlier guarantees required additional assumptions on how matching mass is distributed across edges; our result resolves the unrestricted case. Moreover, the menus are simple to generate from any benchmark matching rule, either by weighted sampling according to the benchmark's edge marginals, or by applying the benchmark to sampled realizations and retaining the resulting partners. Our proof constructs a near-optimal certificate inside the sparsifier by combining a \emph{locally computable} surrogate for the large-marginal edges with a fractional completion from sampled light edges. The surrogate nearly preserves the benchmark's value and endpoint loads while controlling dependencies, which makes the statistical light-edge completion possible.

0.08

Bipartite Matching with Few Rounds of Demand Queries

cs.DS cs.CC ·2026-10-13 ·Shravan Mehra, Sagnik Mukhopadhyay, Vihan Shah
theory similarity 0.67
Abstract · 60 pages 1 figure

We study the randomised and deterministic demand-query complexity of approximate bipartite matching with few query rounds. The demand-query model, introduced in [Blumrosen and Nisan SICOMP 2009; Nisan SODA 2021], is inspired by combinatorial auctions and welfare maximisation, where an oracle returns the first neighbouring vertex (item) of a vertex u (agent) according to a given permutation pi (preference ordering of the agent over the items). For randomised algorithms, our main result gives a trade-off between the number of rounds k, the per-round query budget q=n^{1+δ}, and the achievable approximation ratio. Let 1 <= k <= log n, and -1 <= delta <= 1/k. Every k-round randomised algorithm using O(q) demand queries per round has a worst-case expected-size approximation factor of Omega(n^{1/2k-delta/2}/k). Conversely, we give a randomised algorithm achieving approximation factor O(n^{(1-k*delta)/(k+1)}/k) in expectation. For deterministic algorithms, for k*q >= n, we show that the optimal deterministic approximation factor is ~Theta(n^2/(q*k^2)), thereby improving the previous lower bound of [Nisan SODA 2021] by a polynomial factor over a wide range of parameters. In particular, for q=Theta(n), we improve the deterministic round-complexity lower bound for constant-factor approximation from ~Omega(n^{1/3}) to ~Omega(sqrt n). Our algorithms produce matching and vertex-cover certificates; the deterministic trade-off also extends to minimum vertex cover and maximum fractional matching. We extend the randomised upper bounds to the weaker Demand-OR model [Nisan 2021]. We prove a non-adaptive simulation of uniform random-neighbour queries using known techniques, avoiding the O(log n)-round penalty of the trivial binary-search simulation. Consequently, our upper bounds yield the same k-round approximation guarantees using O(q * log^2 n) Demand-OR queries per round.

0.28