CS Paper Radar

Randomized Greedy MIS Is Fast at Every Node of a Tree

Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović, Srikkanth Ramachandran

cs.DS ·submitted 2026-11-06 21:01 UTC · v1
theory

Abstract

The Randomized Greedy MIS (RGMIS) algorithm computes a maximal independent set (MIS) by processing the vertices in a uniformly random order and greedily adding each vertex to the independent set whenever possible. Despite its simplicity, this algorithm has proved effective in a range of parallel, distributed, and dynamic settings. For sufficiently small maximum degree, Nguyen and Onak (FOCS~'08) and Yoshida, Yamamoto, and Ito (STOC~'09) showed that a recursive simulation of RGMIS can be used to estimate the sizes of matching and vertex cover in sublinear time. The key subroutine in their approach is the following local query procedure: given a vertex $v$, to determine whether $v$ belongs to the MIS, recursively evaluate the neighbors of $v$ that precede $v$ in the random order. If any such neighbor is found to belong to the MIS, the procedure immediately concludes that $v$ is not in the MIS; otherwise, it concludes that $v$ is in the MIS. For graphs of maximum degree $Δ$, Nguyen and Onak showed that, in expectation over the random ordering, this procedure makes $O(\exp(Δ))$ recursive calls from a worst-case starting vertex. No better upper bound is known even for trees. We prove that on trees, from \textit{any} starting vertex, this recursive RGMIS procedure makes $\mathrm{poly}(Δ)$ recursive calls in expectation.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation Testing

cs.DS math.STstat.ML ·2026-11-01 ·Jiale Cheng, Ziao Wang, Lei Ying
similarity 0.64
Abstract · 67 pages, 3 figures

This paper presents a near-quadratic-time algorithm that correctly matches almost all nodes of two correlated Erdős-Rényi graphs without any incorrect matches. Each graph has average degree $λ$ and its edges are subsampled from a common parent Erdős-Rényi graph with $n$ nodes, with subsampling probability $s$. The nodes of one graph are then relabeled by an unknown permutation. The algorithm is built on a test for correlated versus independent Galton-Watson trees with approximated likelihood ratios. For every constant $s>\sqrt{C_{\mathrm{Otter}}}$, where $C_{\mathrm{Otter}}\approx0.338$ is Otter's tree-counting constant, and every $λ=ω(1)$ with $λ=(\log n)^{O(1)}$, the algorithm outputs a partial matching of size $n-o(n)$ that contains no incorrect matches with high probability. If, in addition, $λs\ge(1+ε)\log n$ for a constant $ε>0$, a seeded completion step recovers the permutation exactly. In both cases, the time complexity of the algorithm is $n^{2+o(1)}$ with high probability, whereas previous polynomial-time algorithms with the same guarantees either have a time-complexity bound whose exponent goes to $\infty$ as $s$ approaches $\sqrt{C_{\mathrm{Otter}}}$ from above, or apply only when $s$ is close to $1$.

0.31

A Parallel Greedy Algorithm for Maximal b-Matching in Hypergraphs

cs.DS cs.DC ·2026-11-11 ·Saeed Bakhshan, Daniel Grosu, Henrik Reinstädtler, Christian Schulz
published similarity 0.63
Abstract · 19 pages. Accepted to the SIAM Conference on Applied and Computational Discrete Algorithms (ACDA 2027)

