<p>If you allow weighted edges and weighted perfect matchings (instead of just counts), then yes. I don't know a &quot;nice&quot; clean graph-theoretic description, but in principle one can be extracted from the following proof.</p>
<p>In fact more generally the permanent is what's called a <em>linearly closed</em> family, meaning any linear combination <span class="math-container">$\sum_{i=1}^k \alpha_i perm_{n_i}(X_i)$</span>, where each <span class="math-container">$X_i$</span> is an <span class="math-container">$n_i \times n_i$</span> matrix of independent variables, is a p-projection of <span class="math-container">$perm_n$</span> for some <span class="math-container">$n \leq poly(k, \max\{n_i\})$</span>.</p>
<p>This follows along the lines of <a href="https://doi.org/10.1016/j.jco.2006.09.006" rel="nofollow noreferrer">Malod &amp; Portier</a>'s proof that det is linearly closed (Proposition 7). Namely, note that <span class="math-container">$f(X_1, \dotsc, X_k) = \sum_{a=1}^k \alpha_a perm_{n_a}(X_a)$</span> is in <span class="math-container">$\mathsf{VNP}$</span>: Without loss of generality, suppose <span class="math-container">$n_1 = \max\{n_i\}$</span>. Then, similar to the permanent itself, we have</p>
<p><span class="math-container">$f(X_1, \dotsc, X_k) = \sum_{E_{ij} \in \{0,1\}} \left(\prod_{i,j,i',j' : i=i' \Leftrightarrow j \neq j'} (1-E_{ij}E_{i'j'})\right)\left(\prod_{i \in [n_1]}\sum_{j \in [n_1]} E_{ij}\right)\left(\sum_{a=1}^k \alpha_a \prod_{i \in [n_a]}\sum_{j \in [n_a]} (X_{a})_{ij} E_{ij}\right)$</span></p>
<p>Now, by the VNP-completeness of perm, <span class="math-container">$f$</span> is a p-projection of the permanent, say it is the permanent of a matrix <span class="math-container">$A_f(X_1, \dotsc, X_k)$</span> whose size is polynomial in the size of the above formula, i.e. <span class="math-container">$poly(k, \max\{n_i\})$</span>. This completes the proof of linear closedness of the permanent.</p>
<p>Now, back to the question about bipartite graphs. Upon substituting <span class="math-container">$X_1, \dotsc, X_k$</span> by numerical matrices <span class="math-container">$M_1, \dotsc, M_k$</span> (such as the adjacency matrices of bipartite graphs), we then get a numerical matrix <span class="math-container">$A_f(M_1, \dotsc, M_k)$</span>, which we may take as the weighted adjacency matrix of a bipartite graph. Because Valiant's proof for the completeness of the permanent only uses the original variables (from the matrices <span class="math-container">$M_1, \dotsc, M_k$</span> in our case) and constants <span class="math-container">$0,1,-1,2,3, 1/2$</span>, our final matrix <span class="math-container">$A_f(M_1, \dotsc, M_k)$</span> - and the corresponding bipartite graph - also has those weights.</p>
<p>Note: although {0,1}-permanent is #P-complete, the proof I know uses some modular arithmetic, so it seems not to go through in the purely algebraic setting. In other words, I don't know how to fix the above to produce an unweighted bipartite graph even if the original graphs were unweighted. Even more, if one is to use the completeness of perm, then both the use of 1/2 and the use of negative constants seem crucial. For 1/2, this is because in characteristic 2 we have per=det, so if the proof of VNP-completeness worked in characteristic 2 we'd have VP=VNP in characteristic 2. For the use of negative numbers, see (shameless self plug) the paragraphs around Rmk 1.2 at the top of p. 4 <a href="http://dx.doi.org/10.4086/toc.2017.v013a018" rel="nofollow noreferrer">here</a>.</p>

