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.