Approximating the Permanent of Graphs with Large Factors

TitleApproximating the Permanent of Graphs with Large Factors
Publication TypeTechnical Report
Year of Publication1989
AuthorsDagum, P., & Luby M.
Other Numbers522
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 in [Broder 86] and analyzed in [Jerrum, Sinclair 88 a,b]. A combinatorial lemma is used to prove that the simple algorithm runs in time n(superscript O(n/f)). Thus (1) for all constants alpha > 0, the simple algorithm runs in polynomial time for graphs with factor size at least alpha(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, et. al. 88).We prove the following complementary hardness results. For functions f such that 3 is less than or equal to f(n) is less than or equal to n-3, the exact counting problem for f(n)-regular bipartite graphs is #P-complete. For any epsilon > 0, for any function f such that 3 is less than or equal to f(n) is less than or equal to n (superscript 1-epsilon), approximate counting for f(n)-regular bipartite graphs is as hard as approximate counting for all bipartite graphs.

URLhttp://www.icsi.berkeley.edu/pubs/techreports/tr-89-23.pdf
Bibliographic Notes

ICSI Technical Report TR-89-023

Abbreviated Authors

P. Dagum and M. Luby

ICSI Publication Type

Technical Report