<p>From <a href="https://arxiv.org/abs/1807.04599" rel="nofollow noreferrer">Dumitrescu et al.</a>:</p>
<blockquote>
<p>In 2005, <a href="https://arxiv.org/abs/quant-ph/0511069" rel="nofollow noreferrer">Markov and Shi showed</a> that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph.</p>
</blockquote>
<p>From <a href="https://arxiv.org/abs/1906.00013" rel="nofollow noreferrer">Bryan O'Gorman's paper</a>, section 2.5:</p>
<blockquote>
<p>Computing the branchwidth of a graph is in general NP-hard, but can be
done efficiently for planar graphs <a href="https://link.springer.com/article/10.1007%2FBF01215352" rel="nofollow noreferrer">(&quot;Call routing and the ratcatcher, P. D. Seymour &amp; R. Thomas&quot;)</a>. Whether computing the treewidth of a planar graph is NP-hard is an open question.</p>
</blockquote>
<p>So it seems like your question is unsolved. Although I find this stuff pretty difficult so my reading might be wrong.</p>

CC BY-SA 4.0
2022-01-06T03:38:03.877Z
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)
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T03:48:36.717Z
@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
Jordan Taylor
CC BY-SA 4.0
2022-01-06T12:36:34.027Z
O’Gorman’s paper uses tree *embeddings*, not tree decompositions. You may find the language in this paper more accessible. https://arxiv.org/abs/2002.01935
delete000
CC BY-SA 4.0
2022-01-06T12:41:34.710Z
They use tree embeddings to define treewidth which I don't think works, you need tree decomposition for that.
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T14:55:41.573Z
@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 https://arxiv.org/abs/1908.11034
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T14:57:38.890Z
@Jordan Johnny Gray pointed out this paper which describes polynomial-time algorithm for optimal contraction of a tree structured tensor networks, however both of us had trouble reading it, their wording is confusing -- [Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees](https://dr.ntu.edu.sg/bitstream/10356/141943/2/Towards%20a%20polynomial%20algorithm%20for%20optimal%20contraction%20sequence%20of%20tensor%20networks%20from%20trees.pdf)
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T15:17:25.420Z
O’Gorman uses tree embeddings to define and bound vertex and edge congestions, *not* the treewidth. The relevant treewidth for TN contraction is that of the line graph of the network anyway, not the treewidth of the network itself.
delete000
CC BY-SA 4.0
2022-01-06T16:10:06.657Z
@delete000 Equation 1 on page 7 of O'Gorman [paper](https://arxiv.org/pdf/1906.00013.pdf) defines treewidth using tree embedding
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T17:30:24.767Z
I don’t see that equation defining treewidth using a tree embedding. I see it defining treewidth using a tree *decomposition*.
delete000
CC BY-SA 4.0
2022-01-06T18:58:56.767Z
That same section says ""A [tree decomposition|...] of a vertex weighted graph G is a tuple (T,b) of a binary tree ..."" So it defines tree decomposition in terms of tree embedding, which I don't think works. I posted diagram of tree/carving/branch decompositions of 3x2 grid graph in the question. You can see that carving/branch decompositions can be defined in terms of tree embedding, but not tree decomposition
Yaroslav Bulatov
CC BY-SA 4.0
2022-01-06T03:00:16.800Z
2022-01-06T03:00:16.800Z
Jordan Taylor
<p><strong>Edit Dec 15</strong> it's not obvious this problem is tractable when further restricting to trees, see cs.SE <a href="https://cs.stackexchange.com/questions/146680/generalizing-matrix-chain-problem-optimal-summation-in-a-tree">question</a></p>
<p>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 <a href="https://quantum-journal.org/papers/q-2021-03-15-410/pdf/" rel="nofollow noreferrer">paper</a>.</p>
<p>For instance, compute the following
<span class="math-container">$$\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)$$</span></p>
<p>Using tensor network diagram <a href="https://tensornetwork.org/diagrams/" rel="nofollow noreferrer">notation</a> 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.</p>
<p><a href="https://i.sstatic.net/HQgiA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/HQgiA.png" alt="enter image description here" /></a></p>
<p>Optimal elimination order reduces to optimal polygon triangulation, solvable in <span class="math-container">$O(n \log n)$</span> time. It is the matrix chain <a href="https://en.wikipedia.org/wiki/Matrix_chain_multiplication#More_efficient_algorithms" rel="nofollow noreferrer">problem</a>. What about other planar graphs?</p>
<p>This is also <a href="https://arxiv.org/abs/1908.11034" rel="nofollow noreferrer">equivalent</a> to the problem finding <strong>optimal carving decomposition</strong>. <a href="https://www.caam.rice.edu/%7Eivhicks/pb1.ijoc.pdf" rel="nofollow noreferrer">Ratcatcher</a> algorithm takes <span class="math-container">$O(n^3)$</span> time to find minimum-width carving decomposition of an arbitrary planar graph. Can optimal decomposition also be done in <span class="math-container">$O(n^3)$</span>?</p>
<p><strong>Edit</strong> (to clarify discussion of Gorman's paper in the comments, adding diagram of problematic decomposition)</p>
<p><a href="https://i.sstatic.net/cNmHS.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/cNmHS.png" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/uNEe5.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/uNEe5.png" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/J6pQx.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/J6pQx.jpg" alt="enter image description here" /></a></p>
<p><a href="https://i.sstatic.net/3PgS2.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/3PgS2.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2021-12-01T07:09:47.570Z
Cross-posted: https://cs.stackexchange.com/q/145830/755
D.W.
CC BY-SA 4.0
2021-12-07T15:49:14.083Z
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: https://drops.dagstuhl.de/opus/volltexte/2019/10402/
delete000
CC BY-SA 4.0
2021-12-07T21:53:27.567Z
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
Yaroslav Bulatov
<ds.algorithms><reference-request><graph-theory><graph-algorithms><planar-graphs>
Complexity of optimal elimination for a planar tensor network
Yaroslav Bulatov
# Complexity of optimal elimination for a planar tensor network

(Asked by: username_0 on 2021-11-30)

**Edit Dec 15** it's not obvious this problem is tractable when further restricting to trees, see cs.SE [question](https://cs.stackexchange.com/questions/146680/generalizing-matrix-chain-problem-optimal-summation-in-a-tree)

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](https://quantum-journal.org/papers/q-2021-03-15-410/pdf/).

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](https://tensornetwork.org/diagrams/) 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](https://i.sstatic.net/HQgiA.png)](https://i.sstatic.net/HQgiA.png)

Optimal elimination order reduces to optimal polygon triangulation, solvable in $O(n \log n)$ time. It is the matrix chain [problem](https://en.wikipedia.org/wiki/Matrix_chain_multiplication#More_efficient_algorithms). What about other planar graphs?

This is also [equivalent](https://arxiv.org/abs/1908.11034) to the problem finding **optimal carving decomposition**. [Ratcatcher](https://www.caam.rice.edu/%7Eivhicks/pb1.ijoc.pdf) 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](https://i.sstatic.net/cNmHS.png)](https://i.sstatic.net/cNmHS.png)

[![enter image description here](https://i.sstatic.net/uNEe5.png)](https://i.sstatic.net/uNEe5.png)

[![enter image description here](https://i.sstatic.net/J6pQx.jpg)](https://i.sstatic.net/J6pQx.jpg)

[![enter image description here](https://i.sstatic.net/3PgS2.png)](https://i.sstatic.net/3PgS2.png)

**Tags:** ds.algorithms, reference-request, graph-theory, graph-algorithms, planar-graphs

> **Comments:**
> **username_1**: Cross-posted: https://cs.stackexchange.com/q/145830/755  
> **username_2**: 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: https://drops.dagstuhl.de/opus/volltexte/2019/10402/  
> **username_0**: 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  

---

## 1 answers

### Answer by username_3 on 2022-01-06. Score: 1

From [Dumitrescu et al.](https://arxiv.org/abs/1807.04599):

> In 2005, [Markov and Shi showed](https://arxiv.org/abs/quant-ph/0511069) that optimal contraction sequences correspond to optimal (minimum width) tree decompositions of a tensor network's line graph.

From [Bryan O'Gorman's paper](https://arxiv.org/abs/1906.00013), 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")](https://link.springer.com/article/10.1007%2FBF01215352). 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.

> **Comments:**
> **username_0**: 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)  
> **username_3**: @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  
> **username_2**: O’Gorman’s paper uses tree *embeddings*, not tree decompositions. You may find the language in this paper more accessible. https://arxiv.org/abs/2002.01935  
> **username_0**: They use tree embeddings to define treewidth which I don't think works, you need tree decomposition for that.  
> **username_0**: @username_2 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 https://arxiv.org/abs/1908.11034  
> **username_0**: @Jordan Johnny Gray pointed out this paper which describes polynomial-time algorithm for optimal contraction of a tree structured tensor networks, however both of us had trouble reading it, their wording is confusing -- [Towards a polynomial algorithm for optimal contraction sequence of tensor networks from trees](https://dr.ntu.edu.sg/bitstream/10356/141943/2/Towards%20a%20polynomial%20algorithm%20for%20optimal%20contraction%20sequence%20of%20tensor%20networks%20from%20trees.pdf)  
> **username_2**: O’Gorman uses tree embeddings to define and bound vertex and edge congestions, *not* the treewidth. The relevant treewidth for TN contraction is that of the line graph of the network anyway, not the treewidth of the network itself.  
> **username_0**: @username_2 Equation 1 on page 7 of O'Gorman [paper](https://arxiv.org/pdf/1906.00013.pdf) defines treewidth using tree embedding  
> **username_2**: I don’t see that equation defining treewidth using a tree embedding. I see it defining treewidth using a tree *decomposition*.  
> **username_0**: That same section says ""A [tree decomposition|...] of a vertex weighted graph G is a tuple (T,b) of a binary tree ..."" So it defines tree decomposition in terms of tree embedding, which I don't think works. I posted diagram of tree/carving/branch decompositions of 3x2 grid graph in the question. You can see that carving/branch decompositions can be defined in terms of tree embedding, but not tree decomposition  

---

