# FPRAS for Perfect Matching

If you have FPRASes for counting number of matchings of size $\leq n$ and size $\leq n-1$, can you get an FPRAS for counting number of matchings of size $n$ (i.e perfect matchings)?

No. Knowing $x$ and $y$ to within multiplicative error bounds of $1\pm\varepsilon$ does not give you a multiplicative error bound on $x-y$. In particular, if $x=y$, being allowed only multiplicative error means that an FPRAS for $x-y$ would have to return exactly zero with probability at least $\tfrac34$, whereas you could end up returning any value $v$ such that $|v|\leq 2\varepsilon\cdot |x|$.
• Although what you say is true in general, are you sure it applies in this case? For example, a-priori, it could be that the number of matchings of size less than or equal to n is dominated by the number of matchings of size exactly n, in which case you would have $y \ll x$, so $x - y \ge (1-\epsilon) x$. Also, perhaps, given a graph G, you might be able to construct a graph G' where this imbalance occurs, and the number of matchings of size n' in G' tells you approximately the number of size n in G... Commented Feb 9, 2014 at 4:24
• @NealYoung Are you saying that the total number of matchings (of any kind) may be much greater the number of strictly imperfect matchings? This can't be true, as there's a simple injective mapping from perfect matchings to disjoint sets of $n/2$ imperfect matchings, so perfect matchings only account for a small fraction of total matchings. Commented Feb 9, 2014 at 4:50
• @NealYoung The number of matchings of size exactly $n$ can't dominate the number of strictly smaller matchings because deleting any nonempty subset of the edges from a matching produces a smaller matching. There are many more small matchings than large ones. And, yes, the situation I describe can occur with matchings: just consider the case where there are no perfect matchings. Because an FPRAS is randomized, there's no reason it should give exactly the same answer for "matchings of size $n$" as it does for "matchings of size $n-1$" so the subtraction won't reliably return zero, which it must. Commented Feb 9, 2014 at 9:32
• @NealYoung map any perfect matching $M$ to the set of size-$(n/2-1)$ matchings consisting of $M$ minus one edge. This set has size $n/2$. Sets constructed this way are disjoint because each size-$(n/2-1)$ matching has exactly one completion into a perfect matching (namely, connecting the only two unpaired vertices), so their union form a set $n/2$ times larger than the set of perfect matchings. I agree with your original point that there might be some perfect-matching specific trick that can be used in this context, but I have no idea what that would be (if it exists). Commented Feb 9, 2014 at 20:58