CS Paper Radar

Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows

Xiaoyu Chen, Eric Vigoda, Xiongxin Yang

cs.DM cs.DSmath.PR ·submitted 2026-08-27 04:27 UTC · v1
highly cited

Abstract

The permanent of an $n\times n$ $0/1$ matrix $A$ equals the number of perfect matchings in the bipartite graph with edges defined by $A$. Jerrum, Sinclair, and Vigoda (2004) presented an FPRAS for approximating the permanent of any nonnegative matrix using a novel simulated-annealing algorithm. The running time was improved by Bezáková, Štefankovič, Vazirani, and Vigoda (2008) to $O(n^7\log^4 n)$ for $0/1$ matrices, for any fixed approximation and success parameters. We present the first asymptotic improvement over this running time bound, obtaining an $O(n^6\log^5 n)$-time algorithm. As in the previous works, our algorithm extends to arbitrary nonnegative matrices. The analysis of Bezáková et al. yields an $O(n^4)$ relaxation time bound for the JSV Markov chain on perfect and near-perfect matchings with ideal hole weights, under which each hole pattern (the unmatched vertices, if any) is equally likely in the stationary distribution. We introduce a restricted Poincaré inequality for the partition into hole patterns and prove an $O(n^3)$ bound on the corresponding restricted relaxation time. Our proof uses a coupled multicommodity flow argument inspired by a recent transport-flow argument of Chen et al.~(2025) for the Jerrum-Sinclair chain on all matchings.

Closest papers

Nearest neighbours by meaning across the whole index.

An $\widetilde{O}(n^3)$-time FPRAS for the Permanent

cs.DS cs.DMmath.COmath.PR ·2026-09-17 ·Xiaoyu Chen, Heng Guo, Eric Vigoda, Xiongxin Yang
theory similarity 0.76
Abstract · 62 pages

We give an FPRAS for the permanent of an $n\times n$ $0/1$ matrix with running time $\widetilde O(n^3)$. Our algorithm extends to a strongly polynomial FPRAS for arbitrary nonnegative matrices with the same running-time bound (but in the unit-cost arithmetic model). Jerrum, Sinclair, and Vigoda (2004) gave the first FPRAS for the permanent of a nonnegative matrix. The running time was subsequently improved to $\widetilde{O}(n^7)$ by Bezáková, Štefankovič, Vazirani, and Vigoda (2008), and recently to $\widetilde{O}(n^6)$ by Chen, Vigoda, and Yang (2026). We introduce a multicommodity-flow bound inspired by electrical flows, replacing the usual path-length factor by routing energy. For the classical JSV chain with perfect-matching weights multiplied by $n^2$, we prove a relaxation-time bound of $O(n^3\log n)$ and obtain comparable bounds for estimating the stationary probabilities of having a specified pair of unmatched vertices. We use a separate chain on assignments to generate a warm start at any given temperature, avoiding the long initialization of the JSV chain. Finally, we replace the JSV chain with a new chain that uses only $n$ hole weights and speeds up hole-weight learning by a factor of $n$.

0.20

Maximum Matching on Regular Nonbipartite Graphs

cs.DS cs.DM ·2026-09-12 ·Varsha Dani, Thomas P. Hayes, Seth Pettie
theory similarity 0.67
Abstract

Blocking flow-type maximum matching algorithms are based on finding maximal sets of shortest augmenting paths. They run in $O(m\sqrt{n})$ time, on both bipartite [HK73, Din70, Kar73a, Kar73a] and nonbipartite graphs [GT91, Gab17, Vaz24], but this time bound can be improved if the input is constrained. In this paper we consider $d$-regular bipartite and nonbipartite graphs. Previous algorithms show that a perfect matching in $d$-regular bipartite graphs can be computed in near-linear time deterministically [COS01] or sublinear time with high probability [GKK13]. On $d$-regular non-bipartite graphs, a $(1-1/(d+1))$-approximation can be computed in sublinear time $O(n \log n)$ with high probability [DH25], and hence a maximum matching can be computed in $O(n^2)$ time, w.h.p., which is slightly faster than the best deterministic algorithm for regular graphs [Yus13], running in O(n^2 log n) time. We prove that any blocking flow-type maximum matching algorithm based on finding shortest augmenting paths runs in $O(n^2)$ time on d-regular graphs, both bipartite and nonbipartite. On nonbipartite graphs this is an asymptotic improvement over $O(n^2 \log n)$ [Yus13] and an improvement over $O(m\sqrt{n})$ [GT91, Gab17, Vaz24] when $d = ω(\sqrt{n})$. It also improves [DH25] by making its $O(n^2)$ bound deterministic. However, the main take-away message is that no new algorithms are needed: the "classic" matching algorithms automatically outperform [Yus13, DH25]. We also consider extensions of our results to graphs that are only "nearly regular," meaning that their degrees all lie within a specified range, $[d, Δ]$.

0.24

Subexponential Approximation of the Permanent in Deterministic Polynomial Time

cs.DS cs.CCmath.CO ·2026-09-09 ·Sergei Kudria, Jason Luo, Mahbod Majid
theory similarity 0.66
Abstract · 44 pages

