4
$\begingroup$

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$?
  1. How about if we are allowed to know $P_2$ alone?
$\endgroup$
11
  • 2
    $\begingroup$ 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.... $\endgroup$ Commented Aug 9, 2017 at 20:33
  • $\begingroup$ What do you mean by "the decision version" of a #P problem? Its graph? Subgraph? Bitgraph? Something else? $\endgroup$ Commented Aug 9, 2017 at 20:58
  • $\begingroup$ @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. $\endgroup$ Commented Aug 10, 2017 at 2:17
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Aug 10, 2017 at 4:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Commented Nov 12, 2021 at 16:59

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
11
  • $\begingroup$ 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? $\endgroup$
    – Turbo
    Commented Apr 20, 2022 at 0:16
  • 1
    $\begingroup$ 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? $\endgroup$
    – Turbo
    Commented Apr 20, 2022 at 0:38
  • $\begingroup$ Do you know the degree of $poly(k,\max\{n_i\})$? Can it be linear? $\endgroup$
    – Turbo
    Commented May 12, 2023 at 16:22
  • 2
    $\begingroup$ 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.) $\endgroup$ Commented May 17, 2023 at 20:48
  • 2
    $\begingroup$ 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. $\endgroup$ Commented May 24, 2023 at 14:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.