Lower Bounds on Pure Dynamic Programming for Connectivity Problems on Graphs of Bounded Path-Width

In the Maximum Weight Independent Set problem one is given a graph $G=(V,E)$ along with a vertex weight $x_v$ for every $v\in V$, and is asked for the value $I{S}_G:={\max }_{I\in ℐ(G)}{\sum }_{v\in I}{x}_v$ where $ℐ(G)$ denotes the family of all independent sets of $G$. Our lower bound for this problem reads as follows (full definitions are postponed to Section 2):

Note that pathwidth is a width measure that is always at least the treewidth of the graph. Since there is a simple $𝒪(2^{k}N)$-sized tropical circuit that calculates $I{S}_G$ for an $N$-vertex graph of pathwidth $k$, this result is optimal in a tight sense.¹¹1This can be shown by translating the standard $𝒪(2^{k}N)$ time algorithm for $I{S}_G$ (see e.g. [10, Section 7.3.1]) in the natural way into a tropical circuit. A previous result by Korhonen [27] showed that for every graph $G$ of treewidth $k$ and maximum degree $d$ any tropical circuit calculating $I{S}_G$ must be of size at least $2^{\mathrm{\Omega }(k/d)}$. This result is less tight than our new result and also seems to crucially rely on some properties of the Maximum Weight Independent Set problem. While the type of universal lower bound from [27] is quite interesting, it does not directly have added value in our context of worst case complexity analysis and hence we do not pursue it further in this work.

Theorem 1.1 is obtained using the following two ingredients. The graphs for which we show the bounds are constructed based on ideas from the classic reduction from CNF-Sat to Maximum Weight Independent Set. The tropical circuit size bound itself is shown by analyzing the structure of the so-called rectangles, a combinatorial notion that typically arises in the study of tropical circuits that captures the way in which the partial solution calculated at some node of the tropical circuit can combine with the computations done by the rest of the circuit, see e.g. [22].

We show lower bounds on the tropical circuit complexity of the following graph connectivity problems. Let $G$ be an $N$-vertex graph with an edge weight $x_{u,v}\in \mathbb{N}$ for every pair of distinct vertices $u$ and $v$. Let $\mathscr{H}(G)$ denote the family of all sequences of $N+1$ vertices ${(u_i)}_{i=0}^N$ such that $u_0=u_N$ and $u_0\to u_1\to \mathrm{\dots }\to u_{N-1}\to u_N$ is a directed Hamiltonian cycle in $G$. We define $DTS{P}_G$ to be the minimum ${\sum }_{i\in [N]}{x}_{u_{i-1},u_i}$ taken over all $(u_0,\mathrm{\dots },u_N)\in \mathscr{H}(G)$. For an undirected graph, we define the undirected variant $TS{P}_G$ similarly while identifying variables $x_{u,v}$ and $x_{v,u}$ for all $uv\in E(G)$.

With these definitions in place, our main results can be stated as follows:

We also provide a similar lower bound for the Directed Spanning Tree problem. We let $𝒯(G)$ denote the family of all functions $p:V(G)\to V(G)$ such that for exactly one vertex $v\in V(G)$, $p(v)=v$, and edges $(p(u),u)$ over all other vertices $u$ form an out-tree rooted at $v$ (i.e. a tree oriented away from the root). Furthermore, we define $DS{T}_G$ as the minimum ${\sum }_{v\in V(G):p(v)\ne v}{x}_{p(v),v}$ taken over all $p\in 𝒯(G)$ (i.e., $DS{T}_G$ is the minimum weight spanning tree of $G$).

By adapting textbook dynamic programming algorithms, one can directly obtain tropical circuits for $DTS{P}_G,TS{P}_G$ and $DS{T}_G$ of size $k^{𝒪(k)}N$ if $G$ has $N$ vertices and pathwidth/treewidth $k$. Thus, there is still a gap between the lower bound and upper bound, and in fact this seems closely related to a similar gap in the area of communication complexity (see Section 7 for more details on this). Nevertheless, our results show that the currently fastest $2^{𝒪(k)}N$ time algorithms for TSP and Directed Steiner Tree (which generalizes Directed Spanning Tree) cannot be matched with merely pure dynamic programming.

