Publication Details
Title: Approximating the Permanent of Graphs with Large Factors
Author: P. Dagum and M. Luby
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-23.pdf
Overview:
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).
Author: P. Dagum and M. Luby
Group: ICSI Technical Reports
Date: April 1989
PDF: http://www.icsi.berkeley.edu/pubs/techreports/tr-89-23.pdf
Overview:
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.
Bibliographic Information:
ICSI Technical Report TR-89-023
Bibliographic Reference:
P. Dagum and M. Luby. Approximating the Permanent of Graphs with Large Factors. ICSI Technical Report TR-89-023, April 1989