<p>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 <em>exactly</em> zero with probability at least $\tfrac34$, whereas you could end up returning any value $v$ such that $|v|\leq 2\varepsilon\cdot |x|$.</p>

CC BY-SA 3.0
2014-02-09T04:24:52.517Z
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...
Neal Young
CC BY-SA 3.0
2014-02-09T04:50:06.427Z
@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.
Yonatan N
CC BY-SA 3.0
2014-02-09T05:31:08.237Z
@YonatanN, (i) What you say seems likely.  Can you give a proof that the number of matchings of size n is a vanishing fraction?  (ii) Even if that's the case, are you sure it answers Kaveh's question?  E.g. does it preclude reducing the problem of estimating perfect matchings in one graph G to the problem of estimating the number of matchings (perfect or otherwise) in other graphs G' that I might construct for the purpose of estimating pm's in G?
Neal Young
CC BY-SA 3.0
2014-02-09T09:32:58.533Z
@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.
David Richerby
CC BY-SA 3.0
2014-02-09T20:58:05.667Z
@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).
Yonatan N
CC BY-SA 3.0
2014-02-09T23:16:03.257Z
@YonatanN, oh, good, that's a nice argument.. definitely shows that the perfect matchings are at most a (2/n) fraction (and that bound is tight for the (n/2)-edge graph formed by a single perfect matching).  David: what about the possibility of a reduction (i.e., to estimate the perfect matchings for G, asking the FPRAS about graphs G' other than the given graph G)?
Neal Young
CC BY-SA 3.0
2014-02-08T16:15:28.997Z
2014-02-08T21:45:20.427Z
2014-02-08T21:45:20.427Z
David Richerby
<p>If you have <a href="http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme#Randomized" rel="nofollow">FPRAS</a>es 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)? </p>

<ds.algorithms><approximation-algorithms>
FPRAS for Perfect Matching
Unknown
# FPRAS for Perfect Matching

(Asked by: username_0 on 2014-02-08)

If you have [FPRAS](http://en.wikipedia.org/wiki/Polynomial-time_approximation_scheme#Randomized)es 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)?

**Tags:** ds.algorithms, approximation-algorithms


---

## 1 answers

### Answer by username_1 on 2014-02-08. Score: 3

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|$.

> **Comments:**
> **username_2**: 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...  
> **username_3**: @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.  
> **username_2**: @YonatanN, (i) What you say seems likely.  Can you give a proof that the number of matchings of size n is a vanishing fraction?  (ii) Even if that's the case, are you sure it answers Kaveh's question?  E.g. does it preclude reducing the problem of estimating perfect matchings in one graph G to the problem of estimating the number of matchings (perfect or otherwise) in other graphs G' that I might construct for the purpose of estimating pm's in G?  
> **username_1**: @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.  
> **username_3**: @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).  
> **username_2**: @YonatanN, oh, good, that's a nice argument.. definitely shows that the perfect matchings are at most a (2/n) fraction (and that bound is tight for the (n/2)-edge graph formed by a single perfect matching).  David: what about the possibility of a reduction (i.e., to estimate the perfect matchings for G, asking the FPRAS about graphs G' other than the given graph G)?  

---