The proofs of these three results combine the basic ingredients of the proof of Theorem 1.1 with the properties of the Matchings Compatibility Matrix, defined as follows. The rows and columns of this binary matrix are both indexed by perfect matchings of a bipartite graph, and an entry in the matrix indicates whether the union of these two perfect matchings forms a Hamiltonian cycle. This matrix has already been studied in [36] in the context of the log-rank conjecture in communication complexity, where a lower bound on the nondeterministic communication complexity and an upper bound of its rank was given. The rank of (a slight variant of) this matrix also turned out to be important for studying the complexity of the Hamiltonian Cycle and TSP problem, both parameterized by the path/treewidth of the input graph and parameterized by the number of vertices [9, 11, 35].

Our main technical contribution is that the lower bound on the nondeterministic communication complexity of this matrix from [36] can be used to obtain the above lower bounds on the size of tropical circuits.

A notion closely related to minimum tropical circuit size of a polynomial is that of the extension complexity of a polytope.²²2To compare the two notions, we focus on multilinear polynomials, i.e. polynomials of maximum individual degree $1$. With such a polynomial we can associate a polytope which is the convex hull of all points $(a_1,\mathrm{\dots },a_n)\in {\{0,1\}}^n$ with the property that $x^{a_1}\mathrm{\dots }{x}^{a_n}$ is a monomial in the polynomial. The extension complexity $\text{xc}(P)$ of a polytope $P$ is the minimum number of facets of a (possibly, higher-dimensional) polytope that can be projected to $P$. The notion has been introduced by Yannakakis [40] and culminated in celebrated exponential lower bounds of the polytope associated with $TS{P}_G$ [14] and the non-bipartite matching polytope [37]. These two (Gödel-prize winning) papers also achieve their lower bound by lower bounding the nondeterministic communication complexity of a certain matrix, but we use a completely different matrix.

While it is known that dynamic programming algorithms can usually be turned into extension complexity upper bounds [8, 33], of course many problems amenable to linear programming cannot be solved directly with dynamic programming. Analogously, the spanning tree polynomial (denoted with $DS{T}_G$ in this paper) cannot be computed with tropical circuits of size $2^{o(\sqrt{n})}$ (see [23]), but has polynomial extension complexity (see e.g. [32]). In the other direction, it is known that the existence of small monotone neural networks implies small extension complexity (see [20]). In particular, since tropical circuits are a special case of such networks, for any multilinear polynomial $f$ and its corresponding polytope $P$, every tropical circuit calculating $f$ must have size at least $\frac{1}{2}\text{xc}(P)$.

The extension complexity of polytopes in terms of treewidth of the input graph was already upper bounded in previous works [26, 13]. In [13] the authors presented lower bounds, but those are conditioned on the Exponential Time Hypothesis. The currently (to our best knowledge) highest relevant unconditional lower bounds are a $2^{\mathrm{\Omega }(n/\log n)}$ lower bound on the extension complexity of the independent set polytope (corresponding to $I{S}_G$) from [18], and a $2^{\mathrm{\Omega }(n)}$ lower bound on the extension complexity of the TSP polytope (corresponding to $TS{P}_G$) from [37].

These lower bounds are incomparable to our lower bounds in Theorem 1.1 and Theorem 1.2. We hope that our techniques can be used to prove stronger lower bounds on the extension complexity of polytopes (as a function of the treewidth of the input graph, or in general).

This paper is organized as follows: In Section 2 we provide the necessary definitions and preliminary tools used in the remainder of the paper. Section 3 presents the proof of Theorem 1.1. Section 4 presents the aforementioned matchings compatibility matrix and the required results about its structure. In Section 5 we prove Theorem 1.2 and Theorem 1.3. In Section 6 we prove Theorem 1.4, and we provide some concluding remarks in Section 7.

