Structural Corrections to the Bethe Approximation of the Permanent
2026-08-31 • Data Structures and Algorithms
Data Structures and Algorithms
AI summaryⓘ
The authors study how to approximate the permanent of a nonnegative matrix, a quantity that is hard to compute exactly. They build on the Bethe permanent, which can be computed efficiently but only approximates the true permanent within a certain factor. They identify a specific pattern, related to 4-cycles, that limits the approximation quality and develop an algorithm to find and handle these patterns. This leads them to improve the approximation factor slightly below the known bound, resulting in a better deterministic polynomial-time algorithm for estimating the permanent.
PermanentNonnegative matrixBethe permanentDeterministic approximation algorithmPolynomial time4-cycleMatrix approximationCombinatoricsAlgorithmic graph theory
Authors
Ijay Narang, Will Perkins
Abstract
We study deterministic approximation algorithms for the permanent of a nonnegative matrix through the Bethe permanent, an approximation computable in polynomial time. The tight analysis of Anari and Rezaei gives a universal comparison between the permanent and the Bethe permanent within a factor $(\sqrt 2)^n$. The simple example of the unweighted $4$-cycle $C_4$ (or a union of disjoint $C_4$'s) shows that this bound is tight. We show that such $4$-cycle obstructions can be identified and exploited algorithmically. Given a Bethe optimizer, our algorithm identifies nearly isolated weighted $2\times2$ blocks and peels off a vertex-disjoint family of them. If the total weighted correction is large, we can improve the Bethe approximation; if it is small, we show that the Bethe permanent is within a factor of $(\sqrt2 - \varepsilon)^n$ of the truth. Combining these facts, we obtain a deterministic polynomial time $(\sqrt2-\varepsilon)^n$-approximation algorithm for the permanent of an arbitrary nonnegative $n\times n$ matrix, where $\varepsilon>0$ is some absolute constant.