Approximating the permanent of graphs with large factors

https://doi.org/10.1016/0304-3975(92)90234-7Get rights and content
Under an Elsevier user license
open archive

Abstract

Let G=(U, V, E) be a bipartite graph with |U|=|V|=n. The factor size of G, f, is the maximum number of edge disjoint perfect matchings in G. We characterize the complexity of counting the number of perfect matchings in classes of graphs parameterized by factor size. We describe the simple algorithm, which is an approximation algorithm for the permanent that is a natural simplification of the algorithm suggested by Broder (1986) and analyzed by Jerrum and Sinclair (1988a, b). Compared to the algorithm by Jerrum and Sinclair (1988a, b), the simple algorithm achieves a polynomial speed up in the running time to compute the permanent. A combinatorial lemma is used to prove that the simple algorithm runs in time nO(n/f). Thus: (1) for all constants α>0, the simple algorithm runs in polynomial time for graphs with factor size at least αn; (2) for some constant c, the simple algorithm is the fastest known approximation for graphs with factor size at least c log n. (Compare with the approximation algorithms described in Karmarkar (1988).)

We prove the following complementary hardness results. For functions f such that 3⩽f(n)⩽n−3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For and ε>0, for any function f such that 3⩽f(n)⩽n1−ε, approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs.

An announcement of these results appears in Dagum (1988).

Cited by (0)

Supported by NSERC of Canada and the International Computer Science Institute, Berkeley, California. This work was done while the author was at the University of Toronto and also while visiting ICSI.

∗∗

Research partially supported by NSERC of Canada operating grant A8092. A portion of this research was done while the author was at the University of Toronto.