Source-linked AI summary
Faster FPRAS for the Permanent via Restricted Poincaré Inequalities and Coupled Flows
Xiaoyu Chen, Eric Vigoda, Xiongxin Yang
TL;DR
Approximating the permanent is necessary because exact evaluation is #P-complete even for 0/1 matrices, while prior FPRAS running times remained high. The paper uses a hole-pattern-restricted Poincaré inequality and coupled flows to accelerate weight refinement, obtaining an improved FPRAS that extends to nonnegative matrices.
Problem
Exact permanent evaluation is #P-complete for 0/1 matrices, motivating faster approximation algorithms.
Method
The paper restricts the Poincaré analysis to hole-pattern observables and bounds the resulting relaxation time using coupled multicommodity flows.
Results
O(n^6 log^5 n ε^-2) runtime achieves a multiplicative (1 ± ε) approximation with constant success probability, with failure reduced to δ by repetition.
Takeaways & Limitations
The restricted relaxation time is O(n^3) instead of the full-chain O(n^4), accelerating the weight-refinement step by a factor of n.
Takeaways & Limitations
The sampling consequence assumes a nonnegative spectrum, in particular satisfied by lazy chains, and the theorem assumes the graph contains a perfect matching.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper develops a faster FPRAS for the permanent by targeting the hole-pattern observables used in weight refinement rather than the full matching state space. Its restricted relaxation analysis reduces the refinement bottleneck and yields an asymptotic running-time improvement while retaining extension to nonnegative matrices.
- Motivation: The permanent counts perfect matchings of a bipartite graph, but exact evaluation is #P-complete even for 0/1 matrices, making approximation necessary.The permanent also has applications in combinatorics, statistical physics, computer vision, and statistics.
- Prior framework: The Jerrum–Sinclair–Vigoda FPRAS was the first to handle arbitrary matrices with nonnegative entries using simulated annealing.The algorithm operates on perfect and near-perfect matchings while adjusting activities and hole weights.
- Contribution: The weight-recalibration term is the bottleneck, and reducing it by a factor of n drives the paper’s main theorem.Refinement estimates hole-pattern frequencies rather than using the entire matching as its observable.
- Contribution: Theorem 1 gives an FPRAS approximating the permanent of an n × n 0/1 matrix within factor (1 ± ε), with high probability, in the stated improved time bound.The algorithm extends to arbitrary matrices with nonnegative entries.
- Contribution: The hole-restricted relaxation time is O(n^3), improving the full-chain bound O(n^4) and reducing the correlation scale relevant to hole-pattern frequency estimates.The proof uses a coupled multicommodity-flow refinement of classical flow arguments.
2 Sketch of the Permanent Algorithm
The algorithm uses simulated annealing with hole weights that balance perfect and near-perfect matching blocks, refining those weights from stationary hole-pattern frequencies. A restricted relaxation bound makes refinement faster, producing the improved FPRAS running time and preserving the nonnegative-matrix extension.
- Annealing framework: The annealing schedule decreases nonedge activity from 1 through positive values until the weighted perfect-matching count approximates the permanent.The telescoping identity reduces the computation to ratios at consecutive activities.
- Annealing framework: The JSV chain samples perfect and near-perfect matchings, with hole weights chosen to balance the stationary masses of the perfect and near-perfect blocks.Ideal weights make all n^2 + 1 hole-pattern blocks equally likely, while constant-factor approximations preserve the mixing guarantee.
- Weight refinement: Weight refinement estimates stationary probabilities of the n^2 + 1 hole-pattern blocks and converts their ratios into accurate ideal hole weights.Rough weights lie within a factor of 2 of ideal weights; refinement outputs accurate weights under the stated success guarantee.
- Weight refinement: The hole-restricted relaxation analysis reduces the relevant correlation scale from O(n^4) to O(n^3), yielding a factor-n faster refinement procedure.Theorem 2 applies to every choice of positive activities when the graph contains a perfect matching.
- Running time: O(n^6 log^4 n) is the total cost of weight refinement across the cooling schedule.The schedule uses at most 48n(log n)^2 activity values, with failure probabilities controlled across refinement calls.
- Running time: O(n^6 log^5 n ε^-2) is the conditional runtime for a complete execution achieving a multiplicative (1 ± ε) approximation with constant success probability.Repeating executions and taking a median reduces failure probability to δ, giving the theorem’s total running time.
- Scope: The algorithm extends to nonnegative matrices through the weighted cooling reduction because the refinement procedure accepts arbitrary positive activities.The proof separately handles n = 1 and instances with zero permanent.
3 Poincaré and Restricted Poincaré Inequalities
The section develops a partition-restricted Poincaré inequality that measures variance visible through blocks, then connects it to sampling and coupled-flow bounds. This framework can yield sharper control than the full relaxation time when within-block fluctuations are irrelevant.
- Restricted variance: The restricted Poincaré inequality averages observables within partition blocks and measures variation among their conditional means.It discards fluctuations that remain entirely within a block.
- Restricted relaxation time: The restricted relaxation time satisfies τS ≤ τrel and can be much smaller for coarser partitions because it ignores block-invariant slow modes.Equality holds for singleton blocks, where block averaging is the identity.
- Sampling consequences: For block-constant observables, a trajectory of length m has an effective sample size of order m/τS rather than requiring full-chain mixing within τS steps.This is the sampling guarantee needed when the estimator records only the visited block.
- Sampling consequences: Stationary-initialized trajectories provide relative-ε mean estimates for ordinary observables using τrel and for block-constant observables using τS.The corresponding bounds assume a finite irreducible reversible chain with nonnegative spectrum and a partition.
- Sampling consequences: The projection-chain relaxation time alone is insufficient because hidden within-block state information can persist, whereas τS accounts for this memory.The restricted definition permits test functions depending on the full state while retaining only their block averages in the variance.
- Coupled flows: Coupled flows assign block-level demand while choosing endpoint couplings with conditional stationary marginals, after which standard path-congestion analysis applies.This flexibility contrasts with ordinary flows, which prescribe independent endpoint demand π(x)π(y).
4 Faster FPRAS via Hole-Restricted Relaxation Time
The algorithm accelerates weight refinement by analyzing only hole-pattern observables through a restricted relaxation time and by routing coupled flows from near-perfect blocks to the perfect block. This yields an O(n^3) restricted relaxation bound and faster refinement, while preserving accuracy with high probability.
- Restricted relaxation framework: The hole-pattern partition contains the perfect-matching block and n^2 near-perfect blocks, with equal stationary block probabilities under ideal hole weights.The chain records only whether a matching is perfect or which pair of vertices forms its holes.
- Restricted relaxation framework: The hole-restricted relaxation time τholes bounds variance after averaging observables within each hole-pattern block.This weaker quantity targets the statistics used by weight refinement rather than arbitrary functions of the full matching state.
- Coupled flow: The coupled-flow construction routes each near-perfect source block to the perfect block using paths of length at most n and flow weights based on conditional stationary distributions.The coupling keeps one hole fixed while unwinding the alternating path between a near-perfect and perfect matching.
- Coupled flow: 16n^3 bounds the coupled-flow congestion, establishing the ideal-weight restricted relaxation estimate.The factor-n improvement arises because a fixed transition receives flow from only n source blocks instead of O(n^2).
- Transfer to rough weights: Rough hole weights remain comparable to ideal weights, allowing the restricted variance bound to transfer from ideal to rough weights.The comparison uses conditional distributions that coincide within each block and the bound π ≤ 4π∗.
- Weight refinement: The resulting refinement procedure costs O(n^6 log^4 n) and outputs accurate weights with probability at least 1 − δ.It uses O(log(2n/δ)) independent burn-in and trajectory copies, each costing O(n^5 log n) transitions.
5 Congestion Analysis
The congestion proof analyzes slides and additions separately, encoding routed paths into matching pairs to bound the load on every transition. The fixed-hole routing property limits contributing source blocks and yields the stated congestion bound.
- Final bound: The maximum congestion is at most 8n^2(n^2 + 1), which becomes 16n^3 after applying the prefactor in the flow bound.The slide and addition cases together establish the transition bound used in Lemma 15.
- Case analysis: The congestion analysis splits transitions into slides with |α ⊕ β| = 2 and additions with |α ⊕ β| = 1.Deletions have zero load because every route ends with an addition.
- Slide transitions: For right-hole slides, the route keeps the right hole z fixed, so only source blocks N(u, z) can contribute.Summing over at most n choices of u bounds the slide load after an injective encoding into near-perfect matchings.
- Slide transitions: The slide-case encoding reconstructs the originating pair (I, F) from the transition state and an auxiliary matching K.The symmetric-difference path is oriented from u, while untouched alternating cycles determine their two matching classes.
- Addition transitions: For additions, the transition is the final step of every route, and the fixed right hole again restricts contributing source blocks to N(u, z).An injective encoding maps contributing pairs into N(u, z), and summing over u gives the required load bound.