CS Paper Radar

Sampling Matchings in Near-linear Time

Tianshun Miao, Yitong Yin

cs.DS ·submitted 2026-09-18 15:54 UTC · v1
theory

Abstract

For every fixed activity $λ>0$, we establish three results for the monomer--dimer model on an $n$-vertex simple graph $G$ with $m\ge1$ edges and maximum degree $Δ$. 1. Near-linear mixing and sampling. Single-edge Glauber dynamics has mixing time $O_λ(m[\log^2 n+\log(1/\varepsilon)])$, giving a near-linear-time approximate sampler. 2. Work-efficient parallel sampling. We simulate the same Glauber dynamics in parallel using $\tilde{O}_λ(m+n)$ work and $\tilde{O}_λ(\min\{Δ,m^{1/3},\sqrt n\})$ depth with high probability. 3. Fast approximate counting. We estimate the partition function within relative error $\varepsilon$ in $\tilde{O}_λ(n^2/\varepsilon^2)$ work. For dense graphs with $m=Θ(n^2)$, this is near-linear in the input size. For the mixing theorem, we establish a general log--Sobolev criterion based on field-dynamics spectral stability, with only logarithmic dependence on the inverse occupied-marginal lower bound. Parallelism uses a matching-specific analysis of occupation-interval dependencies. Counting uses monomer-preconditioned Jerrum--Sinclair dynamics, whose parameters are learned efficiently by Glauber dynamics.

Closest papers

Nearest neighbours by meaning across the whole index.

Fine-Grained Complexity Across the Computational Phase Transition

cs.CC cs.DSmath.PR ·2026-11-02 ·Zhe Ju, Jingcheng Liu, Yitong Yin
theory similarity 0.69
Abstract

How does a computational problem transition from easy to hard? In the hard-core model, approximate counting and sampling are polynomial-time tractable up to tree uniqueness, but worst-case intractable at any constant relative distance above it unless $\mathsf{NP}=\mathsf{RP}$. We quantify the transition from polynomial to exponential mixing for classical Glauber dynamics. On $n$-vertex graphs of maximum degree $d\ge3$, at fugacity $λ=(1+δ)λ_{\mathrm c}(d)$ with sufficiently small $δ\ge0$ that may vanish with $n$, its worst-case mixing time has the form $\exp\{Θ(nδ^2/d)\}n^{1+Θ(1)}$. The upper bound is degree-uniform, and the matching lower bound holds for every fixed $d$. Annealing gives approximate counting with the same running-time upper bound at fixed accuracy. For general sampling and counting algorithms, we establish a robust fine-grained reduction from SAT without assuming a lower bound on SAT's running time. For any fixed $d\ge3$ and $0<γ<1$, a sampling or approximate-counting algorithm running in $\exp\{O((nδ^2/d)^{1-γ})\}\operatorname{poly}(n)$ time along any one suitable inverse-polynomial distance sequence $δ=δ(n)$, yields a randomized SAT algorithm running in $\exp\{\widetilde O(s^{1-γ})\}$ time on inputs of binary length $s$. This power-saving transfer identifies $nδ^2/d$ as the analogue of SAT input length for hard-core sampling and counting at relative distance $δ$ above criticality: beating the Glauber exponent by a fixed power through any sampling or counting method would yield a corresponding power improvement for SAT. At criticality, we establish $O(\sqrt{n/d})$ spectral independence, optimal in $n$ at fixed degree, and degree-uniform Glauber mixing in $\widetilde O(n(n/d)^{1+1/(d-2)})$ time, improving the previous $\widetilde O(n^{4+4/(d-2)})$ bound.

0.50

Sampling Colorings on $G(n, d/n)$ via Glauber Dynamics

cs.DS math.COmath.PR ·2026-11-09 ·Leon Schiller
similarity 0.68
Abstract

We study the mixing time of Glauber dynamics for sampling uniformly from the proper $q$-colorings of sparse Erdős-Rényi random graphs $G(n,d/n)$. Our main result establishes that with probability $1-o(1)$ over the draw of $G$, Glauber dynamics is rapidly mixing for every $q\geq d+d^{1/2+\varepsilon}$, given any fixed $0<\varepsilon\leq1/2$ and any sufficiently large fixed $d$. In particular, the surplus of colors above $d$ is sublinear and close to $\sqrt{d}$. The achieved color range therefore approaches the tree uniqueness threshold and improves over the previously best achievable number of colors $q > 1.763 d$ due to Efthymiou, Hayes, Stefankovic, and Vigoda [SODA 2018]. Moreover, our mixing-time bound is $O(n^{2+o_d(1)})$, and hence almost quadratic as $d\rightarrow\infty$. Our proof is based on establishing a spectral gap for block dynamics resulting from a suitable decomposition of $G(n,d/n)$ into blocks and singleton vertices, ensuring that every high-degree vertex is encapsulated within a block. Our main technical contribution is a novel way of establishing rapid mixing of block dynamics via an integrated Bochner-Bakry-Émery approach, which we expect to have applications beyond sampling colorings. We further devise a new block decomposition of $G(n,d/n)$ that strengthens and simplifies similar constructions used in previous work. Finally, to compare block and Glauber dynamics, we establish a novel recursive separator decomposition of tree-like blocks, together with a coupling argument that avoids the need for nearly uniform color marginals at vertices adjacent to hubs. This comparison argument might be of independent interest.

