CS Paper Radar

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

Jiale Cheng, Ziao Wang, Lei Ying

cs.DS math.STstat.ML ·submitted 2026-11-01 23:19 UTC · v1

Abstract

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

Comment
67 pages, 3 figures

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

No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL Model

cs.DS cs.DC ·2026-10-13 ·Seri Khoury, Aaron Schild
theory similarity 0.66
Abstract · 34 pages, 2 figures. Abstract shortened due to arXiv requirements

We prove that $o(\frac{\log n}{\log\log n})$-round randomized LOCAL algorithms find a maximal independent set (MIS) with subconstant probability on some input. This shows that the 40-year-old $O(\log n)$-round randomized CONGEST algorithm of Luby and Alon, Babai, and Itai is nearly optimal. Our lower bound improves upon the $Ω(\sqrt{\log n})$-round lower bound of Khoury and Schild and nearly closes the 20+ year-old gap between the $O(\log n)$-round algorithm and the $Ω(\sqrt{\frac{\log n}{\log\log n}})$-round lower bound of Kuhn, Moscibroda, and Wattenhofer. To close this gap, one must show a lower bound for a graph that is not locally treelike. We do this by starting with a $D$-regular, $Θ(\log_D n)$-girth graph, with $D = Θ(\log n)$. Crucially, this is not our final graph. We obtain our hard instance by \emph{replacing} each vertex of this treelike graph with a clique on $n^c$ vertices for some constant $c \in (0,1)$. We then replace each edge with a bipartite Erdős--Rényi graph between the corresponding cliques, with each edge present independently with probability $1/2$. We analyze arbitrary LOCAL algorithms on our non-treelike hard instance with a novel round elimination approach. We describe algorithms that output a set of vertices in this graph using two metrics: their \emph{occupancy probability} and their \emph{conflict probability}. Our round elimination framework takes an $r$-round algorithm and produces an $(r-1)$-round algorithm where occupancy and conflict probabilities collectively slightly degrade, but individually can significantly improve or degrade. This round elimination result is obtained by exploiting the lack of large biclique complements in dense bipartite Erdős--Rényi graphs, which in turn allows us to bound the entropy of the output distribution for any independent set algorithm.

0.56

Stochastic Matching with Polynomial Degree

cs.DS ·2026-11-02 ·Soheil Behnezhad
hot direction similarity 0.64
Abstract

We study the stochastic matching problem, where a graph $G$ is known in advance, but each edge survives independently with probability $p$. The goal is to select a subgraph $H$ of small maximum degree before seeing the surviving edges, while preserving a $(1-ε)$ fraction of the expected maximum matching size. This problem has received significant attention due to its numerous applications in kidney exchange, labor markets, and online dating. In this paper, we show there is always a subgraph $H \subseteq G$ achieving a $(1-ε)$-approximation while having a maximum degree of at most $O\left(\frac{\log(1/ε)}{ε^4} \cdot \frac{1}{p}\right).$ This resolves a major conjecture of the literature, first stated by [BDH, STOC'20], that $poly(\frac{1}{εp})$ degrees suffice. The best previous bound was $(1/p)^{\exp((1/ε)\log(1/ε))}$ by [ABGR, STOC'25]. The key to this result is a lemma of independent interest that any distribution over the matchings of a stochastic graph can be transformed to another distribution which matches each vertex with exactly the same probability, but exhibits extremely low total pairwise correlation.

0.23

Randomized Greedy MIS Is Fast at Every Node of a Tree

cs.DS ·2026-11-06 ·Mina Dalirrooyfard, Konstantin Makarychev, Slobodan Mitrović, Srikkanth Ramachandran
theory similarity 0.64
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.

0.28

Graph Matching in Random Geometric Graphs I: Efficient Algorithms

cs.DS math.PRmath.ST ·2026-10-12 ·Dong Huang, Ankang Jiao, Shuangping Li, Zhangsong Li
hot direction similarity 0.64
Abstract · 62 pages, 4 figures

We study the recovery of the hidden vertex correspondence between two correlated dense random geometric graphs. Each graph is generated from $n$ latent unit vectors in $\mathbb R^d$; the vectors $u_i^A$ and $u_i^B$ of corresponding vertices satisfy $\langle u_i^A,u_i^B\rangle=ρ$, and the vertex labels of the second graph are permuted by an unknown permutation $π$. For every fixed correlation $ρ\in(0,1]$ and every edge density bounded away from zero and one, we give a randomized polynomial time algorithm that recovers $π$ exactly with probability tending to one whenever $d\ge(\log n)^L$, where $L$ depends only on the correlation and the density bounds. The algorithm assigns to each vertex a signature formed by counting decorated paths with a constant number of seeds. The number of such seeded templates grows exponentially with the path length, with an arbitrarily large constant base, so the resulting statistics amplify an arbitrarily small constant correlation. We control the dependencies created by the latent geometry in two ways: when $d$ is larger than $n/(\log n)^{L_0}$ for a suitable constant $L_0$, by comparing local moments with those of correlated Erdős--Rényi graphs; for smaller $d$, by spectral estimation of the latent geometry combined with a harmonic correction. We also provide low-degree evidence for a tradeoff between the correlation and the computational cost.

0.36

A tight lower bound for malicious online bipartite matching with limited recourse budget

cs.DS cs.DM ·2026-08-23 ·Julia Baligacs, Bartłomiej Bosek, Paweł Putra, Marek Sokołowski, Anna Zych-Pawlewicz
theory similarity 0.64
Abstract

