Page 74 - Textos de Matemática Vol. 39

64
SHMUEL FRIEDLAND AND DANIEL LEVY
• An m − k match between the set of vertices V2(Bk)\V2(B) and the set
of vertices α′ ∈ Qm−k,m, viewed as a subset of V1(B).
• A k match between the set of vertices α := ⟨m⟩\α′ ⊂ V1(B) and
β := ⟨n⟩\β′ ⊂ V2(B).
Fix α ∈ Qk,m,β ∈ Qk,n. Then the total weight of k-matchings in Gw(Bk) using the set of vertices α ⊂ V1(Bk), β ⊂ V2(Bk) is given by perm B[α, β]. The total weight of n−k matchings using V1(Bk)\V1(B) and β′ ⊂ V2(Bk) is (n−k)!. The total weight of m − k matchings using V2(Bk)\V2(B) and α′ ⊂ V1(Bk) is (m − k)!. Hence the total weight of perfect matchings in Gw(Bk), which matches the set of vertices α ⊂ V1(Bk) with the set β ⊂ V2(Bk) is given by (m−k)!(n−k)!permB[α,β].ThuspermBk =(m−k)!(n−k)!permkB.
We remark that the special case of Theorem 2.1 where m = n appears in an equivalent form in [2].
Proposition 2.2. The complexity of computing the number of k-matchings in a bipartite graph G = (V1 ∪ V2, E), where
min(#V1, #V2) ≥ k ≥ c max(#V1, #V2)α and c, α ∈ (0, 1], is polynomially equivalent to the complexity of computing the number of perfect matching in a bipartite graph G′ = (V1′ ∪ V2′, E′), where #V1′ = #V2′.
Proof. Assume first that G = (V1 ∪ V2,E), m = #V1, n = #V2 and
k ∈ [c max(#V1, #V2)α, min(m, n)] are given. Let G′ = (V1′ ∪ V2′, E′) be the
bipartite graph constructed in the proof of Theorem 2.1. Theorem 2.1 yields
that the number of perfect matching in G′ determines the number of k-matching
in G. Note that n′ := #V′ = #V′ = O(k1 ). So the k-matching problem is a 12α
special case of the perfect matching problem.
Assume second that G′ = (V1′ ∪ V2′, E′) is a given bipartite graph with
k=#V1 =#V2.Letm,n≥kanddenotebyG=(V1∪V2,E′), #V1 = m, #V2 = n the graph obtained from G by adding m−k,n−k isolated vertices to V1′,V2′ respectively, (E′ = E). Then a perfect matching in G′ is a k-matching in G, and the number of perfect matching in G′ is equal to the number of k-matchings in G. Furthermore if k ≥ cmax(m,n)α it follows
thatm,n=O(k1 ).
The results of [7] yield

α
Corollary 2.3. Let B ∈ Rm×n and k ∈ ⟨min(m,n)⟩. Then there exists a +
fully-polynomial randomized approximation scheme to compute permk B. Fur- thermore for each x ∈ R there exists a fully-polynomial randomized approxima- tion scheme to compute the matching polynomial Φ(x,B).