CC BY-SA 4.0
2022-04-20T00:16:21.517Z
immensely thankful.. I also wonder if I replace bipartite graphs by planar graphs, number of perfect matchings by number of spanning trees and polynomial time by Logspace would we get Logspace +-reducibility of spanning trees of planar graphs?
Turbo
CC BY-SA 4.0
2022-04-20T00:38:37.330Z
So bottom line (forgetting about graphs and dealing as matrices as such) is in $P$-time or maybe even in $LOGSPACE$ one can construct a matrix $C$ from given matrices $A$ and $B$ with $\mathbb Q$ entries so that all three have rational entries and per(C)=per(A)+per(B) and $C$ has $poly(n)$ size where $A$ and $B$ are $poly(n)$ sized?
Turbo
CC BY-SA 4.0
2023-05-12T16:22:57.890Z
Do you know the degree of $poly(k,\max\{n_i\})$? Can it be  linear?
Turbo
CC BY-SA 4.0
2023-05-12T16:42:08.440Z
I don't know. I don't even know what the degree is from the construction above (but it should just be an exercise in unwrapping the construction to calculate it).
Joshua Grochow
CC BY-SA 4.0
2023-05-12T16:42:27.793Z
Why should $1/2$ occur? Mod $2$ value of sum of permanents is calculated directly from determinant! I do not understand why Valiant's proof comes here?
Turbo
CC BY-SA 4.0
2023-05-12T19:44:30.440Z
I might believe that there could be a proof that perm is a linearly closed family that did not use 1/2, but my proof above uses the VNP-completeness result as part of the proof, and the VNP-completeness of perm needs 1/2 (unless VNP=VDET over GF(2)).
Joshua Grochow
CC BY-SA 4.0
2023-05-17T07:03:46.770Z
Just to be clear... before you get the matrix with entries containing $1/2$, do you get an integer matrix? Valiant's proof in https://en.wikipedia.org/wiki/♯P-completeness_of_01-permanent says the matrix contains 0,1,2,3 and it seems 1/2 is not there in the first step.
Turbo
CC BY-SA 4.0
2023-05-17T07:10:55.947Z
I guess I am looking for whether the matrix A_f is integer entried in "VNP-completeness of perm, 
 is a p-projection of the permanent, say it is the permanent of a matrix (1,…,)"?
Turbo
CC BY-SA 4.0
2023-05-17T20:48:22.890Z
In Valiant's reduction if you don't include 1/2, what you get is $2^{poly(n,m)}$ times the number of satisfying assignments from the original SAT instance, where the poly in the exponent is some fixed polynomial (like $n^2$?) that I don't remember at the moment. So if you want the number of satisfying assignments, or even to know whether it's nonzero or not, you have to be able to divide by 2. For VNP-completeness, you need the recover the original polynomial on the nose (not just a multiple), so you need to divide by 2. (As needed given det not being VNP-complete assuming Valiant's Conj.)
Joshua Grochow
CC BY-SA 4.0
2023-05-24T06:58:23.130Z
Is there a reference for the relation between occurrence of 1/2 and representation for 'exact' number of satisfying assignments to given 3CNF form? I looked at https://www.sciencedirect.com/science/article/pii/0304397579900446 and I do not see 1/2 there.
Turbo
CC BY-SA 4.0
2023-05-24T14:54:31.367Z
It's implicit in the factor of $4^{t(F)}$ in Lemma 3.1. And in the contrast between Theorems 2 (perm is $Mod_K P$-hard for all $K$ that aren't a power of 2) and Theorem 3 (perm mod $2^k$ can be computed in $O(n^{4k-3})$ time). Basically, if you could do everything with rational numbers that *never* involved dividing by 2, then you could take everything mod 2 and it would still work, but now it'd be in P because perm=det mod 2.
Joshua Grochow
CC BY-SA 4.0
2022-04-19T23:10:59.323Z
2022-04-19T23:10:59.323Z
Joshua Grochow
<p>Suppose we have two bipartite graphs <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with perfect matching count <span class="math-container">$P_1$</span> and <span class="math-container">$P_2$</span> respectively then their disjoint union gives a bipartite graph with perfect matching <span class="math-container">$P_1P_2$</span>.</p>
<blockquote>
<ol>
<li>Is there a graph construction in polynomial time to get a bipartite graph from  <span class="math-container">$G_1$</span> and <span class="math-container">$G_2$</span> with perfect matching count <span class="math-container">$P_1+P_2$</span> without knowing <span class="math-container">$P_1$</span> or <span class="math-container">$P_2$</span>?</li>
</ol>
</blockquote>
<blockquote>
<ol start="2">
<li>How about if we are allowed to know <span class="math-container">$P_2$</span> alone?</li>
</ol>
</blockquote>