If we treat the weights $x_v$ as indeterminates we can view $I{S}_G$ as a polynomial in the $(\max ,+)$ semiring by replacing the max operation by addition and the $+$ operation by multiplication:

where we remind the reader that $ℐ(G)$ denotes the family of all independent sets of $G$.

Similarly to the Independent Set polynomial $I{S}_G$, we define the directed TSP polynomial of $G$ as

where we remind the reader that $\mathscr{H}(G)$ denotes the family of all sequences of $N+1$ vertices ${(u_i)}_{i=0}^N$ such that $u_0=u_N$ and $u_0\to u_1\to \mathrm{\dots }\to u_{N-1}\to u_N$ is a directed Hamiltonian cycle in $G$. Naturally, we also view $TS{P}_G$ similarly as a polynomial by identifying variables $x_{u,v}$ and $x_{v,u}$ for all $uv\in E(G)$.

We also define a directed spanning tree polynomial of $G$ as

where we remind the reader that $𝒯(G)$ denotes the family of all functions $p:V(G)\to V(G)$ such that for exactly one vertex $v\in V(G)$, $p(v)=v$, and edges $(p(u),u)$ over all other vertices $u$ form an out-tree rooted at $v$.

The support of a monomial $m=x_{i_1}^{a_1}\mathrm{\dots }{x}_{i_{\mathrm{\ell }}}^{a_{\mathrm{\ell }}}$ is the set of variables $\{x_{i_1},\mathrm{\dots },x_{i_{\mathrm{\ell }}}\}$ and is denoted as $sup(m)$. The support of a polynomial $p=m_1+\mathrm{\cdots }+m_{\mathrm{\ell }}$ is the union of supports $sup(m_i)$ over all $i\in [\mathrm{\ell }]$. We let $sup(p)$ denote the support of polynomial $p$. For a monomial $m$ and a polynomial $p$, we write $m\in p$ if $p$ treated as a formal expression is of the form $m+q$ for some polynomial $q$. We say that a polynomial $p$ is homogeneous if and only if for some $d\in \mathbb{N}$, the degree of all monomials $m\in p$ is $d$. For a polynomial $p$, we write $|p|$ to denote the number of monomials $m$ such that $m\in p$.

A valuation is a function which maps variables to $ℝ$. A characteristic valuation ${\chi }_m$ of a monomial $m$ is a valuation such that ${\chi }_m(x)=1$ if $x\in sup(m)$ and ${\chi }_m(x)=-1$ otherwise. As stated before, we evaluate polynomials in a $(\max ,+)$ semiring, i.e., given a valuation $v$, the monomial $x$ evaluates to $v(x)$, $(f+g)(v)$ evaluates to $\max (f(v),g(v))$ and $(f\cdot g)(v)$ evaluates to $f(v)+g(v)$.

For two polynomials $p,q$, we write $p\subseteq q$ if for every monomial $m\in p$, we have $m\in q$. We write $p\simeq q$ iff $p\subseteq q$ and $q\subseteq p$. In particular, $p\simeq q$ does not imply that $p=q$ (take, e.g. $p=x$ and $q=x+x$). The definition of $\simeq$ is motivated by the following observation.

The implication from $f\simeq g$ to $f(v)=g(v)$ is immediate. In the other direction, assume w.l.o.g. that $f\subseteq g$ does not hold, and hence there is some monomial $m\in f$ such that $m\notin g$. It is easy to see that $f({\chi }_m)=|sup(m)|$ and , which is a contradiction. $◀$

W.l.o.g. we assume that $I_1,I_2\in 𝒜$. If both sets have different intersection with some $V_i$, then the claim trivially follows, hence w.l.o.g. we assume that for some $l\in [q]$, we have $w_l\in I_1$ and $w_l\notin I_2$.

