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?