Parameterised Holant Problems

Introduced by Downey and Fellows in the early 90s [32], the field of parameterised complexity theory, also called multivariate algorithmics, investigates the complexity of computational problems not only along the size $|x|$ of an input $x$, but also along a parameter $k=\kappa (x)$ taking into account one or more (structural) properties of $x$. The notion of efficient algorithms is then relaxed from polynomial-time algorithms to fixed-parameter tractable (FPT) algorithms, which are required to run in time $f(k)\cdot {|x|}^{O(1)}$, where $f$ can be any computable function. The notion of fixed-parameter tractability formalises the existence of efficient algorithms if the parameter of the problem input is significantly smaller than the input size. For example, in the database query evaluation problem, the input is a pair $x=(\phi ,D)$ of a query $\phi$ and a database $D$. Choosing the size of the query as a parameter, i.e., setting $k=|\phi |$, an FPT algorithm for this problem can then be thought as an efficient algorithm for instances in which the size of the query is significantly smaller than the size of the database, which is true for realistic instances.

Independently introduced by McCartin [44] and by Flum and Grohe [34], the field of parameterised counting complexity theory aims to apply the tools and methods from parameterised algorithmics to computational counting problems. In the context of counting problems, the notion of tractability is naturally still given by FPT algorithms, and the notion of intractability is given by $\mathrm{\#}\mathrm{W}[1]$-hardness. In a nutshell, the class $\mathrm{\#}\mathrm{W}[1]$ can be thought as a parameterised equivalent of $\mathrm{\#}\mathrm{P}$ and its canonical complete problem is the problem of, given a positive integer $k$ and a graph $G$, counting the number of $k$-cliques in $G$, parameterised by $k$. Under standard assumptions such as the Exponential Time Hypothesis, $\mathrm{\#}\mathrm{W}[1]$-hard problems are not fixed-parameter tractable (see e.g. [17, 18, 27]).

In addition to early key results such as the classification of the parameterised homomorphism counting problem by Dalmau and Jonson [28], and the resolution of the complexity of the problem of counting $k$-matchings by Curticapean [20], the field of parameterised counting recently witnessed significant advancements with the introduction of the framework of graph motif parameters [24] which has subsequently been used to fully resolve the parameterised and fine-grained complexity of numerous network pattern counting problems [50, 29, 51, 8, 3, 46, 7, 36, 30, 22, 25, 31].

We provide a complexity “trichotomy” for $\text{p-Holant}(𝒮)$, and a complexity dichotomy for $\text{p-UnColHolant}(𝒮)$, both along the permitted signatures $𝒮$.

For the statement of our results, we first introduce signature fingerprints and types of signature sets.

We point out that $\chi (d,s)$ is equal to a weighted sum over all evaluations of the Möbius function of the lattice of partitions of the set $[d]$; the details necessary for this work are provided in the full version [1, Section 2.2] and we refer the reader to e.g. [52, Chapter 3] for further reading.

We point out that there are infinitely many signature sets of each type – we provide an easy construction in the appendix. For now, let us discuss some natural examples which also help us gain some initial understanding of the properties of the signature fingerprints.

1. (I)

   Unsurprisingly, any signature set containing only a constant function $s(x)=c\ne 0$ for all $x\in \mathbb{N}$ makes the problem easy. In that case, we have, for each $d$, that $\chi (d,s):={\sum }_{\sigma }{(-1)}^{|\sigma |-1}(|\sigma |-1)!$, since $s(|B|)/s(0)$ will always be $1$. However, as indicated previously, this alternating sum is equal to ${\sum }_{\rho }\mu (\rho ,\top )$, where $\mu$ is the Möbius function of the partition lattice, and $\top$ is the coarsest partition of the $d$-element set. This sum is well-known to be $0$ for every $d\ge 2$ (see e.g. [52, Section 3.7]), implying that $𝒮=\{s_c\}$ is indeed of type $𝕋[\mathrm{𝖫𝗂𝗇}]$. Analogously, any finite signature set $𝒮$ containing only constant functions is of type $𝕋[\mathrm{𝖫𝗂𝗇}]$ as well.

   As a slightly more interesting example, a similar argument applies to the function $s(x):=2^{ax+b}$ for any pair of rational numbers $a$ and $b$, since $s(|B|)/s(0)=2^{ax}$, implying that ${\prod }_{B\in \sigma }s(|B|)/s(0)=2^{a{\sum }_{B\in \sigma }|B|}=2^{ad}$, and thus $\chi (d,s):=2^{ad}\cdot {\sum }_{\sigma }{(-1)}^{|\sigma |-1}(|\sigma |-1)!=0$, for $d\ge 2$.

2. (II)

   For type $𝕋[\omega ]$, we consider the evaluation of $\text{p-Holant}(𝒮)$ modulo $2$ (in the full version [1, Section 4.1] we show how to lift our results on the edge-coloured holant problem to modular counting). Then we set $𝒮=\{{\mathrm{𝗁𝗐}}_{\le 1}\}$, and we recall that ${\mathrm{𝗁𝗐}}_{\le 1}(x)$ evaluates to $1$ if $x\in \{0,1\}$ and to $0$ otherwise. Then the holant problem is precisely the problem of counting edge-colourful $k$-matchings modulo $2$. Now note that we have $(|\sigma |-1)!=0$ modulo $2$ whenever $|\sigma |\ge 3$, and, for $s={\mathrm{𝗁𝗐}}_{\le 1}$, $s(|B|)=0$ whenever $|B|\ge 2$. Therefore, for any $d\ge 3$, we have that $\chi (d,s)=0$ modulo $2$.

   However, note that $\chi (2,s)=1$ modulo $2$: The set $[2]$ only has two partitions ${\perp }_2=\{\{1\},\{2\}\}$ and ${\top }_2=\{\{1,2\}\}$, and observe that ${\top }_2$ contains a block $B$ of size $2$, hence $s(|B|)$ and the contribution of ${\top }_2$ to $\chi (2,s)$ vanishes. Therefore

   $$\chi (2,s)={(-1)}^{|{\perp }_2|-1}(|{\perp }_2|-1)!\prod _{B\in {\perp }_2}\frac{s(|B|)}{s(0)}=1mod2.$$

   Thus $𝒮=\{{\mathrm{𝗁𝗐}}_{\le 1}\}$ is indeed of type $𝕋[\omega ]$ when computation is done modulo $2$.

3. (III)

   A natural example for type $𝕋[\mathrm{\infty }]$ is the signature $\mathrm{𝖾𝗏𝖾𝗇}(x)$ which maps $x$ to $1$ if $x$ is even, and to $0$ otherwise. Let us fix $d=4$ and set $s=\mathrm{𝖾𝗏𝖾𝗇}$. Observe that

   There are precisely four partitions of $[4]$ that only contain even sized blocks: $\{\{1,2\},\{3,4\}\}$, $\{\{1,3\},\{2,4\}\}$, $\{\{1,4\},\{2,3\}\}$, and $\{\{1,2,3,4\}\}$. The former three each contribute ${(-1)}^{2-1}(2-1)!=-1$ to $\chi (4,s)$, and the latter contributes ${(-1)}^{1-1}(1-1)!=1$ to $\chi (4,s)$. Thus $\chi (4,s)=-3+1=-2\ne 0$ and $𝒮=\{\mathrm{𝖾𝗏𝖾𝗇}\}$ is, as promised, of type $𝕋[\mathrm{\infty }]$.

In some cases, e.g. for signatures with co-domain $\{0,1\}$, it will be possible to simplify the definition of the types. Moreover, we will show that $𝕋[\mathrm{𝖫𝗂𝗇}]$ can always be simplified if $s(0)=1$ for each signature (and we will later see that we can always make this assumption without loss of generality).

We are now able to state our main results. Some of the lower bounds rely on two well-known hardness assumptions from fine-grained complexity theory: The Exponential Time Hypothesis (ETH), and the Triangle Conjecture. We introduce both in the full version [1, Section 2.4.1]; in a nutshell, ETH asserts that $3$-SAT cannot be solved in sub-exponential time in the number of variables, and the Triangle conjecture asserts that there is no linear-time algorithm for finding a triangle in a graph.

At the time of writing this paper the matrix multiplication exponent $\omega$ is known to be bounded by $2\le \omega \le 2.371552$ [57]. Note that the lower bound in (III) matches, up to a factor of $1/\log k$ in the exponent, the running time of the brute force algorithm – which runs in time ${|\mathrm{\Omega }|}^{𝒪(k)}$ – making this bound (almost) tight. Moreover, the factor $1/\log k$ is not an artifact of our proofs, but a consequence of the notoriously open problem of whether “you can beat treewidth” [41].

We emphasise that our complexity trichotomy above is much stronger than an FPT vs $\mathrm{\#}\mathrm{W}[1]$ classification result: Under ETH and the Triangle Conjecture, the best possible exponent of $|\mathrm{\Omega }|$ in the running time is either $1$, or between $1$ and $\omega$, or lower bounded by $o(k/\log k)$. In particular, there are no FPT instances requiring an exponent larger than $\omega$.

Perhaps surprisingly, we discover that the complexity changes for the uncoloured holant problem; one can see in the full version [1, Section 6] that $\text{p-UnColHolant}(𝒮)$ appears to be strictly harder than $\text{p-Holant}(𝒮)$.

It turns out that we do not need to rely on any of the well-established tools for analysing holant problems, such as matchgates [9], combined signatures [26], or holographic reductions [56, 14], despite the fact that some of those tools have already been adapted to the realm of parameterised counting by Curticapean [21]. Instead, similarly to most works on exact parameterised counting throughout the last seven years [50, 29, 51, 8, 7, 30, 25, 31], we crucially rely on the framework of complexity monotonicity of graph motif parameters as introduced by Curticapean, Dell, and Marx [24]. In a nutshell, we show that both the coloured and the uncoloured holant problems can be cast as a finite linear combination of homomorphism counts. Let us make this explicit for the uncoloured version – in fact, the coloured version is easier to analyse, but requires a more extensive set-up on edge-coloured graphs, which we omit from the introduction for the sake of conceptual clarity.

Fix a finite set $𝒮=\{s_1,\mathrm{\dots },s_{\mathrm{\ell }}\}$ of signatures. We write $𝒢(𝒮)$ for the set of all signature grids over $𝒮$. Given two signature grids ${\mathrm{\Omega }}_H=(H,{\{s_v^H\}}_{v\in V(H)})$ and ${\mathrm{\Omega }}_G=(G,{\{s_v^G\}}_{v\in V(G)})$ in $𝒢(𝒮)$, a homomorphism from ${\mathrm{\Omega }}_H$ to ${\mathrm{\Omega }}_G$ is a graph homomorphism $\phi$ from $H$ to $G$ such that $s_{\phi (v)}^G=s_v^H$ for all $v\in V(H)$, that is $\phi$ must preserve signatures. We write $\mathrm{\#}\mathrm{𝖧𝗈𝗆}({\mathrm{\Omega }}_H\to {\mathrm{\Omega }}_G)$ for the number of homomorphisms from ${\mathrm{\Omega }}_H$ to ${\mathrm{\Omega }}_G$.

Using Möbius inversion, it is not hard to show that, for each $k$, there is a finitely supported function ${\zeta }_{𝒮,k}$ from $𝒢(𝒮)$ to algebraic complex numbers such that, for each signature grid $\mathrm{\Omega }$ over $𝒮$, we have

As mentioned before, a similar transformation exists for the colourful holant problem. Now, an adaptation of the principle of “complexity monotonicity” [24] will imply that evaluating the linear combination (2) is precisely as hard as evaluating its hardest term $\mathrm{\#}\mathrm{𝖧𝗈𝗆}({\mathrm{\Omega }}_H\to \mathrm{\Omega })$ with a non-zero coefficient ${\zeta }_{𝒮,k}({\mathrm{\Omega }}_H)\ne 0$. Fortunately, the complexity of evaluating the individual terms $\mathrm{\#}\mathrm{𝖧𝗈𝗆}({\mathrm{\Omega }}_H\to \mathrm{\Omega })$ is very well understood: under standard assumptions from fine-grained and parameterised complexity theory, the evaluation is hard if the treewidth of ${\mathrm{\Omega }}_H$ is large, and the evaluation is easy if the treewidth of ${\mathrm{\Omega }}_H$ is small. For this reason, the goal of understanding the complexity of parameterised holant problems can be reduced to the purely combinatorial problem of understanding the coefficient function ${\zeta }_{𝒮,k}$, and its analogue in the coloured setting.

In previous results, this approach has mostly been used for establishing lower bounds on pattern counting problems on graphs [35, 30, 22, 25], in which case it suffices to find a high-treewidth term that survives with a non-zero coefficient, and it has turned out that even finding one such a term can constitute solving highly challenging combinatorial problems [51, 48, 30, 31]. Using the framework for upper bounds is usually even more difficult since it makes it necessary to find an upper bound on the treewidth of all graphs surviving with a non-zero coefficient (see e.g. [47, 3, 8, 7]). In the current work, we solve this task as precisely as possible; intuitively, our main combinatorial result reads as follows:

The maximum treewidth of the graphs surviving in the “homomorphism basis” of any instance of a parameterised Holant problem (coloured or uncoloured) is either $1$, $2$, or unbounded.

Concretely, in the coloured setting, we show that

1. (1)

   for $𝒮$ of type $𝕋[\mathrm{𝖫𝗂𝗇}]$ all terms of treewidth $\ge 2$ vanish,

2. (2)

   for $𝒮$ of type $𝕋[\omega ]$ all terms of treewidth $\ge 3$ vanish, but at least one term of treewidth $2$ survives, and

3. (3)

   for $𝒮$ of type $𝕋[\mathrm{\infty }]$, terms of arbitrary high treewidth survive.

In the uncoloured setting (specifically in Equation (2)), we show that

1. (1)

   for $𝒮$ of type $𝕋[\mathrm{𝖫𝗂𝗇}]$ all terms of treewidth $\ge 2$ vanish,

2. (2)

   for $𝒮$ of type $𝕋[\omega ]$ or $𝕋[\mathrm{\infty }]$, terms of arbitrary high treewidth survive.

We consider the combinatorial analysis of the coefficients $\zeta$ to be the central technical contribution of this work. Moreover, we emphasize that, by understanding the coefficients in this detail, our work is, to the best of our knowledge, the only application of the framework of complexity monotonicity achieving a classification of a general family of counting problems into FPT and $\mathrm{\#}\mathrm{W}[1]$-complete cases in which the exponents of all FPT cases are almost precisely determined under assumptions from fine-grained complexity theory.

In this work, we focused on symmetric signatures for parameterised Holant problems. We provided complete classifications for both the coloured and the uncoloured variant of the problem, not only identifying precisely those instances that allow for FPT algorithms, but also proving almost tight bounds for the best possible run-time exponents under assumptions from fine-grained complexity theory.

We identify the following questions as starting points for future research on parameterised Holants:

• $\mathrm{■}$

  Asymmetric signatures. In classical Holant theory, after the case of symmetric (boolean) signatures had been solved [13], a significant amount of effort has been put in understanding asymmetric signatures, which involve more intricate cases than the classifications for symmetric signatures [11, 10, 45]. We expect that the tools we set up for the study of parameterised Holants can be generalised to apply to the asymmetric setting via encoding the orderings of activated incident edges to a vertex by imposing constraints on the set of tuples of edge-colours.

• $\mathrm{■}$

  Polynomial Time vs. $\mathrm{\#}\mathrm{P}$-hardness. The FPT cases of our classifications are all “real” FPT cases in the sense that the running time of our algorithms yields superpolynomial overhead in the parameter $k$. For a future direction, we propose to study for which cases the superpolynomial overhead is necessary, under standard assumptions from (counting) complexity theory such as $\mathrm{FP}\ne \mathrm{\#}\mathrm{P}$.