Since $I_2$ is useful, we have $J_2\in ℬ$ such that $I_2\cup J_2$ is a canonical solution. Since $I_1$ and $J_2$ are disjoint, we have $w_l\notin I_2\cup J_2$, hence $v_{i,j}\in I_2\cup J_2$ for some neighbor $v_{i,j}$ of $w_l$. As $I_1$ and $J_2$ are non-adjacent, we have $v_{i,j}\notin J_2$, hence $v_{i,j}\in I_2$. As $I_1$ is an independent set of $G_k$, we have $v_{i,j}\notin I_1$, which finishes the proof of the claim. $\mathrm{⊲}$

Assume w.l.o.g. that $I_1,I_2\in 𝒜$. By the previous claim, we have some $i\in [k],j\in \{0,\mathrm{\dots },2q-1\}$ such that w.l.o.g. $v_{i,j}\in I_1$ and $v_{i,j}\notin I_2$. Put $r=j\mathrm{𝗆𝗈𝖽}2$. Since $I_1,I_2$ are useful, we have the corresponding $J_1,J_2\in ℬ$. By contradiction, let $j^{\prime }\in \{0,\mathrm{\dots },2q-1\}$ be an index minimizing $|j-j^{\prime }|$ for which $v_{i,j^{\prime }}$ does not belong to the expected set, i.e., such that either $j^{\prime }\mathrm{𝗆𝗈𝖽}2=r$ and $v_{i,j^{\prime }}\notin I_1$ or $j^{\prime }\mathrm{𝗆𝗈𝖽}2\ne r$ and $v_{i,j^{\prime }}\notin I_2$.

Consider the case $j^{\prime }\mathrm{𝗆𝗈𝖽}2=r$, the other one will be symmetric. As $v_{i,j}\in I_1\cup J_1$, we also have $v_{i,j^{\prime }}\in I_1\cup J_1$. By minimality, we have that either $v_{i,j^{\prime }+1}$ or $v_{i,j^{\prime }-1}$ is in $I_2$. If $v_{i,j^{\prime }}\notin I_1$ then $v_{i,j^{\prime }}\in J_1$, but this would imply that $I_2\cup J_1$ is not an independent set, which is a contradiction. $\mathrm{⊲}$

Assume by contradiction that we have useful $J_2\in ℬ$ different to $J_1$. Applying the previous claim to both sides, we obtain $i_A,i_B\in [k]$ and $r_A,r_B\in \{0,1\}$ such that: $V_{i_A,r_A}\subseteq I_1,V_{i_A,1-r_A}\subseteq I_2,V_{i_B,r_B}\subseteq J_1$ and $V_{i_B,1-r_B}\subseteq J_2$. Naturally, we have $i_A\ne i_B$.

Pick $w=w_{i_A,i_B,1-r_A,1-r_B}$. That is, for some $j\in \{0,\mathrm{\dots },q-1\}$, the neighbors of $w$ are exactly $v_A=v_{i_A,2j+1-r_A}$ and $v_B=v_{i_B,2j+1-r_B}$. We have $v_A\in I_2$ and $v_B\in J_2$. Since $V_{i_A,r_A}\subseteq I_1$ and $I_1$ is independent in $G_k$, we have $v_A\notin I_1$. Similarly, $v_B\notin J_1$. Since $I_2$ and $J_1$ are disjoint, we have $v_A\notin J_1$, and similarly $v_B\notin I_1$. Since $I_2$ and $J_1$ are not adjacent, we have $w\notin J_1$, and similarly $w\notin I_1$. However, this means that $I_1\cup J_1$ is not a canonical solution since neither $w$ nor its two neighbors belong to $I_1\cup J_1$. This is a contradiction, hence the claim is proven. $\mathrm{⊲}$ Lemma 3.2 follows immediately from the last claim.

Let $u,v$ be the predecessors of $w$. First, consider the case where $w$ is a max gate, that is, $B_w=B_u+B_v$. Then, either $b\in B_u$ or $b\in B_v$. W.l.o.g. assume the former. We have $a\cdot B_u\subseteq a\cdot B_w\subseteq I{S}_G$, hence $a\in A_u$. Therefore, $b\in B_u^{\ast }$, $a\in A_u^{\ast }$, and hence $c\in A_u^{\ast }\cdot B_u^{\ast }$ as desired.

