Monotone Bounded-Depth Complexity of Homomorphism Polynomials

In many applications, the pattern is smaller in comparison to the target graph. Curticapean and Marx [16] modeled this setting by classifying the complexity of counting subgraphs from fixed pattern classes: Given any fixed class of graphs $\mathscr{H}$, they defined a problem $\mathrm{\#}\mathrm{𝖲𝗎𝖻}(\mathscr{H})$ that asks, given a graph $H\in \mathscr{H}$ and a general graph $G$, to count the $H$-subgraphs in $G$. The parameter is $|V(H)|$. This problem is known to be polynomial-time solvable when the graphs in $\mathscr{H}$ do not contain arbitrarily large matchings – if they do contain arbitrarily large matchings, then $\mathrm{\#}\mathrm{𝖲𝗎𝖻}(\mathscr{H})$ with parameter $|V(H)|$ is complete for the parameterized complexity class $\mathrm{\#}𝖶[\mathrm{𝟣}]$, i.e., the analogue of $\mathrm{\#}𝖯$ in parameterized complexity.

An analogously defined problem $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(\mathscr{H})$ of counting homomorphisms with patterns drawn from $\mathscr{H}$ was also classified by Dalmau and Jonsson [17]. Here, the tractability criterion is a constant bound on the treewidth of graphs in $\mathscr{H}$, a measure of the “tree-likeness” of $H$: The problem $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(\mathscr{H})$ is polynomial-time solvable when all graphs in $\mathscr{H}$ admit a constant upper bound on their treewidth, and the problem is $\mathrm{\#}𝖶[\mathrm{𝟣}]$-hard otherwise with respect to the parameter $|V(H)|$. Here, a homomorphism from $H$ to $G$ is a function $h:V(H)\to V(G)$ such that $uv\in E(H)$ implies $h(u)h(v)\in E(G)$. Homomorphism counts from small patterns find direct applications in database theory, where they capture answer counts to so-called conjunctive queries [12]. It was also shown that $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(\mathscr{H})$ captures the complexity of other pattern counting problems, including that of counting subgraphs [14]: In a nutshell, (i) many pattern counting problems can be expressed as unique linear combinations of homomorphism counts from graphs $H$, and (ii) in many models of computation, such linear combinations turn out to be precisely as hard as their hardest terms. This motivates understanding the complexity of these individual terms, i.e., of homomorphism counts.

Following the classification of $\mathrm{\#}\mathrm{𝖲𝗎𝖻}(\mathscr{H})$ and $\mathrm{\#}\mathrm{𝖧𝗈𝗆}(\mathscr{H})$, almost-tight quantitative bounds were obtained under the exponential-time hypothesis [23, 29]: For any graph $H$, there is an $O(n^{\mathrm{tw}(H)+1})$ time algorithm for counting homomorphisms from $H$ into $n$-vertex target graphs, and assuming the exponential-time hypothesis, Marx ruled out $n^{o(\mathrm{tw}(H)/\log \mathrm{tw}(H))}$ time algorithms [33], recently revisited in [25, 15]. Through connections between homomorphism counts and other pattern counts [14], these bounds translate directly to other counting problems. For example, there is an $O(n^{\mathrm{vc}(H)})$ time algorithm for counting $H$-subgraphs in an $n$-vertex graph $G$, where $\mathrm{vc}(H)$ is the vertex-cover number of $H$. As a consequence of the lower bound on counting homomorphisms, the exponential-time hypothesis rules out $n^{o(\mathrm{vc}(H)/\log \mathrm{vc}(H))}$ time algorithms [14] for counting $H$-subgraphs.

Thus, some slack remains between the known upper and conditional lower bounds on the exponents of pattern counting problems, and it would be desirable to settle the $\log$-factor in the exponent of the running time. Moreover, one might also dare to ask for the precise exponent for concrete finite graphs $H$, such as $K_3$ (which amounts to triangle counting) or $K_4$ or $C_6$. Finally, let us stress that the lower bounds on the exponent are conditioned on the exponential-time hypothesis, an assumption that is a priori stronger than $𝖯\ne \mathrm{𝖭𝖯}$.

Valiant’s seminal papers [41, 43] studied the problem of counting perfect matchings from the perspective of both counting and algebraic complexity. Following the work of Komarath, Pandey, and Rahul [27], we consider an algebraic version of pattern counting problems.

For undirected graphs $H$ and $n\in \mathbb{N}$, we consider the homomorphism polynomial ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ on variables $x_{i,j}$ for $i,j\in [n]$ and its set-multilinear version, the colorful subgraph polynomial ${\mathrm{𝖢𝗈𝗅𝖲𝗎𝖻}}_{H,n}$ on variables $x_{i,j}^{(e)}$ for $i,j\in [n]$ and $e\in E(H)$. The latter can often be handled more easily in proofs, while complexity results can be transferred between these two polynomials.

The polynomial ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ can be viewed as the weighted homomorphism count from $H$ into a complete $n$-vertex graph with generic indeterminates as edge-weights. Similarly, ${\mathrm{𝖢𝗈𝗅𝖲𝗎𝖻}}_{H,n}$ can be viewed as counting the color-preserving homomorphisms from a colorful graph $H$ into a complete graph with indeterminate edge-weights and $n$ vertices per color class. Formally, these multivariate polynomials are defined as

The complexity of multivariate polynomials is commonly studied via algebraic circuits, first formalized by Valiant [41]. The efficiency of a circuit is usually quantified by its size (number of edges and gates) and its depth (number of layers). The size captures the total number of operations the circuit performs, and the depth roughly corresponds to parallelism. For convenience, we will instead consider the product-depth, which is the number of “multiplication layers” in the circuit. Refer to Section 2 for formal definitions. These efficiency measures define natural algebraic circuit complexity classes, for instance, $\mathrm{𝖵𝖯}$ – polynomials of polynomially bounded degree computable by circuits of size $\mathrm{poly}(n)$, and $\mathrm{𝖵𝖭𝖯}$ – polynomials which can be expressed as a hypercube sum of $\mathrm{𝖵𝖯}$ circuits.

Valiant established that the permanent polynomial is complete for the class $\mathrm{𝖵𝖭𝖯}$, while its sibling, the determinant polynomial, is complete for a seemingly smaller class, $\mathrm{𝖵𝖡𝖯}$ – the class of polynomially bounded algebraic branching programs (see Definition 6). In a recent line of work [11, 18, 31], homomorphism polynomials have been used to obtain natural polynomials which are complete for several well-studied algebraic circuit classes.

Monotone circuits over a field like $\mathbb{Z}$ are circuits that do not use negative constants, and hence computations performed by them cannot feature cancellations (Definition 7). Several important techniques for proving upper bounds on the complexity of polynomials (e.g., dynamic programming) directly yield monotone circuits. Compared to general computational models, lower bounds for monotone computation are much better understood, and many exponential lower bounds [36, 43, 24, 34, 19, 9] and strong algebraic complexity class separations [38, 22, 46, 39] are known. As a striking example, monotone variants of the algebraic complexity classes $\mathrm{𝖵𝖯}$ and $\mathrm{𝖵𝖭𝖯}$ are proven to be different [39, 46]. In contrast, Hrubeš [21] showed that strong-enough monotone lower bounds of a special kind (called $ϵ$-sensitive) imply unconditional lower bounds for general arithmetic circuits!

In a fascinating recent work, Komarath, Pandey and Rahul [27] studied the monotone arithmetic circuit complexity of the polynomials ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ and discovered that this complexity is completely determined by the treewidth of the pattern graph $H$. More precisely, they show that the smallest monotone circuit computing ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ is of size $\mathrm{\Theta }(n^{\mathrm{tw}(H)+1})$. Similarly, they show that algebraic branching programs for ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ are of size $\mathrm{\Theta }(n^{\mathrm{pw}(H)+1})$, where $\mathrm{pw}(H)$ is the pathwidth of $H$, a linear version of treewidth. Moreover, they also consider the monotone formula complexity of ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ and show that it is $\mathrm{\Theta }(n^{\mathrm{td}(H)+1})$, where $\mathrm{td}(H)$ is the treedepth of $H$, the minimum height of a tree on vertex set $V(H)$ that contains all edges of $H$ in its tree-order. These results together show that, when considering homomorphism polynomials for fixed patterns $H$, the power of monotone computation is precisely characterized by graph-theoretic quantities of $H$: For natural and well-studied monotone computational models, the precise exponent $c_H$ in the complexity $\mathrm{\Theta }(n^{c_H})$ is the value of a natural and well-studied graph parameter of $H$.

In this paper, we investigate whether the correspondence between monotone circuit complexity and graph parameters can also be established for another restriction of monotone circuits, namely bounded-depth monotone circuits: Are there natural graph parameters that dictate the bounded-depth monotone complexity of ${\mathrm{𝖧𝗈𝗆}}_{H,n}$?

Bounded-depth circuits are of central importance in algebraic complexity due to the phenomenon of depth reduction. In a sequence of works [44, 2, 26, 40], it was shown that any algebraic circuit of size $s$ computing a polynomial of degree $d$ can also be simulated by a product-depth $\mathrm{\Delta }$ circuit of size $s^{O(d^{1/\mathrm{\Delta }})}$. If the circuit was monotone to begin with, the resulting bounded-depth circuit is also monotone. Depth reduction also implies that strong enough lower bounds for bounded-depth circuits will lead to general circuit lower bounds – an exceptionally hard open question. A lot of work has gone into proving strong bounded-depth circuit lower bounds (see [35] for a survey). Recently, following the breakthrough result of Limaye, Srinivasan, and Tavenas [28], superpolynomial lower bounds have been shown for bounded-depth circuits (also see [7, 4]).

Studying the monotone bounded-depth complexity of ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ naturally leads us to define bounded-depth versions of treewidth, the $\mathrm{\Delta }$-treewidth ${\mathrm{tw}}_{\mathrm{\Delta }}(H)$ for any fixed $\mathrm{\Delta }\in \mathbb{N}$. These graph parameters ask to minimize the maximum bag size over all tree-decompositions of $H$, however, with the twist that only tree-decompositions with an underlying tree of height at most $\mathrm{\Delta }$ are admissible. Their values interpolate between $|V(H)|-1$ (when only height $1$ is allowed) and $\mathrm{tw}(H)$ (when no height restrictions are imposed), and they are connected to the vertex-cover number in the special case $\mathrm{\Delta }=2$ (see Section 3). Bounded-depth variants of treewidth implicitly appear in balancing techniques for tree-decompositions [10, 8], and the $\mathrm{\Delta }$-treewidth of paths also appears implicitly in divide-and-conquer schemes for iterated matrix multiplication in a bounded-depth setting [28]. A recent work of Adler and Fluck [1] studied a notion that bounds the width and depth simultaneously, which they call bounded depth treewidth. Our notion of ${\mathrm{tw}}_{\mathrm{\Delta }}(H)$ only bounds the height of the tree decomposition to $\mathrm{\Delta }$. In particular, for a fixed $\mathrm{\Delta }$, there is always a tree decomposition of height $\mathrm{\Delta }$ for any graph $H$, but with a possibly large treewidth.

We show that the $\mathrm{\Delta }$-treewidth of graphs completely characterizes the complexity of ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ for monotone circuits of product-depth at most $\mathrm{\Delta }$. For technical reasons described later, it is, however, not the $\mathrm{\Delta }$-treewidth of $H$ itself that governs the complexity, but rather the $\mathrm{\Delta }$-treewidth of the graph $H^{†}$ obtained by removing all vertices of degree at most $1$. We call this the pruned $\mathrm{\Delta }$-treewidth ${\mathrm{ptw}}_{\mathrm{\Delta }}$ of a graph $H$. Our main result is as follows:

Note that any fixed pattern graph $H$ on $k$ vertices gives a homomorphism polynomial on $n^k$ monomials, which has a trivial $\mathrm{poly}(n)$ sized monotone circuit of depth two. We stress that we wish to determine the precise exponent in this polynomial size: In general, $k$ could be much larger than the pruned $\mathrm{\Delta }$-treewidth of $H$.

We also study the related computational model of algebraic branching programs (ABPs). An ABP is a directed acyclic graph with a source vertex $s$ and a sink $t$, with edges between vertices labeled by variables or constants. The size of the ABP is the total number of vertices in the graph, and the length of the longest path from $s$ to $t$ is its length. We refer the reader to Section 2 for a formal definition of an ABP and its computation.

For a graph $H$, we define a new graph parameter called $\mathrm{\Delta }$-pathwidth ${\mathrm{pw}}_{\mathrm{\Delta }}(H)$, which asks to minimize the bag size over all path decompositions of $H$ where the underlying path is of length $\mathrm{\Delta }$. We defer the formal definition of these graph parameters to Section 3. Similar to the case of circuits, we show that the $\mathrm{\Delta }$-pathwidth of the pruned graph $H^{†}$ (obtained by removing degree $1$ vertices from $H$), which we call the pruned $\mathrm{\Delta }$-pathwidth ${\mathrm{ppw}}_{\mathrm{\Delta }}$ of $H$ characterizes the monotone ABP of length $\mathrm{\Delta }$ computing ${\mathrm{𝖧𝗈𝗆}}_{H,n}$.

For a length-$\mathrm{\Delta }$ ABP to compute the polynomial ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ (or ${\mathrm{𝖢𝗈𝗅𝖲𝗎𝖻}}_{H,n}$), its length needs to be at least the degree of the polynomial (which is $|E(H)|$). Otherwise, we cannot even compute a single monomial. We note that the above theorem also implies a bound on the ABP width.

For a fixed pattern graph, it was shown in [27] that ${\mathrm{𝖧𝗈𝗆}}_{H,n}$ and ${\mathrm{𝖢𝗈𝗅𝖲𝗎𝖻}}_{H,n}$ have the same “monotone complexity”. We observe that the reduction holds even in the bounded-depth (bounded-length) case (Lemma 21), so we prove our results only for ${\mathrm{𝖢𝗈𝗅𝖲𝗎𝖻}}_{H,n}$. The upper bounds of Theorem 1 and Theorem 2 are shown in Section 4 and Section 5, respectively.

Finally, by turning our attention to pattern graphs of non-constant size, we can prove a depth hierarchy theorem for monotone circuits: Using the tight characterization from the above theorem and the properties of pruned $\mathrm{\Delta }$-treewidth, we are able to obtain the following.

By general depth-reduction results, any monotone circuit of size $\mathrm{poly}(n)$ computing a polynomial of degree $n$ can be flattened to a monotone circuit of product-depth $\mathrm{\Delta }$ and size $n^{O(n^{1/\mathrm{\Delta }})}$, showing that the above theorem is optimal.

We also note that a similar near-optimal statement with a lower bound of $\exp (n^{\mathrm{\Omega }(1/\mathrm{\Delta })})$ can be obtained from earlier results provided the product-depth $\mathrm{\Delta }=o(\log n/\log \log n)$ is small (see [13]). Our results improve upon this in two ways: Firstly, our $\mathrm{\Omega }(\cdot )$ appears in the first rather than second exponent, thus yielding a stronger and optimal lower bound. Secondly, our results hold for any product-depth $\mathrm{\Delta }$.