# Approximative counting of matchings in a graph

The work by Jerrum & Sinclair (1989) describes an approximative approach to determining the number of matchings $$|M_\ast(G)|$$ in a graph $$G=(V,E)$$. The fundamental ingredient of the approximation scheme is a fully polynomial generator for $$M_\ast(G)$$. The generator is realized by a Markov chain, which yields any element (matching) of the state space $$M_\ast(G)$$ with an almost uniform probability (for non-weighted graphs) after sufficiently many iterations.

Informally, the key steps for approximation of the number of matchings are the following. First, the Markov chain is used to construct a stochastically independent sample $$\hat M_\ast \subseteq M_*(G)$$ of matchings. Second, an edge $$e \in E$$ is chosen to compute the relative frequencies of matchings which contain the edge $$e$$ and which do not. Third, the steps are repeated recursively for a sub-graph. Finally, the approximative number of the matchings is computed from the number which was determined recursively for the sub-graph.

This gives rise to the following questions, which I do not see answered in the paper:

1. What is the minimum required number of iterations of the Markov chain? The paper states, that the bias of the generator should be $$\varepsilon / \alpha |E|$$, but I don't see a direct relation to the minimum number of iterations. Also, the choice of $$\alpha$$ is not specified.
2. What is the minimum required sample size $$|\hat M_\ast|$$? The paper states that it should be within $$O(|E|^3 \varepsilon^{-2})$$, but how is this result useful in practice?
3. How must the edge $$e \in E$$ be chosen in step 2? Is the choice arbitrary?

In the hope for more details, I also checked some other papers on the topic. I found that the same algorithm is also described in the book "Algorithms for Random Generation and Counting: A Markov Chain Approach" by Sinclair (1992), but lacks the same details. Am I missing something between the lines?

1. Proposition 5.11 in  gives the answer to your question. If you are interested on sampling a matching uniformly at random (as it is the case for the counting procedure), then replace $$\lambda=1$$.
2. The number of samples can be upper bounded by $$75|E|^2\varepsilon^{-2}$$, see Proposition 3.4 and its proof in . This is clearly useful, it tells you exactly how many samples you need to get a certain maximum additive error $$\varepsilon$$ (with high probability) for your counting algorithm.