A polynomial-time approximation algorithm for the number of k-matchings in bipartite graphs

Shmuel Friedland, Daniel Levy

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 $G_k$ on an even number of vertices di…