0.11

A Linear-Time Approximation Scheme for the Densest Subgraph Problem

cs.DS ·2026-08-11 ·Elena Grigorescu, Mehrshad Taziki
similarity 0.68
Abstract

In the undirected \emph{Densest Subgraph Problem (DSG)} the goal is to output a subset $S$ of vertices of a given graph $G$ that maximizes the quantity $|E(S)|/|S|$, where $E(S)$ is the set of edges in the subgraph induced by $S$. The problem is well studied in both theory and practice, and it admits natural efficient exact algorithms, as well as near-linear time algorithms with a $(1-\varepsilon)$ approximation ratio. However, all previously-known approximation schemes incur logarithmic factors in the size of the graph or other parameters of the graph. This raises the question of whether a linear time $(1-\varepsilon)$-approximation can be obtained for all $\varepsilon>0$. We answer this question affirmatively by providing a $(1-\varepsilon)$-approximation algorithm running in time $O\left(\frac{n+m}{\varepsilon^3}\log \frac{1}{\varepsilon}\right)$, where $m$ and $n$ are respectively the number of edges and vertices of $G$. To the best of our knowledge, this is the first truly linear-time approximation scheme for the problem (when $\varepsilon>0$ is a constant). Our algorithm uses assignments arising from a flow-based formulation together with a structural carving lemma. This lemma allows us to progressively carve "sparse" parts of the graph while nearly preserving the densest subgraph, allowing us to shift heavy computations to smaller instances, which eventually yields the mentioned runtime. Our framework also yields a $(1/2 -\varepsilon)$-approximation for the \emph{Densest At-Least-$k$ Subgraph Problem}, where in addition to maximizing the density, we require the subgraph to have at least $k$ vertices. Our algorithm runs in time $O\left( \frac{(n+m) \log^2 n \log \frac{1}{\varepsilon}}{\varepsilon} \right)$. This nearly matches the known $1/2$ approximation hardness while running in near-linear time.

0.04

Uniformity Testing for the Monomer-Dimer Model

cs.DS cs.DM ·2026-10-27 ·Joy Qiping Yang, Yuichi Yoshida
top venuetheory similarity 0.68
Abstract · To appear in SODA 2027

We study uniformity testing for the monomer-dimer model on a known graph $G=(V,E)$. Given samples from an unknown distribution $D_w(M)\propto \prod_{e\in M} w_e$ over matchings $M$ of $G$, we ask whether $D_w$ is the uniform distribution over all matchings of $G$ or is $\varepsilon$-far from it in total variation distance. Our main result is that, for every maximum-degree bound $Δ$, uniformity can be tested with $\widetilde O_Δ(\sqrt m/\varepsilon^2)$ samples, where $m=|E|$. We complement this with an information-theoretic lower bound for general graphs: for every pair of parameters $n\le m\le n^2$, there are graphs with $Θ(n)$ vertices and $Θ(m)$ edges on which every tester requires $Ω(\sqrt m/\varepsilon^2)$ samples. Thus, for bounded-degree graph families with $m=Θ(n)$, testing uniformity over the space of matchings has $\widetilde Θ(\sqrt n/\varepsilon^2)$ sample complexity, in contrast with the $Θ(n/\varepsilon^2)$ samples needed to estimate $D_w$ in total variation distance.

0.42

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness Threshold

cs.DM math.PRcs.DS ·2026-10-18 ·Zhidan Li, Kuan Yang
theory similarity 0.67
Abstract · 52 pages

We study the mixing time of the single-site Glauber dynamics for sampling proper $q$-colorings on sparse Erdős-Rényi random graphs $\mathcal{G}(n, d/n)$. We prove that, whenever $q \ge (1 + o_d(1))d$, Glauber dynamics mixes in polynomial time with high probability over $\mathcal{G}(n, d/n)$ for all sufficiently large integers $n$. This improves the previous bound $q = (α^* + o_d(1))d$ where $α^* = 1.7632...$ is the unique solution of $x = \exp(1/x)$ on $[1, \infty)$ by Efthymiou, Hayes, Štefankovič, and Vigoda (SODA, 2018) and asymptotically matches the uniqueness threshold on infinite regular trees. Our proof has three main ingredients. First we establish logarithmic bounds on the spectral and coupling independence constants of the Gibbs distribution by extending the tree analysis of Chen, Liu, Mani, and Moitra (J. ACM, 2026). Second, we extend the entropy-factorization framework for two-spin systems on random graphs, developed by Bezáková, Galanis, Goldberg, and Štefankovič (TALG, 2024), to proper colorings by introducing a buffer around high-degree vertices. Finally, we compare the resulting heat-bath block dynamics with the single-site Glauber dynamics.