Second, consider the case where $w$ is a plus gate, that is, $B_w=B_u\cdot B_v$. Then, we have $b=b_v\cdot b_u$ for some $b_v\in B_v$ and $b_u\in B_u$. We have $a\cdot b_v\cdot B_u\subseteq a\cdot B_v\cdot B_u\subseteq I{S}_G$, hence $a\cdot b_v\in A_u$. Therefore, $b_u\in B_u^{\ast }$, $a\cdot b_v\in A_u^{\ast }$, and hence $c\in A_u^{\ast }\cdot B_u^{\ast }$. By a symmetric argument, $c\in A_v^{\ast }\cdot B_v^{\ast }$. $\mathrm{⊲}$

Now, consider the following process. We fix a canonical solution $c\in I{S}_G^{\ast }$ and start at output node $w_1$. If we are currently in a max node $w_i$, we move towards the predecessor $w_{i+1}$ given by the claim. If we are currently in a plus node, we move towards the predecessor $w_{i+1}$ for which $|B_{w_{i+1}}^{\ast }|$ is larger. Such process terminates at an input node and produces a path $w_{\mathrm{\ell }},\mathrm{\dots },w_1$. As argued before, for some $i\in [\mathrm{\ell }-1]$, we have $|A_{w_i}^{\ast }\cdot B_{w_{i+1}}^{\ast }|\le 1$.

We have $c\in A_{w_{i+1}}^{\ast }\cdot B_{w_{i+1}}^{\ast }$. If $w_i$ is a max node, we have $B_{w_{i+1}}\subseteq B_{w_i}$, hence $A_{w_{i+1}}^{\ast }\subseteq A_{w_i}^{\ast }$, hence $c\in A_{w_i}^{\ast }\cdot B_{w_{i+1}}^{\ast }$, and hence $A_{w_i}^{\ast }\cdot B_{w_{i+1}}^{\ast }=\{c\}$.

If $w_i$ is a plus node, then we additionally have $c\in A_v^{\ast }\cdot B_v^{\ast }$ where $v$ is the predecessor of $w_i$ other than $w_{i+1}$. Given the way we chose $w_{i+1}$, we have $|B_v^{\ast }|\le |B_{w_{i+1}}^{\ast }|\le 1$. Since $B_{w_i}^{\ast }\subseteq B_{w_{i+1}}^{\ast }\cdot B_v^{\ast }$, we have $|B_{w_i}^{\ast }|\le 1$. Thus, $A_{w_i}^{\ast }\cdot B_{w_i}^{\ast }=\{c\}$.

Repeating this process for each canonical $c$ creates a mapping from $I{S}_G^{\ast }$ to the set $V(\mathrm{\Gamma })\cup E(\mathrm{\Gamma })$. If we map $c$ to a vertex $w$, then we have a guarantee that $A_w^{\ast }\cdot B_w^{\ast }=\{c\}$. If we map $c$ to an edge $(u,w)$, we have a guarantee that $A_w^{\ast }\cdot B_u^{\ast }=\{c\}$. This implies that the mapping is injective, and hence $2^k=|I{S}_G^{\ast }|\le |V(\mathrm{\Gamma })|+|E(\mathrm{\Gamma })|\le 3|V(\mathrm{\Gamma })|$. This finishes the proof of Lemma 3.1, which consequently proves Theorem 1.1

Let $Q\subseteq {𝒮}_k\times {𝒮}_k$ denote the set of pairs $({\rho }_1,{\rho }_2)$ such that ${\rho }_2{\rho }_1\in {\overline{𝒮}}_k$, i.e., the set of 1-entries of ${ℳ}_k$. Let $P_1$ and $P_2$ denote the sets of permutations which are indices of, respectively, rows and columns of $R$. Thus, for every ${\rho }_1\in P_1,{\rho }_2\in P_2$, we have $({\rho }_1,{\rho }_2)\in Q$. Consider a map ${\mu }_{\alpha ,\beta }:{𝒮}_k\times {𝒮}_k\to {𝒮}_k\times {𝒮}_k$ parameterized by permutations $\alpha ,\beta \in {𝒮}_k$, defined as

