0

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!

MathManM
  • 525

1 Answers1

1

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.

Dap
  • 25,286
  • 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.) – MathManM Nov 30 '17 at 13:14
  • @MathManM: for the unrestricted sum you can orient each (white,black) pair either way, which gives a factor of $2^{L/2}.$ – Dap Nov 30 '17 at 13:33
  • Also, can you comment on the complexity of the recursion given in the link? – MathManM Nov 30 '17 at 14:02
  • @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) – Dap Nov 30 '17 at 14:07
  • Thanks for your help, and for the excellent paper you referenced. – MathManM Nov 30 '17 at 14:18
  • I took your previous comment to mean that the dynamic programming recursion described in my other post has quadratic complexity, but how can this be since it counts all matchings of a bipartite graph? Did I misunderstand? What did you mean by 'quadratic dynamic programming'? – MathManM Dec 03 '17 at 02:15
  • @MathManM: that doesn’t count all matchings - as I said it would only count one matching for $K_{d,d}.$ It only counts “non-crossing” matchings of order $d,$ by which I mean if $a_i<a_j$ then $b_i<b_j.$ – Dap Dec 03 '17 at 06:41
  • Yep you're right; I see it now. Suppose we restrict the problem further to sparse bipartite graphs where $L$ is not too large. Does the bounded treewidth approach described in your references still apply? If not, what is the preferred approach? – MathManM Dec 03 '17 at 23:06
  • @MathManM: with bounded treewidth you can compute the (weighted) matching polynomial, whose coefficients tell you the number of matchings of each order. – Dap Dec 04 '17 at 00:44
  • You seem to be suggesting that the computing the matching polynomial coefficients is an effective technique against sparse bipartite graphs for small $L$? Do sparse bipartite graphs have small treewidth? – MathManM Dec 04 '17 at 01:32
  • @MathManM: I was just mentioning that there are algorithms for the matching polynomial of bounded treewidth graphs. If you have any further questions please ask them as stackexchange questions. – Dap Dec 04 '17 at 01:41