We investigate the complexity of parameterised holant problems p-Holant(𝒮) for families of symmetric signatures 𝒮. The parameterised holant framework has been introduced by Curticapean in 2015 as a counter-part to the classical and well-established theory of holographic reductions and algorithms, and it constitutes an extensive family of coloured and weighted counting constraint satisfaction problems on graph-like structures, encoding as special cases various well-studied counting problems in parameterised and fine-grained complexity theory such as counting edge-colourful k-matchings, graph-factors, Eulerian orientations or, more generally, subgraphs with weighted degree constraints. We establish an exhaustive complexity trichotomy along the set of signatures 𝒮: Depending on the signatures, p-Holant(𝒮) is either 1) solvable in "FPT-near-linear time", i.e., in time f(k)⋅ 𝒪̃(|x|), or 2) solvable in "FPT-matrix-multiplication time", i.e., in time f(k)⋅ {𝒪}(n^{ω}), where n is the number of vertices of the underlying graph, but not solvable in FPT-near-linear time, unless the Triangle Conjecture fails, or 3) #W[1]-complete and no significant improvement over the naive brute force algorithm is possible unless the Exponential Time Hypothesis fails. This classification reveals a significant and surprising gap in the complexity landscape of parameterised Holants: Not only is every instance either fixed-parameter tractable or #W[1]-complete, but additionally, every FPT instance is solvable in time (at most) f(k)⋅ {𝒪}(n^{ω}). We show that there are infinitely many instances of each of the types; for example, all constant signatures yield holant problems of type (1), and the problem of counting edge-colourful k-matchings modulo p is of type (p) for p ∈ {2,3}. Finally, we also establish a complete classification for a natural uncoloured version of parameterised holant problem p-UnColHolant(𝒮), which encodes as special cases the non-coloured analogues of the aforementioned examples. We show that the complexity of p-UnColHolant(𝒮) is different: Depending on 𝒮 all instances are either solvable in FPT-near-linear time, or #W[1]-complete, that is, there are no instances of type (2).

Given a graph property [Formula: see text], the problem [Formula: see text] asks, on input of a graph [Formula: see text] and a positive integer [Formula: see text], to compute the number [Formula: see text] of induced subgraphs of size [Formula: see text] in [Formula: see text] that satisfy [Formula: see text]. The search for explicit criteria on [Formula: see text] ensuring that [Formula: see text] is hard was initiated by Jerrum and Meeks [ J. Comput. System Sci., 81 (2015), pp. 702–716] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell, and Marx [ STOC, ACM, New York, pp. 151–158] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [ Discrete Appl. Math., 198 (2016), pp. 170–194] and Dörfler et al. [ MFCS, LIPIcs Leibniz Int. Proc. Inform. 138, Wadern Germany, 2019, 26], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is, subgraph-closed, properties: We show that for any nontrivial monotone property [Formula: see text], the problem [Formula: see text] cannot be solved in time [Formula: see text] for any function [Formula: see text], unless the exponential time hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a [Formula: see text]-completeness result. The methods we develop for the above problem also allow us to prove a conjecture by Jerrum and Meeks [ ACM Trans. Comput. Theory, 7 (2015), 11; Combinatorica 37 (2017), pp. 965–990]: [Formula: see text] is [Formula: see text]-complete if [Formula: see text] is a nontrivial graph property only depending on the number of edges of the graph.

Abstract. Given a graph property [Formula: see text], we consider the problem [Formula: see text] EdgeSub [Formula: see text], where the input is a pair of a graph [Formula: see text] and a positive integer [Formula: see text], and the task is to compute the number of [Formula: see text]-edge subgraphs in [Formula: see text] that satisfy [Formula: see text]. Specifically, we study the parameterized complexity of [Formula: see text] EdgeSub [Formula: see text] with respect to both approximate and exact counting, as well as its decision version EdgeSub [Formula: see text]. Among others, our main result fully resolves the case of minor-closed properties [Formula: see text]: the decision problem EdgeSub [Formula: see text] always admits a fixed-parameter tractable algorithm, and the counting problem [Formula: see text] EdgeSub [Formula: see text] always admits a fixed-parameter tractable randomized approximation scheme. For exact counting, we present an exhaustive and explicit criterion on the property [Formula: see text] which, if satisfied, yields fixed-parameter tractability and otherwise [Formula: see text]-hardness. Additionally, our hardness results come with an almost tight conditional lower bound under the exponential time hypothesis. Our main technical result concerns the exact counting problem: Building upon the breakthrough result of Curticapean, Dell, and Marx (Symposium on Theory of Computing 2017), we express the number of subgraphs satisfying [Formula: see text] as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of [Formula: see text]-groups, which might be of independent interest. The properties of those expanders allow us to analyze the coefficients in the aforementioned linear combinations over the field [Formula: see text] which gives us significantly more control over the cancelation behavior of the coefficients.

