Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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$.
- 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$?
- How about if we are allowed to know $P_2$ alone?
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'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.
