Page 71 - Textos de Matemática Vol. 39

A POLYNOMIAL-TIME APPROXIMATION ALGORITHM FOR THE NUMBER OF K-MATCHINGS IN BIPARTITE GRAPHS
SHMUEL FRIEDLAND AND DANIEL LEVY
To our friend E. Marques de Sa´ on his birthday.
Abstract. We show that the number of k-matching in a given undirected graph G is equal to the number of perfect matching of the corresponding graph Gk on an even number of vertices divided by a suitable factor. If G is bipartite then one can construct a bipartite Gk. For bipartite graphs this result implies that the number of k-matching has a polynomial-time approxi- mation algorithm. The above results are extended to permanents and hafnians of corresponding matrices.
1. Introduction
Let G = (V, E) be an undirected graph, (with no self-loops), on the set of
vertices V and the set of edges E. A set of edges M ⊆ E is called a matching
if no two distinct edges e1,e2 ∈ M have a common vertex. M is called a
k-matching if #M = k. For k ∈ N let Mk(G) be the set of k-matchings in
G.(Mk(G)=∅fork>⌊#V⌋.)If#V =2niseventhenann-matchingis 2
called a perfect matching. φ(k,G) := #Mk(G) is number of k-matchings, and let φ(0, G) := 1. Then Φ(x, G) := ∞k=0 φ(k, G)xk is the matching polynomial of G. It is known that a nonconstant matching polynomial of G has only real negative roots [6].
LetGbeabipartitegraph,i.e.,V =V1∪V2 andE⊂V1×V2.Inthe special case of a bipartite graph where n = #V1 = #V2, it is well known that φ(n, G) is given as perm B(G), the permanent of the incidence matrix B(G) of the bipartite graph G. It was shown by Valiant that the computation of the permanent of a (0, 1) matrix is #P-complete [8]. Hence, it is believed that the computation of the number of perfect matching in a general bipartite graph satisfying #V1 = #V2 cannot be polynomial.
In a recent paper Jerrum, Sinclair and Vigoda gave a fully-polynomial randomized approximation scheme (fpras) to compute the permanent of a non- negative matrix [7]. (See also Barvinok [1] for computing the permanents within a simply exponential factor, and Friedland, Rider and Zeitouni [5] for concen- tration of permanent estimators for certain large positive matrices.)
2000 Mathematics Subject Classification. 05A15, 05C70, 68A10.
Key words and phrases. Perfect matchings, k-matchings, permanents, hafnians, polynomial-time approximation algorithm.
61