Complexity of optimal elimination for a planar tensor network

Question

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.

enter image description here

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)

enter image description here

enter image description here

enter image description here

enter image description here

• D.W.: Cross-posted: cs.stackexchange.com/q/145830/755
• delete000: 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
• Yaroslav Bulatov: 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

Answer 1

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.

• Yaroslav Bulatov: 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)
• Jordan Taylor: @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
• delete000: 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
• Yaroslav Bulatov: They use tree embeddings to define treewidth which I don't think works, you need tree decomposition for that.
• Yaroslav Bulatov: @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