3
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.