First, note that ${\rho }_2{\rho }_1\in {\overline{𝒮}}_k$ if and only if $({\beta }^{-1}{\rho }_2{\alpha }^{-1})(\alpha {\rho }_1\beta )={\beta }^{-1}{\rho }_2{\rho }_1\beta \in {\overline{𝒮}}_k$, as permutation conjugation preserves cycle type, hence $({\rho }_1,{\rho }_2)\in Q$ if and only if ${\mu }_{\alpha ,\beta }({\rho }_1,{\rho }_2)\in Q$.

Let $\alpha ,\beta$ be two random permutations sampled independently from a uniform distribution on ${𝒮}_k$. First, we show that for any two pairs $({\rho }_1,{\rho }_2),({\sigma }_1,{\sigma }_2)\in Q$, we have

To do this, we show that there are $k$ different pairs $\alpha ,\beta$ for which $\alpha {\rho }_1\beta ={\sigma }_1$ and ${\beta }^{-1}{\rho }_2{\alpha }^{-1}={\sigma }_2$. By Section 2, we have exactly $k$ permutations $\beta$ which satisfy ${\sigma }_2{\sigma }_1={\beta }^{-1}{\rho }_2{\rho }_1\beta$. For each of those, we must put $\alpha ={\sigma }_2^{-1}{\beta }^{-1}{\rho }_2$ to obtain a pair satisfying the conditions.

For any pair $({\rho }_1,{\rho }_2)\in Q$, we have $({\rho }_1,{\rho }_2)\in {\mu }_{\alpha ,\beta }(R)$ if and only if ${\mu }_{{\alpha }^{-1},{\beta }^{-1}}({\rho }_1,{\rho }_2)\in R$, and therefore

Now, sample $\mathrm{\ell }$ pairs ${\alpha }_i,{\beta }_i$ independently uniformly from ${𝒮}_k\times {𝒮}_k$ and let $R_i={\mu }_{{\alpha }_i,{\beta }_i}(R)$. Clearly $R_i\subseteq Q$ for each $i\in [\mathrm{\ell }]$. Let $\overline{R}={\bigcup }_{i\in [\mathrm{\ell }]}{R}_i$. For any $({\rho }_1,{\rho }_2)\in Q$, we have

By union bound, we have , hence there exist a choice of ${\alpha }_i,{\beta }_i$ for which $\overline{R}=Q$. For this choice of ${\alpha }_i,{\beta }_i$ we have that $R_1,\mathrm{\dots },R_{\mathrm{\ell }}$ is a rectangle cover, which finishes the proof. $\mathrm{⊲}$

Immediately, we get the following lemma as a corollary.

There is a natural correspondence between permutations in ${𝒮}_k$ and perfect matchings of a complete bipartite graph $K_{k,k}$. Let us label the vertices of both sides of a bipartition of $K_{k,k}$ as respectively $v_1,\mathrm{\dots },v_k$ and $u_1\mathrm{\dots },u_k$. For any perfect matching $M\subseteq \{v_1,\mathrm{\dots },v_k\}\times \{u_1,\mathrm{\dots },u_k\}$, its corresponding permutation is $\rho \in {𝒮}_k$ defined as

It is easy to see that for any two perfect matchings $M_1,M_2$ in $K_{k,k}$, their union $M_1\cup M_2$ forms a Hamiltonian cycle iff ${\rho }_2^{-1}{\rho }_1\in {\overline{𝒮}}_k$ iff ${\rho }_1^{-1}{\rho }_2\in {\overline{𝒮}}_k$, where ${\rho }_i$ denotes a permutation corresponding to $M_i$.