2
$\begingroup$

How can one show that the counting problem:

Given a graph, output the number of perfect matchings

Is self reducible?

I found a hint in Moore's Chapter on Counting, Sampling and Statistical Physics:

Let G be a graph and e one of its edges. Show that we can modify G to produce two graphs, G0 and G1, such that the number of perfect matchings of G that include and exclude e is the number of perfect matchings of G1 and G0 respectively.

But I could not come up with a proof. The main question here is: How can we proof self-reducability of #perfectMatchings?

Aside: I don't know of a formal definition of self-reduciability. I just know the intuitive phrasing "partially solving the problem results in a smaller problem of the same kind". But is there a formal definition?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

To count all perfect matchings containing an edge $e = (x,y)$, simply remove both endpoints $x,y$. To count all perfect matching not containing the edge $e$, simply remove the edge.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks, this makes sense. Just that I got the notion of self-reducibility correct: As in both cases, the number of edges decreases by at least 1, it is self-reducible? $\endgroup$
    – bingo_b
    Commented Nov 19, 2020 at 9:41
  • $\begingroup$ Self-reducibility is a somewhat informal notion, though there might be formalizations floating around in some papers. $\endgroup$
    – Yuval Filmus
    Commented Nov 19, 2020 at 9:43

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.