0.49

Constant-Factor Matching-Size Estimation in Random-Order Streams

cs.DS ·2026-11-16 ·Alireza Farhadi, Mohammad Hajiaghayi, Morteza Monemizadeh
similarity 0.67
Abstract

We give a one-pass algorithm that estimates the maximum matching size of an arbitrary simple graph within a constant factor using $O(\log^2 n)$ bits of space. The edges arrive exactly once in uniformly random order. The algorithm succeeds with probability at least $2/3$, does not require the number of edges in advance, and has worst-case total running time $O((m+1)\log(n+2))$ on a word RAM. Kapralov, Khanna, and Sudan (SODA 2014) obtained a polylogarithmic approximation in polylogarithmic space. Kapralov, Mitrović, Norouzi-Fard, and Tardos (SODA 2020) subsequently gave a constant-factor approximation from independent uniform edge samples and an $O(\log^2 n)$-approximation in random order. We obtain a constant factor in the latter model with the same $O(\log^2 n)$ space bound. The main ingredient is a comparison between the memory states of a recursive sampling algorithm under sampling with and without replacement. We account jointly for the sampled edges retained by the recursion and the positions at which they arrived. Randomized thresholds limit the additional information stored in numerical counters. A bound on the expected work of the entire recursion then removes the loss from its logarithmic depth. The resulting estimator repeatedly improves a coarse estimate while storing only one recursion stack.

0.13

Degree-Free Spectral Independence for Log-Concave Holant Measures

cs.DS math.PR ·2026-09-16 ·Xiaoyu Chen, Zejia Chen, Xinyuan Zhang
similarity 0.66
Abstract

We establish a degree-independent bound on spectral independence for log-concave Holant problems on simple graphs. As a corollary, we obtain relaxation-time bounds for Glauber dynamics of $O_λ(m)$ for the monomer-dimer model at activity $λ$ and $O_{b,λ}(m)$ for $b$-matchings at fugacity $λ>0$, where $m$ is the number of edges. For uniform $b$-matchings, the relaxation-time bound improves to $O(bm)$. The main proof ideas were found using GPT-5.6 Sol.

0.52

The Matching Number Characterizes the Query Complexity of Edge Counting and Degree Moment Estimation

cs.DS ·2026-10-10 ·Chenglin Fan, Wonseok Shin
similarity 0.65
Abstract · 46 pages; abstract shortened for arXiv

Consider an unknown graph $G = (V,E)$ with vertex degrees $d_v$, accessed only by sampling uniformly random edges and querying the degrees of their endpoints. We study the query complexity of estimating the number of edges $m$ and the degree moments $M_s = \sum_{v \in V} (d_v)^s$ for fixed integers $s \ge 2$. In this model, [Beretta and Tětek, TALG 2024] estimate $m$ within relative error $\varepsilon$ using $O(\log n/\varepsilon^2+\sqrt n/\varepsilon)$ expected queries without knowing the number of vertices $n$, and [Bhattacharya and Pradhan, CIAC 2025] estimate $M_s$ using $O(n^{1-1/s}/\varepsilon^2)$ queries when $n$ is given. We show that the query complexity of both problems is governed by the matching number $ν$ of $G$ (the maximum number of pairwise disjoint edges) rather than the number of vertices $n$, and that the dependence on $\varepsilon$ for degree moments can be polynomially improved. Our algorithms rest on a simple observation: the endpoints of a maximum matching cover every edge, so a random endpoint of a random edge falls on this set of $2ν$ vertices with probability at least $1/2$. For every $\varepsilon\in(0,1]$, we give advice-free algorithms that estimate $m$ and $M_s$ within relative error $\varepsilon$ with probability at least $2/3$, without knowledge of $n$, $ν$, or other graph parameters. Specifically, our algorithms use $O(\min\{ν/\varepsilon, 1/\varepsilon^2+\sqrtν/\varepsilon\})$ expected queries for $m$ and $O(\min\{ν^{1-1/s}/\varepsilon^{2/s}, ν^{1-1/(2s-1)}/\varepsilon^{2/(2s-1)}\})$ for $M_s$. Finally, our lower bounds show that for every $k \ge 2$ and sufficiently small $\varepsilon$, these query complexities are optimal up to constant factors over graphs with matching number at most $k$.

0.30