CC BY-SA 3.0
2017-08-09T20:33:39.697Z
FYI, #P closure under addition means given $f,g \in \mathsf{\# P}$, $f+g$ is in $\mathsf{\# P}$ - this is the sum of two different functions on the same input. You are asking about addition of the same function on two different inputs....
Joshua Grochow
CC BY-SA 3.0
2017-08-09T20:58:20.813Z
What do you mean by "the decision version" of a #P problem? Its graph? Subgraph? Bitgraph? Something else?
Emil Jeřábek
CC BY-SA 3.0
2017-08-10T02:17:27.427Z
@777: I wasn't asking, I was stating a result. You can get a permanent back (with perhaps multiplying $P_1 + P_2$ by some power of 2) using Valiant's $\mathsf{\# P}$-completeness of perm.
Joshua Grochow
CC BY-SA 3.0
2017-08-10T04:13:04.007Z
Okay. That wasn't the point of my original comment, though. My point was: it's not *just* that you don't want the power of 2; you are asking a *different type* of question. Instead of asking for the sum of two functions of the same input, you are asking for the sum of one function over two different inputs.
Joshua Grochow
CC BY-SA 3.0
2017-08-10T07:25:46.897Z
@777 The function $f$ counts the number of accepting paths of the machine on what input?
Sasho Nikolov
CC BY-SA 3.0
2017-08-10T07:57:07.940Z
OK thank you for correcting me and I kept the query since I think it is still interesting. With what I know now I do not think there is any reason to believe such construction exists.
Turbo
CC BY-SA 4.0
2021-11-12T16:59:33.083Z
Here's an idea that fails.  Given $G_1$ and $G_2$, in polytime, construct a non-deterministic poly-time TM $M$ such that the number of accepting computations of $M$ when run on blank tape is the number of perfect matchings in $G_1$ plus the number of perfect matchings in $G_2$.  Then use a parsimonious reduction to produce, from $M$, a bipartite graph $G'$ such that the number of perfect matchings in $G'$ equals this number of accepting computations. *This last step fails, because there is no such reduction unless P=NP.*
Neal Young
CC BY-SA 4.0
2021-11-12T22:35:34.487Z
Yes I think p is np might be necessary.
Turbo
CC BY-SA 4.0
2022-01-16T18:18:03.620Z
@NealYoung If I replace bipartite graphs by planar graphs, number of perfect matchings by number of spanning trees and polynomial time by Logspace would we get Logspace $+$-reducibility?
Turbo
CC BY-SA 4.0
2022-01-16T22:12:26.790Z
I don't know... Looks like approximating the number of spanning trees is doable in log space ?  https://arxiv.org/abs/1608.01426
Neal Young
CC BY-SA 4.0
2022-02-22T23:07:38.257Z
@NealYoung Do you think if P is NP this + reducibility is possible for perfect matchings? Likewise if L is NL is the + reducibility possible for spanning trees?
Turbo
<cc.complexity-theory><counting-complexity><matching><permanent><bipartite-graphs>
Is Permanent $+$-reducible?
Turbo
# Is Permanent $+$-reducible?

(Asked by: username_0 on 2017-08-09)

Suppose we have two bipartite graphs $G\_1$ and $G\_2$ with perfect matching count $P\_1$ and $P\_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P\_1P\_2$.

> 1. Is there a graph construction in polynomial time to get a bipartite graph from $G\_1$ and $G\_2$ with perfect matching count $P\_1+P\_2$ without knowing $P\_1$ or $P\_2$?

> 2. How about if we are allowed to know $P\_2$ alone?

**Tags:** cc.complexity-theory, counting-complexity, matching, permanent, bipartite-graphs

> **Comments:**
> **username_1**: FYI, #P closure under addition means given $f,g \in \mathsf{\# P}$, $f+g$ is in $\mathsf{\# P}$ - this is the sum of two different functions on the same input. You are asking about addition of the same function on two different inputs....  
> **username_2**: What do you mean by "the decision version" of a #P problem? Its graph? Subgraph? Bitgraph? Something else?  
> **username_1**: @777: I wasn't asking, I was stating a result. You can get a permanent back (with perhaps multiplying $P_1 + P_2$ by some power of 2) using Valiant's $\mathsf{\# P}$-completeness of perm.  
> **username_1**: Okay. That wasn't the point of my original comment, though. My point was: it's not *just* that you don't want the power of 2; you are asking a *different type* of question. Instead of asking for the sum of two functions of the same input, you are asking for the sum of one function over two different inputs.  
> **username_3**: @777 The function $f$ counts the number of accepting paths of the machine on what input?  
> **username_0**: OK thank you for correcting me and I kept the query since I think it is still interesting. With what I know now I do not think there is any reason to believe such construction exists.  
> **username_4**: Here's an idea that fails.  Given $G_1$ and $G_2$, in polytime, construct a non-deterministic poly-time TM $M$ such that the number of accepting computations of $M$ when run on blank tape is the number of perfect matchings in $G_1$ plus the number of perfect matchings in $G_2$.  Then use a parsimonious reduction to produce, from $M$, a bipartite graph $G'$ such that the number of perfect matchings in $G'$ equals this number of accepting computations. *This last step fails, because there is no such reduction unless P=NP.*  
> **username_0**: Yes I think p is np might be necessary.  
> **username_0**: @NealYoung If I replace bipartite graphs by planar graphs, number of perfect matchings by number of spanning trees and polynomial time by Logspace would we get Logspace $+$-reducibility?  
> **username_4**: I don't know... Looks like approximating the number of spanning trees is doable in log space ?  https://arxiv.org/abs/1608.01426  
> **username_0**: @NealYoung Do you think if P is NP this + reducibility is possible for perfect matchings? Likewise if L is NL is the + reducibility possible for spanning trees?  

---

## 1 answers

### Answer by username_1 on 2022-04-19. Score: 4 | Accepted answer

If you allow weighted edges and weighted perfect matchings (instead of just counts), then yes. I don't know a "nice" clean graph-theoretic description, but in principle one can be extracted from the following proof.

In fact more generally the permanent is what's called a *linearly closed* family, meaning any linear combination $\sum\_{i=1}^k \alpha\_i perm\_{n\_i}(X\_i)$, where each $X\_i$ is an $n\_i \times n\_i$ matrix of independent variables, is a p-projection of $perm\_n$ for some $n \leq poly(k, \max\{n\_i\})$.

This follows along the lines of [Malod & Portier](https://doi.org/10.1016/j.jco.2006.09.006)'s proof that det is linearly closed (Proposition 7). Namely, note that $f(X\_1, \dotsc, X\_k) = \sum\_{a=1}^k \alpha\_a perm\_{n\_a}(X\_a)$ is in $\mathsf{VNP}$: Without loss of generality, suppose $n\_1 = \max\{n\_i\}$. Then, similar to the permanent itself, we have

$f(X\_1, \dotsc, X\_k) = \sum\_{E\_{ij} \in \{0,1\}} \left(\prod\_{i,j,i',j' : i=i' \Leftrightarrow j \neq j'} (1-E\_{ij}E\_{i'j'})\right)\left(\prod\_{i \in [n\_1]}\sum\_{j \in [n\_1]} E\_{ij}\right)\left(\sum\_{a=1}^k \alpha\_a \prod\_{i \in [n\_a]}\sum\_{j \in [n\_a]} (X\_{a})\_{ij} E\_{ij}\right)$

Now, by the VNP-completeness of perm, $f$ is a p-projection of the permanent, say it is the permanent of a matrix $A\_f(X\_1, \dotsc, X\_k)$ whose size is polynomial in the size of the above formula, i.e. $poly(k, \max\{n\_i\})$. This completes the proof of linear closedness of the permanent.

Now, back to the question about bipartite graphs. Upon substituting $X\_1, \dotsc, X\_k$ by numerical matrices $M\_1, \dotsc, M\_k$ (such as the adjacency matrices of bipartite graphs), we then get a numerical matrix $A\_f(M\_1, \dotsc, M\_k)$, which we may take as the weighted adjacency matrix of a bipartite graph. Because Valiant's proof for the completeness of the permanent only uses the original variables (from the matrices $M\_1, \dotsc, M\_k$ in our case) and constants $0,1,-1,2,3, 1/2$, our final matrix $A\_f(M\_1, \dotsc, M\_k)$ - and the corresponding bipartite graph - also has those weights.

Note: although {0,1}-permanent is #P-complete, the proof I know uses some modular arithmetic, so it seems not to go through in the purely algebraic setting. In other words, I don't know how to fix the above to produce an unweighted bipartite graph even if the original graphs were unweighted. Even more, if one is to use the completeness of perm, then both the use of 1/2 and the use of negative constants seem crucial. For 1/2, this is because in characteristic 2 we have per=det, so if the proof of VNP-completeness worked in characteristic 2 we'd have VP=VNP in characteristic 2. For the use of negative numbers, see (shameless self plug) the paragraphs around Rmk 1.2 at the top of p. 4 [here](http://dx.doi.org/10.4086/toc.2017.v013a018).

> **Comments:**
> **username_0**: immensely thankful.. I also wonder if I replace bipartite graphs by planar graphs, number of perfect matchings by number of spanning trees and polynomial time by Logspace would we get Logspace +-reducibility of spanning trees of planar graphs?  
> **username_0**: So bottom line (forgetting about graphs and dealing as matrices as such) is in $P$-time or maybe even in $LOGSPACE$ one can construct a matrix $C$ from given matrices $A$ and $B$ with $\mathbb Q$ entries so that all three have rational entries and per(C)=per(A)+per(B) and $C$ has $poly(n)$ size where $A$ and $B$ are $poly(n)$ sized?  
> **username_0**: Do you know the degree of $poly(k,\max\{n_i\})$? Can it be  linear?  
> **username_1**: I don't know. I don't even know what the degree is from the construction above (but it should just be an exercise in unwrapping the construction to calculate it).  
> **username_0**: Why should $1/2$ occur? Mod $2$ value of sum of permanents is calculated directly from determinant! I do not understand why Valiant's proof comes here?  
> **username_1**: I might believe that there could be a proof that perm is a linearly closed family that did not use 1/2, but my proof above uses the VNP-completeness result as part of the proof, and the VNP-completeness of perm needs 1/2 (unless VNP=VDET over GF(2)).  
> **username_0**: Just to be clear... before you get the matrix with entries containing $1/2$, do you get an integer matrix? Valiant's proof in https://en.wikipedia.org/wiki/♯P-completeness_of_01-permanent says the matrix contains 0,1,2,3 and it seems 1/2 is not there in the first step.  
> **username_0**: I guess I am looking for whether the matrix A_f is integer entried in "VNP-completeness of perm,   is a p-projection of the permanent, say it is the permanent of a matrix (1,…,)"?  
> **username_1**: In Valiant's reduction if you don't include 1/2, what you get is $2^{poly(n,m)}$ times the number of satisfying assignments from the original SAT instance, where the poly in the exponent is some fixed polynomial (like $n^2$?) that I don't remember at the moment. So if you want the number of satisfying assignments, or even to know whether it's nonzero or not, you have to be able to divide by 2. For VNP-completeness, you need the recover the original polynomial on the nose (not just a multiple), so you need to divide by 2. (As needed given det not being VNP-complete assuming Valiant's Conj.)  
> **username_0**: Is there a reference for the relation between occurrence of 1/2 and representation for 'exact' number of satisfying assignments to given 3CNF form? I looked at https://www.sciencedirect.com/science/article/pii/0304397579900446 and I do not see 1/2 there.  
> **username_1**: It's implicit in the factor of $4^{t(F)}$ in Lemma 3.1. And in the contrast between Theorems 2 (perm is $Mod_K P$-hard for all $K$ that aren't a power of 2) and Theorem 3 (perm mod $2^k$ can be computed in $O(n^{4k-3})$ time). Basically, if you could do everything with rational numbers that *never* involved dividing by 2, then you could take everything mod 2 and it would still work, but now it'd be in P because perm=det mod 2.  

---

