Near linear time methods improve sampling and counting matchings in graphs
Sampling Matchings in Near-linear Time
Data Structures and Algorithms
Summary
Sampling or counting matchings in a network of connections is a common problem with many uses. The authors show new ways to quickly generate representative matchings and count them approximately, even in very large or complex graphs. Their methods run much faster and can use parallel computing efficiently. These advances help handle dense networks and improve previous algorithms in this field.
What this means in practice
- •For network engineers: Generate approximate matchings quickly in large networks to model resource allocation under constraints.
- •For parallel computing developers: Implement efficient parallel algorithms for sampling graph matchings to speed up simulations and optimizations involving network structures.
Authors
Tianshun Miao, Yitong Yin
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.