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$ but knowing $P_2$?

  • 1
    $\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$ – Joshua Grochow Aug 9 '17 at 20:33
  • $\begingroup$ What do you mean by "the decision version" of a #P problem? Its graph? Subgraph? Bitgraph? Something else? $\endgroup$ – Emil Jeřábek Aug 9 '17 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$ – Joshua Grochow Aug 10 '17 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$ – Joshua Grochow Aug 10 '17 at 4:13
  • $\begingroup$ @777 The function $f$ counts the number of accepting paths of the machine on what input? $\endgroup$ – Sasho Nikolov Aug 10 '17 at 7:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.