Consider a square, sparse matrix $M[a_1,a_2]:1\leq a_1,a_2\leq N$ of non-negative entries. My question is for a given even $L>1$, how to efficiently compute the sum $$ S:=\sum_{a!}M[a_1,a_2]\cdot M[a_3,a_4]\cdots M[a_{L-1},a_L] $$ where sum ranges only over index vectors $(a_1,a_2,\ldots,a_L)$ all of whose entries are unique.

I'm also interested in methods to compute a part of the full sum. Here is one: Suppose we color half of the indexes $\{1,\ldots,N\}$ white, and the others black, and consider only those terms of $S$ for which each factor $M[a,b]$ has a white index for $a$ and a black index for $b$. This post gives an efficient recursive calculation. Apparently this trick only gets us an exponentially small proportion of the full sum.

Consider the adjacency graph, $G_M$, which is the graph with $N$ nodes having edges between $a_1$ and $a_2$ iff $M[a_1,a_2]\neq 0$. There seems to be some connection between the complexity of $S$ and the separability of $G_M$. For instance, the result of the previous paragraph means that $S$ can be computed efficiently if $G_M$ is bipartite.

For another example, suppose that $G$ is a union of two disconnected subgraphs $G_1,G_2$ which are connected by a single edge $E=[1,2]$ where $j\in G_j$. Let $S_j$ denote the partial sum obtained by restricting to elements of $G_j$. Then $S$ can be written as a sum of two terms, one of which contains $M[1,2]$ and the other of which doesn't; each term can be factored over the elements of $G_j$ and therefore contain significantly fewer terms than $S$. Thus, near-disconnectedness of $G$ seems to imply a substantial reduction in the complexity of computing $S$.

That's as far as I've gotten. Thanks for reading!


For $M$ an adjacency matrix of a graph, this is counting matchings of order $L.$ For $L=N/2$ it is counting perfect matchings, which is not known to have an efficient algorithm. Your problem is basically counting weighted perfect matchings, and you can apply any of the same algorithms (see for example the discussion in this paper). The sparseness doesn't help much since if you lengthen each edge by replacing it with a large odd-length path you get a graph with the same number of perfect matchings.

The method you linked to is not just the bipartite case of your problem. For example for a complete bipartite graph $K_{N/2,N/2}$ and $L=N/2,$ the restricted $S$ should be $(N/2)!$ (and the unrestricted $S$ would be $2^{N/2}(N/2)!$) but their $E_d$ would be $1.$ If you try a simple recursive approach for $S$ you'll find it takes exponential time.

  • $\begingroup$ Thank you! Is it true that restricting the sum to a given black/white coloring of the nodes accounts only for an exponentially-small (exponentially in $L$) proportion of the total? (I suggested in the post that a quarter of the total terms are accounted for by a given bipartite coloring; that seems to have been crazy talk.) $\endgroup$ – MathManM Nov 30 '17 at 13:14
  • $\begingroup$ @MathManM: for the unrestricted sum you can orient each (white,black) pair either way, which gives a factor of $2^{L/2}.$ $\endgroup$ – Dap Nov 30 '17 at 13:33
  • $\begingroup$ Also, can you comment on the complexity of the recursion given in the link? $\endgroup$ – MathManM Nov 30 '17 at 14:02
  • $\begingroup$ @MathManM: it's a quadratic dynamic programming recursion, but it relies on the fact that there is a recursion into a polynomial number of subproblems (basically initial segments of the numbers) $\endgroup$ – Dap Nov 30 '17 at 14:07
  • $\begingroup$ Thanks for your help, and for the excellent paper you referenced. $\endgroup$ – MathManM Nov 30 '17 at 14:18

Your Answer

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

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