Approximative counting of matchings in a graph

Question

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?

Answer 1

Both Jerrum and Sinclair have written a lot about this kind of topic over the years, and there are more recent references by them that you can check out. In particular, take a look at [1], it addresses among other things the counting algorithm for matchings in great detail. To answer your questions:

1. Proposition 5.11 in [1] 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 [1]. 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.

3. It can be any edge. The important thing is that you are reducing the problem to a smaller version of itself (one less edge).

Hope that helps.

[1] https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/JerrumBook