Abstract We study the problem $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy the property $$\varPhi $$ Φ . It is shown that, given any graph property $$\varPhi $$ Φ that distinguishes independent sets from bicliques, $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) is hard for the class $$\#\mathsf {W[1]}$$ # W [ 1 ] , i.e., the parameterized counting equivalent of $${{\mathsf {N}}}{{\mathsf {P}}}$$ N P . Under additional suitable density conditions on $$\varPhi $$ Φ , satisfied e.g. by non-trivial monotone properties on bipartite graphs, we strengthen $$\#\mathsf {W[1]}$$ # W [ 1 ] -hardness by establishing that $$\#\textsc {IndSub}(\varPhi )$$ # I N D S U B ( Φ ) cannot be solved in time $$f(k)\cdot n^{o(k)}$$ f ( k ) · n o ( k ) for any computable function f, unless the Exponential Time Hypothesis fails. Finally, we observe that our results remain true even if the input graph G is restricted to be bipartite and counting is done modulo a fixed prime.

Given a graph property $Φ$, we consider the problem $\mathtt{EdgeSub}(Φ)$, where the input is a pair of a graph $G$ and a positive integer $k$, and the task is to decide whether $G$ contains a $k$-edge subgraph that satisfies $Φ$. Specifically, we study the parameterized complexity of $\mathtt{EdgeSub}(Φ)$ and of its counting problem $\#\mathtt{EdgeSub}(Φ)$ with respect to both approximate and exact counting. We obtain a complete picture for minor-closed properties $Φ$: the decision problem $\mathtt{EdgeSub}(Φ)$ always admits an FPT algorithm and the counting problem $\#\mathtt{EdgeSub}(Φ)$ always admits an FPTRAS. For exact counting, we present an exhaustive and explicit criterion on the property $Φ$ which, if satisfied, yields fixed-parameter tractability and otherwise $\#\mathsf{W[1]}$-hardness. Additionally, most of our hardness results come with an almost tight conditional lower bound under the so-called Exponential Time Hypothesis, ruling out algorithms for $\#\mathtt{EdgeSub}(Φ)$ that run in time $f(k)\cdot|G|^{o(k/\log k)}$ for any computable function $f$. As a main technical result, we gain a complete understanding of the coefficients of toroidal grids and selected Cayley graph expanders in the homomorphism basis of $\#\mathtt{EdgeSub}(Φ)$. This allows us to establish hardness of exact counting using the Complexity Monotonicity framework due to Curticapean, Dell and Marx (STOC'17). Our methods can also be applied to a parameterized variant of the Tutte Polynomial $T^k_G$ of a graph $G$, to which many known combinatorial interpretations of values of the (classical) Tutte Polynomial can be extended. As an example, $T^k_G(2,1)$ corresponds to the number of $k$-forests in the graph $G$. Our techniques allow us to completely understand the parametrized complexity of computing the evaluation of $T^k_G$ at every pair of rational coordinates $(x,y)$.

We study the problem $\#\mathrm{EdgeSub}(Φ)$ of counting $k$-edge subgraphs satisfying a given graph property $Φ$ in a large host graph $G$. Building upon the breakthrough result of Curticapean, Dell and Marx (STOC 17), we express the number of such subgraphs as a finite linear combination of graph homomorphism counts and derive the complexity of computing this number by studying its coefficients. Our approach relies on novel constructions of low-degree Cayley graph expanders of $p$-groups, which might be of independent interest. The properties of those expanders allow us to analyse the coefficients in the aforementioned linear combinations over the field $\mathbb{F}_p$ which gives us significantly more control over the cancellation behaviour of the coefficients. Our main result is an exhaustive and fine-grained complexity classification of $\#\mathrm{EdgeSub}(Φ)$ for minor-closed properties $Φ$, closing the missing gap in previous work by Roth, Schmitt and Wellnitz (ICALP 21). Additionally, we observe that our methods also apply to modular counting. Among others, we investigate the problems of modular counting of paths, cycles, forests and matroid bases. In the course of our investigations we also provide an exhaustive parameterized complexity classification for the problem of counting graph homomorphisms modulo a prime $p$.