We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online together with their incident edges. After each arrival, the algorithm must maintain a maximum-cardinality matching while minimizing the total number of reallocations, also known as the recourse budget. Despite extensive work, the exact recourse complexity of the problem remains unsettled: the best lower bound is $Ω(n \log n)$, whereas the best upper bound is $\mathcal{O}(n \log^2 n)$, where $n$ denotes the number of online vertices. Tight upper bounds of $\mathcal{O}(n \log n)$ are known only for restricted graph classes, such as forests. The best known upper bounds are attained by a very simple and natural algorithm SAP, which after each arrival applies a shortest augmenting path, and it is conjectured to be optimal. All known upper bound analyses of this algorithm do not depend on the particular maximum matching maintained by the algorithm. Consequently, they also apply to a more difficult problem, which we call the malicious matching setting: after each arrival, the maintained matching is replaced by a worst-case maximum matching for the next step. This led to the conjecture that the malicious setting still admits an $\mathcal{O}(n \log n)$ recourse bound, in line with the conjectured optimal complexity of the original model. Our main result is an $Ω(n \log^2 n)$ lower bound for the malicious matching setting, thus disproving the conjecture. Together with the previous upper bound, this settles the asymptotic recourse complexity of the malicious variant of the problem. We complement our lower bound with an upper bound of $\mathcal{O}(n \log n)$ for expander graphs.

0.20

Tree Edit Distance: Near-Linear-Time Approximate, Sublinear, and Dynamic

cs.DS ·2026-10-15 ·Bingbing Hu, Tomasz Kociumaka, Jakob Nogler, Barna Saha
published similarity 0.63
Abstract · SODA 2027

Tree edit distance (TED), the analog of string edit distance (ED) for hierarchical data, is the minimum number of node insertions, deletions, and substitutions transforming one labeled rooted ordered tree into another. We narrow polynomial gaps between TED and ED in near-linear-time approximation, sublinear algorithms, and dynamic algorithms. We give an $n^{o(1)}$-approximation in $O(n)$ time and, for every $0<δ<1$, a $(\log n)^{O(1/δ)}$-approximation in $O(n^{1+δ})$ time. This improves the previous near-linear-time $O(\sqrt n)$-approximation [Boroujeni et al., STOC'19] and brings TED to parity with ED in this regime up to polylogarithmic factors. With query access to the balanced-parentheses (Euler-tour) representation of the input trees, we give the first sublinear-time TED algorithm: for every $τ\in[1,n]$, it computes a $τn^{o(1)}$-approximation of $1+\mathrm{ted}$ in $O(n/τ)$ time. For dynamic TED, we give an exact algorithm with amortized update time $\tilde{O}(k^7)$ and a $(1+\varepsilon)$-approximation with amortized update time $\tilde{O}_{\varepsilon}(k)$, where $k$ caps the distance that must be reported. The exact algorithm is the first to beat recomputation in a nontrivial parameter regime. The approximation improves prior dynamic guarantees [Das et al., FOCS'25] and cannot be significantly improved in any parameter regime without a breakthrough for static $(1+\varepsilon)$-approximation of ED. All results use dynamic programming on a new hierarchical tree decomposition, analogous to partitioning strings into blocks of geometrically decreasing sizes. It combines structural properties previously achieved only in isolation, providing a framework for transferring algorithmic ideas from ED to TED, with additional ingredients addressing the obstacles in each computational setting.

0.34

Query Complexity of Densest Sub(hyper)graph Problems

cs.DS cs.CC ·2026-10-13 ·Sinan G. Aksoy, Eli Friedman, Nate Veldt, Stephen J. Young
theory similarity 0.63
Abstract · 26 pages

Rubinstein et al. introduce the study of connectivity and minimum cut problems in the cut query model, where an algorithm can only access the edges of a graph through CUT queries. In this work, we examine the query complexity of densest subgraph problems. Our first contribution is to generalize the uniform sparsification approach for Densest Subgraph and other heavy subgraph problems to weighted graphs, achieving the following results. >A $(1+\varepsilon)$-approximation for weighted Densest Subgraph in $O(n\log^2 n/\varepsilon^2)$ queries, roughly matching the $Ω(n/\log n)$ lower bound we prove for randomized algorithms. >A $(1+\varepsilon)$-approximation for weighted Max Cut in $O(n\log^2 n/\varepsilon^2)$ queries. This improves upon the bound of $O(n\log^3 n(\log n+1/\varepsilon^2))$ queries achieved by Plevrakis et al., making significant progress towards their lower bound of $Ω(n/\log n)$ queries. In contrast, we rule out approximation schemes with truly subquadratic query complexity for Densest $k$-Subgraph and settle its exact query complexity in both the unweighted and deterministic settings. For hypergraphs, we show CUT queries alone cannot achieve $o(\sqrt{n})$-approximation for Densest Subhypergraph or $o(n)$-approximation for Densest $k$-Subhypergraph, regardless of the number of queries. Augmenting CUT queries with the EDGE oracle of Chen et al., we overcome this barrier for Densest Subhypergraph and obtain a $(1+\varepsilon)$-approximation on rank-$r$ hypergraphs using $O(nr\log n/\varepsilon^2)$ queries. We also extend our Densest $k$-Subgraph hardness results to hypergraphs and prove exponential query lower bounds for exact Densest $k$-Subhypergraph. Lastly, confirming a conjecture of Chakrabarty and Liao, we show that simulating an ADD query using CUT and IS-EDGE$^?$ queries requires exponentially-many queries.

0.24