Symmetric Parameterised Holants on Hypergraphs: Towards a Classification for Parameterised VCSPs

The weighted satisfiability problem WSAT asks, given a Boolean formula $F$ and a positive integer $k$, whether $F$ contains a satisfying assignment of Hamming weight $k$, that is, whether it is possible to satisfy the formula by setting precisely $k$ variables to $1$. Similarly, its counting version $\mathrm{\#}\text{WSAT}$ asks to compute the number of such assignments. WSAT and $\mathrm{\#}\text{WSAT}$ are the foundational problems for the complexity theory of parameterised decision and counting problems: depending on the allowed structure of the input formula²²2The “W” in the $\mathrm{W}$-hierarchy stands for “weft”, which describes a structural property of boolean circuits., they define, respectively, the $\mathrm{W}$ and the $\mathrm{\#}\mathrm{W}$-hierarchies, including the classes $\mathrm{W}[1]$ and $\mathrm{\#}\mathrm{W}[1]$, which can be considered the parameterised decision and counting equivalents of $\mathrm{NP}$. We refer the reader to the standard textbook of Flum and Grohe [29] for a comprehensive introduction to structural parameterised complexity theory.

Notably, WSAT and $\mathrm{\#}\text{WSAT}$ constitute the most rudimentary instances of parameterised CSP and $\mathrm{\#}$CSP, and it comes to no surprise that analogues of Schaefer’s dichotomy, both for decision and for counting, have already been established for those problems [38, 7, 17]. The key difference in the parameterised setting is that the notion of tractability is relaxed from polynomial-time algorithms to fixed-parameter tractable “FPT” algorithms, the requirement for which is a running time bound of $f(k)\cdot n^{O(1)}$, where $n$ is the input size and $k$ is the problem parameter – in this work, $k$ will always be the Hamming weight of the sought solutions. The function $f$ can be any computable function; in other words, we allow for a super-polynomial overhead only in the problem parameter, reflecting the assumption that the parameter is significantly smaller than the input size in problem instances of interest (see [7] for a discussion on this assumption in the context of parameterised CSPs).

When studying families of parameterised CSPs, the goal is, thus, to classify the problems into instances that are FPT and instances that are hard for a class in the $\mathrm{W}$ (or $\mathrm{\#}\mathrm{W}$) hierarchy. In particular, it is well-known that under the exponential time hypothesis (ETH) [31, 32], which asserts that 3-SAT cannot be solved in time $\mathrm{𝖾𝗑𝗉}(o(n))$ (where $n$ is the number of variables of the input formula), $(\mathrm{\#})\mathrm{W}[1]$-hard problems are not in FPT [14, 15, 22]. In addition to the aforementioned analogues of Schaefer’s dichotomy, such classifications have also been achieved for the problems of finding and counting homomorphisms between relational structures, which can both be expressed as parameterised $(\mathrm{\#})$CSPs (see [30, 23]).

However, all existing results are limited by either focusing on a special case (such as simple, undirected graph homomorphisms) or by the restriction to finite constraint languages. For example, the following natural counting problems cannot be expressed in existing frameworks for parameterised $\mathrm{\#}$CSPs:³³3We note that special cases of $\mathrm{\#}{\text{CodeWord}}_p$ and of $\mathrm{\#}\text{Factor}(S)$, such as restrictions to certain input matrices and to graphs, are expressible in existing frameworks such as in [1]. However, the complexity of both problems has not been fully resolved yet.

• $\mathrm{■}$

  Let $p$ be a prime. The problem $\mathrm{\#}{\text{CodeWord}}_p$ gets as input a matrix $A$ over $\mathbb{Z}/p\mathbb{Z}$ and a positive integer $k$, and the goal is to compute the number of solutions to the system of linear equations $A\overrightarrow{x}=\overrightarrow{0}$ (also over $\mathbb{Z}/p\mathbb{Z}$) that set precisely $k$ variables to $1$ (and the other variables to $0$). Note that $\mathrm{\#}{\text{CodeWord}}_2$ is identical to the counting version of Exact-Even-Set (see e.g. [25]).

• $\mathrm{■}$

  Let $S\subseteq \mathbb{N}$. The problem $\mathrm{\#}\text{Factor}(S)$ gets as input a hypergraph $H$ and a positive integer $k$, and the goal is to compute the number of $k$-edge-subsets of $H$ that induce a hypergraph in which the degree of every vertex is in $S$. Given $d\in \mathbb{N}$, we denote $\mathrm{\#}{\text{Factor}}_d(S)$ for the restriction to $d$-uniform hypergraphs. For example, $\mathrm{\#}{\text{Factor}}_d(\{0,1\})$ is identical to the problem of counting $k$-matchings in $d$-uniform hypergraphs, where a matching in a hypergraph is a set of pairwise disjoint hyperedges.

In this work, we introduce and study a version of parameterised $\mathrm{\#}$CSP which is powerful enough in expressibility to model the previous problems – in fact, we will consider a much more general model which can also describe constraints that map assignments to arbitrary numbers (rather than to just $\mathrm{𝖳𝗋𝗎𝖾}$ or $\mathrm{𝖥𝖺𝗅𝗌𝖾}$). Moreover, we will be able to provide complete complexity classifications for our model which reveal the complexity of the aforementioned examples as straightforward special cases.

We show in a very simple reduction, that holant problems on hypergraphs are VCSPs (and vice versa). In particular, here we show the equivalence for the respective parameterised problems. We stress that for the aforementioned equivalence to hold, we need to modify our definition of holant problems such that the underlying hypergraphs allow for multi-hyperedges, i.e., multiple copies of the same hyperedge may appear. However, this is only a technical subtlety that we do not need to consider in the rest of the paper. The reason is that all of our hardness results for the restricted holant problems transfer trivially to the more general holant problems that allows for multi-hyperedges and as we show in the full version (see [2]) our tractability results still apply as well.

We let $ℱ$ be a finite set of functions $f:{\{0,1\}}^r\to ℂ$ and recall that, given a set $X$ of $n$ variables $x_1,\mathrm{\dots },x_n$, a set $C$ of $m$ constraints of the form $⟨f,(x_{i_1},\mathrm{\dots },x_{i_r})⟩$, where $f\in ℱ$, and a positive integer $k$, the problem $\text{p-VCSP}(ℱ)$ computes

Given $ℐ=(X,C,k)$, we construct a hypergraph $G(ℐ)$, that will be used as the underlying hypergraph of the intended holant instance, as follows. Each constraint $c\in C$ corresponds to a (unique) vertex $v_c\in G(ℐ)$ and each variable $x\in X$ corresponds to a (unique) hyperedge $e_x\in E(G(ℐ))$ given as $\{v_c\mid x\text{ is in the scope of }c\}$. Note that, there may be variables $x\ne x^{\prime }$ such that $e_x=e_{x^{\prime }}$. We allow $G(ℐ)$ to contain multiple copies of the same hyperedge, such that each variable $x$ corresponds uniquely to (some copy of) $e_x$.

Next, we let $\mathrm{\Omega }(ℐ)$ denote the signature grid obtained from $G(ℐ)$ by equipping, for each $c=(f,(x_{i_1},\mathrm{\dots },x_{i_r}))\in C$, the variable $v_c$ with the signature $s_{v_c}=f$. We also assume that the order of the arguments of $f$ is preserved, that is, if $x$ is the $j$-th argument of $f$, then $e_x$ is the $j$-th argument of $s_{v_c}$. It can be readily verified that $Z(ℐ)=\text{Holant}(\mathrm{\Omega }(ℐ),k).$

Furthermore, the reverse direction, that is, formulating a (parameterised) generalised holant problem as a VSCP can be achieved in a similar fashion.

The parameterised complexity of the problem ${\text{p-Holant}}_{\text{uni}}^2(𝒮)$ was recently classified by Aivasiliotis et al. [1]. The classification criterion depends on the type of the set of allowed signatures, as defined in [1], which we also define here momentarily, for reasons of self-containment. In particular, only signature sets that exclude signatures $s$ with $s(0)=0$ are assigned a type in [1] and the reason is that – roughly speaking – signatures $s$ with $s(0)=0$ do not affect the parameterised complexity of the problem, as it was shown in [1]. In other words, any fixed-parameter tractable finite set of signatures remains fixed-parameter tractable even if we add to it any number of signatures $s$ with $s(0)=0$. However, we will see that this is not necessarily true for polynomial-time tractability, which is why we explicitly include the case of $s(0)=0$ in the present paper.

The type of a signature set is decided by the signature fingerprint function, which is a combinatorial sum that is reminiscent of the Möbius function of partition lattices, given as follows.

It was shown in [1] that there are infinitely many signature sets of each type. We are now ready to state the known complexity dichotomy for ${\text{p-Holant}}_{\text{uni}}^2(𝒮)$. In particular, it is only the signature sets of the first type that render the problem tractable. However, the third type of signature sets allow for tighter conditional lower bounds.

Finally, the tractability criteria above are in fact explicit, in the sense that for a set $𝒮$ of signatures of type $𝕋[1]$ and a signature $s\in 𝒮$, we know that $s$ has the following explicit representation: $s(n)={\alpha }^n$, for some $\alpha \in ℂ$. The above implies that $s(0)=1$ must be assumed, but in the context of holant problems it is well-known that scaling a signature by some constant, does not affect the complexity of the problem.

In this part, we explore some well established approaches that appear, at first glance, to allow for deriving complexity classifications for holants on hypergraphs; however, as we argue below, they turn out to be insufficient for our (parameterised and classical) settings.

Firstly, as it has already been pointed out, holant problems on hypergraphs are equivalent to a natural class of symmetric counting constraint satisfaction problems (see Section 1.2). Furthermore, readers familiar with classical holant theory might be aware that the extension of signature grids from graphs to hypergraphs has only limited benefits since classifications for higher arity $\mathrm{\#}$CSPs had already been known when the holant framework was introduced – e.g. the dichotomy for $\mathrm{\#}$CSP [4] first appeared in ICALP’08 while for holants [11] in STOC’13. However, in the parameterised world where we only consider assignments that map precisely $k$ variables/edges to $1$, the situation is flipped: not much is known about the complexity of $\mathrm{\#}$CSP for higher arities and the framework of parameterised holants on hypergraphs allows us to tackle such problems.

Secondly, holants on hypergraphs are also known to reduce, in the classical sense, to holants on graphs via incidence graphs; we provide the details for the sake of self-containment: To this end, we let $𝒮$ be a finite set of signatures. We consider a hypergraph $G$ and an assignment ${\{s_v\}}_{v\in V(G)}$ of signatures from $𝒮$ to its vertices. It is folklore that any hypergraph can be represented as a bipartite incidence graph $B$ as follows. We let $V(B)=L\dot{\cup }R$ and consider two arbitrary bijections ${\pi }_L:V(G)\to L$ and ${\pi }_R:E(G)\to R$. Furthermore, for each $v\in V(G)$ and each $e\in E(G)$ such that $v\in e$, we add $\{{\pi }_L(v),{\pi }_R(e)\}$ to $E(B)$. Then, we consider the following assignment ${\{s_v^{\prime }\}}_{v\in V(B)}$ of signatures to $V(B)$: for each $v\in L$ we assign to $v$ the signature of ${\pi }_L^{-1}(v)$ and for each $u\in R$, we assign to $u$ the signature ${=}_{\mathrm{\ell }}:{\{0,1\}}^{\mathrm{\ell }}\to \{0,1\}$ where $\mathrm{\ell }=|{\pi }_R^{-1}(e)|$ and ${=}_{\mathrm{\ell }}$ evaluates to one if and only if all of its arguments are equal. It can be readily verified that

where $s_v^{\prime }$ is either in $𝒮$ or is an equality signature ${=}_{\mathrm{\ell }}$ for some $\mathrm{\ell }\in \mathbb{N}$. In other words, holants on hypergraphs reduce to holants on (bipartite) graphs assuming – besides $𝒮$ – freely available equality signatures.

It is known that signatures for equality (i.e., ${=}_{\mathrm{\ell }}$) are part of the tractable family of affine signatures, implying the easiness of holant problems on hypergraphs. Moreover, hardness of holants on graphs transfer directly to holant problems on hypergraphs since the former is a special case of the latter.

However, we point out that the aforementioned trivial equivalence already becomes incomplete when introducing even mild natural restrictions to the problem, e.g., restricting holants to uniform hypergraphs of fixed rank (i.e., of upper-bounded maximum hyperedge-size), or, more importantly, by not allowing freely available equality signatures, which cases are considered and remedied in this work. Note that the latter case is realised when we only consider signatures of infinite domain which are our main consideration. It is easy to see that such signatures cannot model equality signatures.

We provide exhaustive complexity dichotomy results both with respect to classical complexity theory ($\mathrm{P}$ vs. $\mathrm{\#}\mathrm{P}$) and with respect to parameterised complexity theory ($\mathrm{FPT}$ vs. $\mathrm{\#}\mathrm{W}[1]$).

We first state our main results in the parameterised setting. As it has been already pointed out, the problem ${\text{p-Holant}}_{\text{uni}}^d(𝒮)$ is a “slice” of $\text{p-Holant}(𝒮)$. The above implies that we need not state two complexity dichotomies, since an FPT algorithm for the latter problem implies an FPT algorithm for the former (w.r.t. the respective parametrisation) and if any slice of $\text{p-Holant}(𝒮)$ is hard, then $\text{p-Holant}(𝒮)$ must already be hard. Hence, our main result – stated formally below – consists of

1. 1.

   an FPT algorithm for $\text{p-Holant}(𝒮)$, for finite sets of signatures $𝒮$ of type $𝕋[1]$, which also addresses the tractable case in which $𝒮$ contains signatures $s$ with $s(0)=0$.

2. 2.

   $\mathrm{\#}\mathrm{W}[1]$-hardness results for the problem ${\text{p-Holant}}_{\text{uni}}^d(𝒮)$, for any $d\ge 2$.

We recall that the parameterised complexity in the special case of ${\text{p-Holant}}_{\text{uni}}^2(𝒮)$, that is, the case of graphs, has already been established in [1].

Note that the previous result implies that all FPT cases are in fact FPT-near-linear time solvable. We also classify the aforementioned problems in the non-parameterised setting. We point out that such a classification is novel even for the case of graphs (that is, $d=2$).

Note that the second part (2.) in the previous result implies that ${\text{p-Holant}}_{\text{uni}}^d(𝒮)$ is $\mathrm{\#}\mathrm{P}$-hard whenever $𝒮$ contains a signature $s$ with $s(0)=0$ but $s(x)\ne 0$ for some $x>0$.

As we explain in Section 1.2 our theorems immediately imply the analogous classifications for (the classical and parameterised) complexity of p-VCSP. We now give two applications of our main results:

Before we conclude our introduction, we give a brief exposition of the machinery we are employing for deriving our results.

Following the recent advancements of Aivasiliotis et al. [1], in the line of work for charting the complexity of parameterised holant problems introduced by Curticapean [19], we introduce generalised parameterised holant problems that can model parameterised VCSPs. The latter can be seen as the counting counterpart (that assumes complex values) of the parameterised satisfiability problem introduced and classified by Marx in [38], the parametrisation of which is given by the solution-size which is restricted to some $k\in {\mathbb{Z}}_{\ge 0}$.

We fully classify the complexity of parameterised VCSPs (as well as the complexity of the non-parameterised equivalent problems) for unbounded symmetric constraints. In particular, several natural variants are also considered subject to additional restrictions, e.g., when no two variables can appear in the same set of constraints and/or variables appear in exactly $d$ constraints, that is the occurrence of every variable is precisely $d$.

As mentioned above, in our setting we assumed unbounded arity (of constraints) and in particular, we further assumed bounded occurrence of (variables). For the rest of this section, we would like to elaborate on the other possible configurations of the problem with respect to the (un)boundedness of the arity and the occurrence.

First, in the context of unbounded arity, we show that trivially tractable instances of the problem already become $\mathrm{W}[2]$-hard if we assume unbounded occurrences (see [2]). In this context, an FPT Turing-reduction from parameterised VCSPs to the problem of evaluating graph motif parameters would imply the collapse of $\mathrm{W}$-hierarchy, since the expansion of instances of the latter problem into the homomorphism basis includes patterns, the size of which is not bounded by the (only) parameter $k$. This shows that a novel framework becomes necessary for tackling those instances of parameterised #CSPs, which is an exciting avenue for future work.

Next, in the context of bounded arity, if we further assume that occurrence is bounded then we can infer trivial fixed-parameter tractability results (for all instances) which follow from standard algorithmic techniques in parameterised complexity such as the bounded search-tree paradigm.

The last case, that is the combination of bounded arity and unbounded occurrence, is not remedied in this work as it is orthogonal to our main setting of interest. Hence we leave this family of parameterised #CSPs open for investigation in future work.