Given a graph property Φ, we study the problem #INDSUB(Φ) which asks, on input a graph G and a positive integer k, to compute the number # IndSub(Φ, k→ G) of induced subgraphs of size k in G that satisfy Φ. The search for explicit criteria on Φ ensuring that # INDSUB(Φ) is hard was initiated by Jerrum and Meeks [J. Comput. Syst. Sci. 15] and is part of the major line of research on counting small patterns in graphs. However, apart from an implicit result due to Curticapean, Dell and Marx [STOC 17] proving that a full classification into “easy” and “hard” properties is possible and some partial results on edge-monotone properties due to Meeks [Discret. Appl. Math. 16] and Dörfler et al. [MFCS 19], not much is known. In this work, we fully answer and explicitly classify the case of monotone, that is subgraph-closed, properties: We show that for any non-trivial monotone property Φ, the problem #INDSUB(Φ) cannot be solved in time f(k). |V(G)|o(k/log1/2(k)) for any function f, unless the Exponential Time Hypothesis fails. By this, we establish that any significant improvement over the brute-force approach is unlikely; in the language of parameterized complexity, we also obtain a #W[1] - completeness result.

Abstract We investigate the problem $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) of counting all induced subgraphs of size k in a graph G that satisfy a given property $$\varPhi $$ Φ . This continues the work of Jerrum and Meeks who proved the problem to be $$\#{{\mathrm {W[1]}}}$$ # W [ 1 ] -hard for some families of properties which include (dis)connectedness [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Using the recent framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], we discover that for monotone properties $$\varPhi $$ Φ , the problem $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) is hard for $$\#{{\mathrm {W[1]}}}$$ # W [ 1 ] if the reduced Euler characteristic of the associated simplicial (graph) complex of $$\varPhi $$ Φ is non-zero. This observation links $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) to Karp’s famous Evasiveness Conjecture, as every graph complex with non-vanishing reduced Euler characteristic is known to be evasive. Applying tools from the “topological approach to evasiveness” which was introduced in the seminal paper of Khan, Saks and Sturtevant [FOCS 83], we prove that $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) is $$\#{{\mathrm {W[1]}}}$$ # W [ 1 ] -hard for every monotone property $$\varPhi $$ Φ that does not hold on the Hamilton cycle as well as for some monotone properties that hold on the Hamilton cycle such as being triangle-free or not k-edge-connected for $$k > 2$$ k > 2 . Moreover, we show that for those properties $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) can not be solved in time $$f(k)\cdot n^{o(k)}$$ f ( k ) · n o ( k ) for any computable function f unless the Exponential Time Hypothesis (ETH) fails. In the final part of the paper, we investigate non-monotone properties and prove that $$\#{{\mathsf {IndSub}}}(\varPhi )$$ # IndSub ( Φ ) is $$\#{{\mathrm {W[1]}}}$$ # W [ 1 ] -hard if $$\varPhi $$ Φ is any non-trivial modularity constraint on the number of edges with respect to some prime q or if $$\varPhi $$ Φ enforces the presence of a fixed isolated subgraph.

We study the problem #IndSub(Phi) of counting all induced subgraphs of size k in a graph G that satisfy the property Phi. This problem was introduced by Jerrum and Meeks and shown to be #W[1]-hard when parameterized by k for some families of properties Phi including, among others, connectivity [JCSS 15] and even- or oddness of the number of edges [Combinatorica 17]. Very recently [IPEC 18], two of the authors introduced a novel technique for the complexity analysis of #IndSub(Phi), inspired by the "topological approach to evasiveness" of Kahn, Saks and Sturtevant [FOCS 83] and the framework of graph motif parameters due to Curticapean, Dell and Marx [STOC 17], allowing them to prove hardness of a wide range of properties Phi. In this work, we refine this technique for graph properties that are non-trivial on edge-transitive graphs with a prime power number of edges. In particular, we fully classify the case of monotone bipartite graph properties: It is shown that, given any graph property Phi that is closed under the removal of vertices and edges, and that is non-trivial for bipartite graphs, the problem #IndSub(Phi) is #W[1]-hard and cannot be solved in time f(k)* n^{o(k)} for any computable function f, unless the Exponential Time Hypothesis fails. This holds true even if the input graph is restricted to be bipartite and counting is done modulo a fixed prime. A similar result is shown for properties that are closed under the removal of edges only.