We present \parallelBatchBMatch, a parallel batch-vote algorithm for maximal $b$-matching in hypergraphs. The algorithm is deterministic for a given ordering of edges and produces the same output as the sequential greedy algorithm, i.e., the lexicographically first maximal $b$-matching. Under a uniformly random priority order it performs $O(m')$ expected work in the binary fork--join model, where $m'$ is the number of pins, the total number of vertex--edge incidences. The algorithm performs at most $m$ rounds for every priority order, where $m$ is the number of edges. Every round of the algorithm has $O(\log^2 m')$ depth with high probability, and thus the total depth of the algorithm is $O(m \log^2 m')$ with high probability. We implement the parallel algorithm in CUDA and evaluate it on real-world hypergraphs with capacities $b \in \{1, 3, 5\}$. The parallel algorithm computes the same matchings as the greedy algorithms and for the case of $b = 5$ it is up to $19.07$ times faster than the existing state-of-the art greedy algorithm.

0.38

Sublinear-Time and Semi-Streaming Algorithms for Path Cover and TSP

cs.DS ·2026-10-13 ·Sharareh Alipour, Ali Nowzari
similarity 0.61
Abstract

We give improved sublinear-time and semi-streaming approximation algorithms for maximum path cover, $(1,2)$-TSP, and Max-TSP. For each fixed $\eps>0$, our distance-query algorithm estimates the optimum cost of an $n$-vertex $(1,2)$-TSP instance from above within factor $2-\cstar+\eps=1.413184\ldots+\eps$, with high probability, in $n^{2-Ω_\eps(1)}$ time, where $\cstar=2(\sec1-\tan1)$. This improves the $3/2+\eps$ factor of direct matching estimation in this subquadratic regime~\cite{BhattacharyaKissSaranurak2023} and of the faster near-linear estimator~\cite{BehnezhadEtAl2024}. A single random vertex order defines an implicit bipartite graph whose matchings project to path covers. An alternating-permutation analysis shows that its expected maximum matching size is at least $\cstar$ times the optimum path-cover size. On long paths, even the best of polynomially many uniform orders retains only a $\cstar+o(1)$ fraction with high probability. In semi-streaming, we construct deterministic $(5/7-\eps)$-approximate unweighted path covers and $(9/7+\eps+5/(7n))$-approximate $(1,2)$-TSP tours, improving the respective $2/3-\eps$ and $4/3+\eps+1/n$ guarantees in~\cite{AlipourFarokhnejadMoemke2025}. For nonnegative weights, we obtain $2/3-\eps$ for path cover and Max-TSP, improving the earlier asymptotic $7/12-\eps$ Max-TSP bound. These algorithms use $\poly(1/\eps)$ passes independent of $n$ and $O(n\log(n/\eps)\poly(1/\eps))$ words. We compute two approximate matchings separated by edge deletion. A cycle-compensation lemma accounts for the weight removed when breaking their cycles. For unweighted graphs, a third approximate matching on a simple auxiliary graph with at most $2n$ vertices chooses component connections; a Tutte--Berge count proves the stronger bound.

0.25

Smoothed Analysis for Distributed MIS

cs.DC ·2026-11-12 ·Dipan Dey, Fabien Dufoulon, William K. Moses, Gopal Pandurangan
theory similarity 0.61
Abstract

We study smoothed analysis of the distributed Maximal Independent Set (MIS) problem. Luby's algorithm computes an MIS in $O(\log n)$ rounds, while the recent $Ω(\log n/\log\log n)$ lower bound of Khoury and Schild (2026) shows that it is nearly optimal even in the LOCAL model. We ask whether small random perturbations can overcome this worst-case barrier. Given an arbitrary base graph $G$ on $n$ nodes, we consider the smoothed graph $\mathcal{G}_s=G\triangle G(n,p)$, where $G(n,p)$ is an independent random graph and $\triangle$ denotes symmetric difference. Thus, each possible edge is independently toggled with probability $p$. We establish nearly tight bounds on the smoothing needed for faster distributed MIS. For every base graph $G$, when $p=β\ln n/n$ for a sufficiently large constant $β$, a randomized LOCAL algorithm, given only $\mathcal{G}_s$, computes an MIS of $\mathcal{G}_s$ in $O(\sqrt{\log n})$ rounds with high probability. This is almost quadratically faster than the worst-case lower bound. Conversely, if $p\le(1/2-δ)\ln n/n$ for a fixed constant $δ>0$, there exists a base graph on which every randomized LOCAL MIS algorithm requires $Ω(\log n/\log\log n)$ rounds on the smoothed graph. Hence, the smoothing parameter required for this speedup is optimal up to a constant factor. These results show that smoothed analysis can overcome worst-case lower-bound barriers for distributed local graph problems.

0.10

Single-Vertex Metropolis on Minor-Free Graphs: A General EPTAS

cs.DS math.CO ·2026-11-17 ·Daniel Skachkov, Yuriy Dorn
theory similarity 0.61
Abstract

We consider a class of combinatorial optimization problems where the goal is to find a largest induced subgraph with a prescribed property. We assume that the property is preserved by taking induced subgraphs and disjoint unions, holds for all edgeless graphs, and can be tested in polynomial time. We study the single-vertex Metropolis process for this class of problems. We show that on graphs excluding an arbitrary fixed minor $H$, this process is a randomized efficient polynomial-time approximation scheme. Starting from any feasible solution on a graph with $n$ vertices, it finds a $(1-\varepsilon)$-approximation within $\exp(O_H(\varepsilon^{-2})) n(n+\log(1/δ))$ steps with probability at least $1-δ$. This includes maximum independent set, maximum induced forest, maximum induced bipartite subgraph, and maximum induced subgraph of degree at most one. The proof uses improving exchanges on one fixed division of the input graph into regions. A recursive separator construction performs each exchange inside a region of size $r$ in at most $2r$ moves, with temporary loss $O_H(\sqrt r)$. We count move sequences through each transition and bound the probability of avoiding all near-optimal states. The general theorem bounds the number of Metropolis steps in terms of the temporary loss along improvement paths. We extend the result to bounded weight imbalance and give a weighted-star obstruction for unrestricted weights.

0.16

Fluid Limits and Upper Bounds for Randomized Greedy Matching

cs.DS math.CO ·2026-10-31 ·Sayan Mukherjee
theory similarity 0.61
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.61
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