<p>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:</p>
<ol>
<li><p>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 <span class="math-container">$\lambda=1$</span>.</p>
</li>
<li><p>The number of samples can be upper bounded by <span class="math-container">$75|E|^2\varepsilon^{-2}$</span>, 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 <span class="math-container">$\varepsilon$</span> (with high probability) for your counting algorithm.</p>
</li>
<li><p>It can be any edge. The important thing is that you are reducing the problem to a smaller version of itself (one less edge).</p>
</li>
</ol>
<p>Hope that helps.</p>
<p>[1] <a href="https://www.math.cmu.edu/%7Eaf1p/Teaching/MCC17/Papers/JerrumBook" rel="nofollow noreferrer">https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/JerrumBook</a></p>

CC BY-SA 4.0
2023-07-18T23:26:19.213Z
2023-07-18T23:26:19.213Z
acrendic
<p>The <a href="https://epubs.siam.org/doi/abs/10.1137/0218077?casa_token=tQBihSoFTCUAAAAA:Zj697CzowbPOLmBdaP5NFqdtnUgiyYM9wg4rDO87iFmpwhgFhIruk15V34vxC0Kih8qLxLd4BA" rel="nofollow noreferrer">work by Jerrum &amp; Sinclair (1989)</a> describes an approximative approach to determining the number of matchings <span class="math-container">$|M_\ast(G)|$</span> in a graph <span class="math-container">$G=(V,E)$</span>. The fundamental ingredient of the approximation scheme is a fully polynomial generator for <span class="math-container">$M_\ast(G)$</span>. The generator is realized by a Markov chain, which yields any element (matching) of the state space <span class="math-container">$M_\ast(G)$</span> with an almost uniform probability (for non-weighted graphs) after sufficiently many iterations.</p>
<p>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 <span class="math-container">$\hat M_\ast \subseteq M_*(G)$</span> of matchings. Second, an edge <span class="math-container">$e \in E$</span> is chosen to compute the relative frequencies of matchings which contain the edge <span class="math-container">$e$</span> 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.</p>
<p>This gives rise to the following questions, which I do not see answered in the paper:</p>
<ol>
<li>What is the minimum required number of iterations of the Markov chain? The paper states, that the bias of the generator should be <span class="math-container">$\varepsilon / \alpha |E|$</span>, but I don't see a direct relation to the minimum number of iterations. Also, the choice of <span class="math-container">$\alpha$</span> is not specified.</li>
<li>What is the minimum required sample size <span class="math-container">$|\hat M_\ast|$</span>? The paper states that it should be within <span class="math-container">$O(|E|^3 \varepsilon^{-2})$</span>, but how is this result useful in practice?</li>
<li>How must the edge <span class="math-container">$e \in E$</span> be chosen in step 2? Is the choice arbitrary?</li>
</ol>
<p>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 <a href="https://link.springer.com/book/10.1007/978-1-4612-0323-0" rel="nofollow noreferrer"><em>&quot;Algorithms for Random Generation and Counting: A Markov Chain Approach&quot;</em> by Sinclair (1992)</a>, but lacks the same details. Am I missing something between the lines?</p>

<graph-theory><graph-algorithms><approximation-algorithms><matching><markov-chains>
Approximative counting of matchings in a graph
kostrykin
# Approximative counting of matchings in a graph

(Asked by: username_0 on 2022-08-18)

The [work by Jerrum & Sinclair (1989)](https://epubs.siam.org/doi/abs/10.1137/0218077?casa_token=tQBihSoFTCUAAAAA:Zj697CzowbPOLmBdaP5NFqdtnUgiyYM9wg4rDO87iFmpwhgFhIruk15V34vxC0Kih8qLxLd4BA) 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)](https://link.springer.com/book/10.1007/978-1-4612-0323-0), but lacks the same details. Am I missing something between the lines?

**Tags:** graph-theory, graph-algorithms, approximation-algorithms, matching, markov-chains


---

## 1 answers

### Answer by username_1 on 2023-07-18. Score: 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](https://www.math.cmu.edu/%7Eaf1p/Teaching/MCC17/Papers/JerrumBook)


---