We give the first deterministic polynomial time algorithm that approximates the permanent of arbitrary nonnegative rational matrices within a subexponential factor. For a matrix of order $n$, the approximation factor is \[ \exp\!\left(O\!\left(\frac{n(\log\log n)^2}{\log n}\right)\right)=\exp(o(n)). \] All previously known deterministic polynomial time guarantees for unrestricted inputs had approximation factors $\exp(Ω(n))$. Our proof uses convex optimization to tighten an upper bound on the permanent. The bound is based on weighted sums over all matchings in a bipartite graph representing the matrix, and correlations between unmatched vertices control its error. We approximate these sums deterministically using correlation decay and a bound on the effect of vertex deletion.

0.45

The Quick and the Dead: Estimating Sparse-Matrix Permanents with Adaptive Work Filtering

cs.DS ·2026-08-15 ·Deniz Elbek, Yiğit Manafi, Zeynep Gürdal, Sinan Yıldırım, Kamer Kaya
similarity 0.63
Abstract

Rasmussen's permanent estimator is a simple and unbiased estimator for the permanent of a binary matrix, but its practical performance can be limited by trajectories that terminate before completing a perfect matching. These failed trajectories, together with dispersion among the surviving weights, can substantially reduce the effective sample size. Although the literature leverages techniques such as matrix scaling to improve proposal balance and support filtering to remove structurally infeasible choices, using these at every step can substantially increase the trajectory cost. Furthermore, they do not directly address the choice of the next vertex. This paper uses the classical minimum-degree ordering in sparse matrix algorithms to select the next vertex with O(n + m) total bucket-maintenance work per trajectory, where n is the number of rows/columns in the matrix and m is the number of nonzeros. The proposed estimator uses adaptive schedules to invoke the more expensive scaling and filtering operations only when needed. The experiments show that it is competitive with the state of the art on the tested small matrices and scales effectively to large sparse matrices.

0.04

Dual-Slack Frontier Matching: Parallel Approximate Maximum-Product Matching

cs.DS ·2026-11-12 ·Marc A. Tunnell, Oguz Selvitopi, Xiaoye Sherry Li
similarity 0.60
Abstract

Maximum-product bipartite matching supports scaling and static pivot selection in sparse matrix preprocessing. We present Dual-Slack Frontier Matching (DSFM), a deterministic, shared-memory parallel algorithm for approximate maximum-product matching. Motivated by heavy matchings on small candidate supports, DSFM searches progressively exposed subgraphs ordered by fixed dual slack. Slack-ordered certified completion guarantees a perfect matching whenever one exists, or a maximum-cardinality matching with a Hall certificate otherwise. Every returned perfect matching carries an a posteriori geometric-mean quality bound; accumulated Hall obstructions can tighten this bound and improve the returned scaling. We compare DSFM with Heavy-Weight Perfect Matching (HWPM) and exact MC64 assignment on 598 nonsingular matrices. DSFM attains higher matching quality than HWPM over most quality thresholds. On a set of large instances consisting of 37 matrices, DSFM achieves a $3.53\times$ geometric-mean speedup over MC64, compared to $2.29\times$ for HWPM.

0.32

Maximum Cardinality Matching in $n^{2+o(1)}$ Time

cs.DS ·2026-10-29 ·George Z. Li, Jason Li, Junkai Zhang
similarity 0.60
Abstract

We consider the maximum cardinality matching problem in general graphs, and give an $n^{2+o(1)}$-time algorithm for the problem. Our work builds on recent work on combinatorial algorithms for maximum flow and extends the techniques to skew-symmetric flow problems which capture general matchings as a special case.

0.23

Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity

cs.DS cs.CCcs.DMmath.CO ·2026-08-25 ·Édouard Bonnet, Julien Duron, Marcin Pilipczuk, Marek Sokołowski, Szymon Toruńczyk
similarity 0.60
Abstract · 31 pages, 5 figures

The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excluding a fixed (topological) minor, or bounded expansion graphs, as well as many structured classes of dense graphs, such as graphs of bounded clique-width, twin-width, merge-width, or flip-width. In this work, we present $O(n^2)$-time optimal algorithms for $n$-vertex graphs coming from a class of linear neighborhood complexity for the following problems: $\bullet$ All-Pairs Shortest Paths, $\bullet$ the multiplication of the adjacency matrix $M$ of the input graph with any $n \times n$ matrix. More specifically, after a quadratic preprocessing, we can multiply $M$ with any $n$-vector in $O(n)$ time. This solves several questions raised in [Bonnet, Kim, Geniet, Moon; ICALP '26], and improves and generalizes results in several other recent papers [Bonnet, Giocanti, Ossona de Mendez, Thomassé; STACS '23], [Bannach, Marwitz, Tantau; STACS '24], [Anand, van den Brand, McCarty; NeurIPS '26], [Kozma, Opler '26], and [Cardinal, McCarty, Yuditsky '26]. We also extend our results to classes of bounded VC density. In classes of linear neighborhood complexity, we also give a triangle-detection algorithm in randomized linear time $O(n+m)$ in $n$-vertex $m$-edge graphs, a $K_4$-detection algorithm in randomized $O(n \log^5 n + m \log n)$ or deterministic $O(n^2)$ time, and a $K_5$-detection algorithm in randomized $O(n \log^9 n + m \log^5 n)$ time.

0.37

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

cs.DS ·2026-10-15 ·Tatsuya Terao
similarity 0.60
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