# Complexity of optimal elimination for a planar tensor network

Edit Dec 15 it's not obvious this problem is tractable when further restricting to trees, see cs.SE question

Suppose we need to sum out variables in a tensor network (a factor graph where each variable appears in 2 factors). I'm interested in the cost of finding an optimal summation strategy. Optimal in a sense of the number of arithmetic operations needed to compute the sum. This is equivalent to the cost of finding contraction tree which minimizes the sum over vertex congestions, see Eq. 5 of J Gray contraction paper.

For instance, compute the following $$\sum_{v_1,v_2,v_3,v_4} f_1(v_1,v_2)f_2(v_2,v_3)f_3(v_3,v_4)f_4(v_4,v_1)$$

Using tensor network diagram notation we represent each factor as a vertex, and connect two factors if they share a variable. This turns above summation into a cycle graph below.

Optimal elimination order reduces to optimal polygon triangulation, solvable in $$O(n \log n)$$ time. It is the matrix chain problem. What about other planar graphs?

This is also equivalent to the problem finding optimal carving decomposition. Ratcatcher algorithm takes $$O(n^3)$$ time to find minimum-width carving decomposition of an arbitrary planar graph. Can optimal decomposition also be done in $$O(n^3)$$?

Edit (to clarify discussion of Gorman's paper in the comments, adding diagram of problematic decomposition)

• Cross-posted: cs.stackexchange.com/q/145830/755
– D.W.
Dec 1 '21 at 7:09
• Optimal with respect to what? If it is number of operations, then the problem reduces to computing the vertex congestion of the graph. If it is memory, then it is the edge congestion. This paper might be helpful: drops.dagstuhl.de/opus/volltexte/2019/10402 Dec 7 '21 at 15:49
• Optimal wrt to number of arithmetic operations, same as in the Matrix Chain problem, of which this is a generalization (updated post to clarify). O'Gorman's paper above defines graph vertex congestion as the maximum over per-vertex congestions. Here the question is how hard it is to find contraction tree which minimizes sum of vertex congestions, for a planar graph Dec 7 '21 at 21:53

From Dumitrescu et al.:

In 2005, Markov and Shi showed that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph.

From Bryan O'Gorman's paper, section 2.5:

Computing the branchwidth of a graph is in general NP-hard, but can be done efficiently for planar graphs ("Call routing and the ratcatcher, P. D. Seymour & R. Thomas"). Whether computing the treewidth of a planar graph is NP-hard is an open question.

So it seems like your question is unsolved. Although I find this stuff pretty difficult so my reading might be wrong.

• I think Gorman's paper has mistakes, so I don't trust it -- what they call "tree decomposition" I think really is "carving decomposition" (I've emailed the author about it) Jan 6 at 3:38
• @Yaroslav Well it's got me confused lol. Perhaps you could first focus first on lattice graphs consisting of identical unit cells of tensors? Then variants of common contraction orders like MPS-MPO contraction, TRG, or CTMRG might be provably optimal? idk Jan 6 at 3:48
• O’Gorman’s paper uses tree embeddings, not tree decompositions. You may find the language in this paper more accessible. arxiv.org/abs/2002.01935 Jan 6 at 12:36
• They use tree embeddings to define treewidth which I don't think works, you need tree decomposition for that. Jan 6 at 12:41
• @delete000 Definition 1. in Section 3 of Gorman's defines tree decomposition as a hierarchical clustering of edges which I don't think is correct. I've added in the question example of tree/branch/carving decomposition for the network from Jakes-Schauer paper arxiv.org/abs/1908.11034 Jan 6 at 14:55