We study the complexity of the parameterised counting constraint satisfaction problem: given a set of constraints over a set of variables and a positive integer k, how many ways are there to assign k variables to 1 (and the others to 0) such that all constraints are satisfied. While this problem, and its decision version, received significant attention during the last two decades, existing work has so far exclusively focused on restricted settings such as finding and counting homomorphisms between relational structures due to Grohe (JACM 2007) and Dalmau and Jonsson (TCS 2004), or the case of finite constraint languages due to Creignou and Vollmer (SAT 2012), and Bulatov and Marx (SICOMP 2014). In this work, we tackle a more general setting of parameterised (counting) valued constraint satisfaction problems (VCSPs) with infinite constraint languages: we allow our constraints to be chosen from an infinite set of permitted constraints and we allow our constraints to map an assignment of its variables not only to True or False, but to arbitrary values. In this setting we are able to model and classify significantly more general problems such as (weighted) parameterised factor problems on hypergraphs and counting weight-k solutions of systems of linear equations, none of which are captured by existing complexity classifications of parameterised constraint satisfaction problems. On a formal level, we express parameterised VCSPs as parameterised holant problems on uniform hypergraphs, and we establish complete and explicit complexity dichotomy theorems for this family of problems both w.r.t. classical complexity theory (P vs. #P) and parameterised complexity (FPT vs. #W[1]). For resolving the P vs. #P question, we mainly rely on the use of hypergraph gadgets, the existence of which we prove using properties of degree sequences necessary for realisability in uniform hypergraphs. As a technical highlight, we also employ Curticapean’s "CFI Filters" (SODA 2024) - named after the Cai-Fürer-Immermann construction for bounding the expressiveness of the Weisfeiler-Leman heuristic - to establish polynomial-time algorithms for isolating vectors in the homomorphism basis of some of our holant problems. For the FPT vs. #W[1] question, we build upon the recently established combinatorial toolkit for parameterised holants on the special case of graphs by Aivasiliotis et al. (ICALP 2025) and also rely on an extension of the framework of the homomorphism basis due to Curticapean, Dell and Marx (STOC 17) to uniform hypergraphs.

Subgraph counting is a fundamental and well-studied problem whose computational complexity is well understood. Quite surprisingly, the hypergraph version of subgraph counting has been almost ignored. In this work, we address this gap by investigating the most basic sub-hypergraph counting problem: given two hypergraphs \(H\) and \(G\), compute the number of sub-hypergraphs of \(G\) isomorphic to \(H\). Formally, for a family \(\mathcal{H}\) of hypergraphs, let #Sub\((\mathcal{H})\) be the restriction of the problem to \(H \in \mathcal{H}\); the induced variant #IndSub\((\mathcal{H})\) is defined analogously. Our main contribution is a complete classification of the fixed-parameter tractability of these problems. Assuming the Exponential Time Hypothesis, we prove that #Sub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional co-independent edge-cover number, a novel graph parameter introduced in this work, and that #IndSub\((\mathcal{H})\) is fixed-parameter tractable if and only if \(\mathcal{H}\) has bounded fractional edge-cover number. Both results subsume pre-existing results for graphs as special cases. We also show that the fixed-parameter tractable cases of #Sub\(\mathcal{H})\) and #IndSub\((\mathcal{H})\) are unlikely to be in polynomial time, unless respectively \(\#P = P\) and Graph Isomorphism \(\in\, P\). This shows a separation with the special case of graphs, where the fixed-parameter tractable cases are known to actually be in polynomial time. From a technical standpoint, we turn to the hypergraph homomorphism basis and lift the complexity monotonicity principle due to Curticapean, Dell, and Marx [STOC 2017] from graphs to hypergraphs of unbounded rank. Moreover, we crucially rely on the integrality gap for fractional independent sets based on adaptive width due to Bressan, Lanzinger, and Roth [STOC 2023]. The heart of our proofs consists of a careful investigation of the adaptive width of the patterns that survive in the hypergraph homomorphism basis. We also consider a natural variant of sub-hypergraphs where edges are trimmed to be vertex subsets; we show that, surprisingly, in this case complexity monotonicity fails.

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).

We study the complexity of approximating the number of answers to a small query \(\varphi\) in a large database \(\mathcal{D}\) . We establish an exhaustive classification into tractable and intractable cases if \(\varphi\) is a conjunctive query possibly including disequalities and negations: — If there is a constant bound on the arity of \(\varphi\) , and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of \(\varphi\) is bounded. — If the arity is unbounded and \(\varphi\) does not have negations, then the problem has an FPTRAS if and only if the adaptive width of \(\varphi\) (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless \(\mathrm{NP}=\mathrm{RP}\) , there is no FPRAS even if the treewidth (and the adaptive width) is \(1\) . However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).

Abstract Given a class of graphs $${\mathcal {H}}$$ H , the problem $$\oplus \text {{Sub}}({\mathcal {H}})$$ ⊕ Sub ( H ) is defined as follows. The input is a graph $$H\in {\mathcal {H}}$$ H ∈ H together with an arbitrary graph G. The problem is to compute, modulo 2, the number of subgraphs of G that are isomorphic to H. The goal of this research is to determine for which classes $${\mathcal {H}}$$ H the problem $$\oplus \text {{Sub}}({\mathcal {H}})$$ ⊕ Sub ( H ) is fixed-parameter tractable (FPT), i.e., solvable in time $$f(|H|)\cdot |G|^{O(1)}$$ f ( | H | ) · | G | O ( 1 ) . Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that $$\oplus \text {{Sub}}({\mathcal {H}})$$ ⊕ Sub ( H ) is FPT if and only if the class of allowed patterns $${\mathcal {H}}$$ H is matching splittable, which means that for some fixed B, every $$H \in {\mathcal {H}}$$ H ∈ H can be turned into a matching (a graph in which every vertex has degree at most 1) by removing at most B vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes $${\mathcal {H}}$$ H , and (II) all tree pattern classes, i.e., all classes $${\mathcal {H}}$$ H such that every $$H\in {\mathcal {H}}$$ H ∈ H is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).

A graph parameter is a function f on graphs with the property that, for any pair of isomorphic graphs G 1 and G 2 , f(G 1 )=f(G 2 ). The Weisfeiler--Leman (WL) dimension of f is the minimum k such that, if G 1 and G 2 are indistinguishable by the k-dimensional WL-algorithm then f(G 1 )=f(G 2 ). The WL-dimension of f is ∞ if no such k exists. We study the WL-dimension of graph parameters characterised by the number of answers from a fixed conjunctive query to the graph. Given a conjunctive query φ, we quantify the WL-dimension of the function that maps every graph G to the number of answers of φ in G. The works of Dvorak (J. Graph Theory 2010), Dell, Grohe, and Rattan (ICALP 2018), and Neuen (ArXiv 2023) have answered this question for full conjunctive queries, which are conjunctive queries without existentially quantified variables. For such queries φ, the WL-dimension is equal to the treewidth of the Gaifman graph of φ. In this work, we give a characterisation that applies to all conjunctive queries. Given any conjunctive query φ, we prove that its WL-dimension is equal to the semantic extension width sew(φ), a novel width measure that can be thought of as a combination of the treewidth of φ and its quantified star size, an invariant introduced by Durand and Mengel (ICDT 2013) describing how the existentially quantified variables of φ are connected with the free variables. Using the recently established equivalence between the WL-algorithm and higher-order Graph Neural Networks (GNNs) due to Morris et al. (AAAI 2019), we obtain as a consequence that the function counting answers to a conjunctive query φ cannot be computed by GNNs of order smaller than sew(φ). The majority of the paper is concerned with establishing a lower bound of the WL-dimension of a query. Given any conjunctive query φ with semantic extension width k, we consider a graph F of treewidth k obtained from the Gaifman graph of φ by repeatedly cloning the vertices corresponding to existentially quantified variables. Using a modification due to Furer (ICALP 2001) of the Cai-Fürer-Immerman construction (Combinatorica 1992), we then obtain a pair of graphs χ(F) and ^χ(F) that are indistinguishable by the (k-1)-dimensional WL-algorithm since F has treewidth k. Finally, in the technical heart of the paper, we show that φ has a different number of answers in χ(F) and ^χ(F). Thus, φ can distinguish two graphs that cannot be distinguished by the (k-1)-dimensional WL-algorithm, so the WL-dimension of φ is at least k.

We study the problem of counting answers to unions of conjunctive queries (UCQs) under structural restrictions on the input query. Concretely, given a class C of UCQs, the problem #UCQ (C) provides as input a UCQ Ψ ∈ C and a database D and the problem is to compute the number of answers of Ψ in D. Chen and Mengel [PODS'16] have shown that for any recursively enumerable class C, the problem #UCQ (C) is either fixed-parameter tractable or hard for one of the parameterised complexity classes W[1] or #W[1]. However, their tractability criterion is unwieldy in the sense that, given any concrete class C of UCQs, it is not easy to determine how hard it is to count answers to queries in C. Moreover, given a single specific UCQ Ψ, it is not easy to determine how hard it is to count answers to Ψ. In this work, we address the question of finding a natural tractability criterion: The combined conjunctive query of a UCQ Ψ=φ 1 ∨ ... ∨ φ l is the conjunctive query ^ Ψ = φ_1 ∧ ... ∧ φ l . We show that under natural closure properties of C, the problem #UCQ (C) is fixed-parameter tractable if and only if the combined conjunctive queries of UCQs in C, and their contracts, have bounded treewidth. A contract of a conjunctive query is an augmented structure, taking into account how the quantified variables are connected to the free variables --- if all variables are free, then a conjunctive query is equal to its contract; in this special case the criterion for fixed-parameter tractability of #UCQ (C) thus simplifies to the combined queries having bounded treewidth. Finally, we give evidence that a closure property on C is necessary for obtaining a natural tractability criterion: We show that even for a single UCQ Ψ, the meta problem of deciding whether #UCQ (Ψ) can be solved in time O(|D| d ) is NP-hard for any fixed d ≥ 1. Moreover, we prove that a known exponential-time algorithm for solving the meta problem is optimal under assumptions from fine-grained complexity theory. As a corollary of our reduction, we also establish that approximating the Weisfeiler-Leman-Dimension of a UCQ is NP-hard.

Abstract. We study the problems of counting copies and induced copies of a small pattern graph [Formula: see text] in a large host graph [Formula: see text]. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns [Formula: see text]. In this work, we address the more challenging task of analyzing the complexity for restricted patterns and restricted hosts. Specifically, we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time [Formula: see text] for some computable function [Formula: see text]. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes [Formula: see text] as our central objects of study and establish the following crisp dichotomies as consequences of the exponential time hypothesis: (1) Counting [Formula: see text]-matchings in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. (2) Counting [Formula: see text]-independent sets in a graph [Formula: see text] is fixed-parameter tractable if and only if [Formula: see text] is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if [Formula: see text] is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting [Formula: see text]-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in [Formula: see text]-colorable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting [Formula: see text]-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time, our proofs are much simpler: using structural characterizations of somewhere dense graphs, we show that a colorful version of a recent breakthrough technique for analyzing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.

Abstract. We study the computational complexity of the problem [Formula: see text] of counting [Formula: see text]-vertex induced subgraphs of a graph [Formula: see text] that satisfy a graph property [Formula: see text]. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): If a hereditary property [Formula: see text] is true for all graphs, or if it is true only for finitely many graphs, then [Formula: see text] is solvable in polynomial time. Otherwise, [Formula: see text] is [Formula: see text]-complete when parameterized by [Formula: see text], and, assuming ETH, it cannot be solved in time [Formula: see text] for any function [Formula: see text]. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [ Theoret. Comput. Sci., 289 (2002), pp. 997–1008]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As an additional result, we also present an exhaustive and explicit parameterized complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalize some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of [Formula: see text] for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [ SIAM J. Comput., (2022), pp. FOCS20-139–FOCS20-174].

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.

The multi-type Moran process is an evolutionary process on a connected graph G in which each vertex has one of k types and, in each step, a vertex v is chosen to reproduce its type to one of its neighbours. The probability of a vertex v being chosen for reproduction is proportional to the fitness of the type of v . So far, the literature was almost solely concerned with the 2-type Moran process in which each vertex is either healthy (type 0) or a mutant (type 1), and the main problem of interest has been the (approximate) computation of the so-called fixation probability , i.e., the probability that eventually all vertices are mutants. In this work we initiate the study of approximating fixation probabilities in the multi-type Moran process on general graphs. Our main result is an FPTRAS (fixed-parameter tractable randomised approximation scheme) for computing the fixation probability of the dominant mutation; the parameter is the number of types and their fitnesses. In the course of our studies we also provide novel upper bounds on the expected absorption time , i.e., the time that it takes the multi-type Moran process to reach a state in which each vertex has the same type.

Given a class of graphs $\mathcal{H}$, the problem $\oplus\mathsf{Sub}(\mathcal{H})$ is defined as follows. The input is a graph $H\in \mathcal{H}$ together with an arbitrary graph $G$. The problem is to compute, modulo $2$, the number of subgraphs of $G$ that are isomorphic to $H$. The goal of this research is to determine for which classes $\mathcal{H}$ the problem $\oplus\mathsf{Sub}(\mathcal{H})$ is fixed-parameter tractable (FPT), i.e., solvable in time $f(|H|)\cdot |G|^{O(1)}$. Curticapean, Dell, and Husfeldt (ESA 2021) conjectured that $\oplus\mathsf{Sub}(\mathcal{H})$ is FPT if and only if the class of allowed patterns $\mathcal{H}$ is "matching splittable", which means that for some fixed $B$, every $H \in \mathcal{H}$ can be turned into a matching (a graph in which every vertex has degree at most $1$) by removing at most $B$ vertices. Assuming the randomised Exponential Time Hypothesis, we prove their conjecture for (I) all hereditary pattern classes $\mathcal{H}$, and (II) all tree pattern classes, i.e., all classes $\mathcal{H}$ such that every $H\in \mathcal{H}$ is a tree. We also establish almost tight fine-grained upper and lower bounds for the case of hereditary patterns (I).

We study the problems of counting copies and induced copies of a small pattern graph H in a large host graph G. Recent work fully classified the complexity of those problems according to structural restrictions on the patterns H. In this work, we address the more challenging task of analysing the complexity for restricted patterns and restricted hosts. Specifically we ask which families of allowed patterns and hosts imply fixed-parameter tractability, i.e., the existence of an algorithm running in time f(H)⋅|G|^O(1) for some computable function f. Our main results present exhaustive and explicit complexity classifications for families that satisfy natural closure properties. Among others, we identify the problems of counting small matchings and independent sets in subgraph-closed graph classes 𝒢 as our central objects of study and establish the following crisp dichotomies as consequences of the Exponential Time Hypothesis: - Counting k-matchings in a graph G ∈ 𝒢 is fixed-parameter tractable if and only if 𝒢 is nowhere dense. - Counting k-independent sets in a graph G ∈ 𝒢 is fixed-parameter tractable if and only if 𝒢 is nowhere dense. Moreover, we obtain almost tight conditional lower bounds if 𝒢 is somewhere dense, i.e., not nowhere dense. These base cases of our classifications subsume a wide variety of previous results on the matching and independent set problem, such as counting k-matchings in bipartite graphs (Curticapean, Marx; FOCS 14), in F-colourable graphs (Roth, Wellnitz; SODA 20), and in degenerate graphs (Bressan, Roth; FOCS 21), as well as counting k-independent sets in bipartite graphs (Curticapean et al.; Algorithmica 19). At the same time our proofs are much simpler: using structural characterisations of somewhere dense graphs, we show that a colourful version of a recent breakthrough technique for analysing pattern counting problems (Curticapean, Dell, Marx; STOC 17) applies to any subgraph-closed somewhere dense class of graphs, yielding a unified view of our current understanding of the complexity of subgraph counting.

We study the fixed-parameter tractability of the following fundamental problem: given two directed graphs H→ and G→, count the number of copies of H→ in G→. The standard setting, where the tractability is well understood, uses only |H→| as a parameter. In this paper we adopt as a parameter |H→|+d(G→), where d(G→) is the maximum outdegree of |G→|. Under this parameterisation, we completely characterize the fixed-parameter tractability of the problem in both its non-induced and induced versions through two novel structural parameters, the fractional cover number ρ* and the source number αs. On the one hand we give algorithms with running time f(|H→|,d(G→)) · |G→|ρ*(H→)+O(1) and f(|H→|,d(G→)) · |G→|αs(H→)+O(1) for counting respectively the copies and induced copies of H→ in G→; on the other hand we show that, unless the Exponential Time Hypothesis fails, for any class C→ of directed graphs the restriction of the problem to patterns in C→ is fixed-parameter tractable if and only if ρ*(C→) is bounded (αs(C→) for the induced version). These results explain how the orientation of the pattern can make counting easy or hard, and prove that a classic algorithm by Chiba and Nishizeki and its extensions (Chiba and Nishizeki, SICOMP ’85; Bressan, Algorithmica ’21) are optimal unless ETH fails.

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.

We study the complexity of approximating the number of answers to a small query φ in a large database D. We establish an exhaustive classification into tractable and intractable cases if φ is a conjunctive query possibly including disequalities and negations: - If there is a constant bound on the arity of φ, and if the randomised Exponential Time Hypothesis (rETH) holds, then the problem has a fixed-parameter tractable approximation scheme (FPTRAS) if and only if the treewidth of φ is bounded. - If the arity is unbounded and φ does not have negations, then the problem has an FPTRAS if and only if the adaptive width of φ (a width measure strictly more general than treewidth) is bounded; the lower bound relies on the rETH as well. Additionally we show that our results cannot be strengthened to achieve a fully polynomial randomised approximation scheme (FPRAS): We observe that, unless NP=RP, there is no FPRAS even if the treewidth (and the adaptive width) is 1. However, if there are neither disequalities nor negations, we prove the existence of an FPRAS for queries of bounded fractional hypertreewidth, strictly generalising the recently established FPRAS for conjunctive queries with bounded hypertreewidth due to Arenas, Croquevielle, Jayaram and Riveros (STOC 2021).

We study the computational complexity of the problem #IndSub(Φ) of counting k-vertex induced subgraphs of a graph G that satisfy a graph property Φ. Our main result establishes an exhaustive and explicit classification for all hereditary properties, including tight conditional lower bounds under the Exponential Time Hypothesis (ETH): If a hereditary property Φ is true for all graphs, or if it is true only for finitely many graphs, then #IndSub(Φ) is solvable in polynomial time. Otherwise, #IndSub(Φ) is #W[1]-complete when parameterised by k, and, assuming ETH, it cannot be solved in time f(k)· |G|o(k) for any function f. This classification features a wide range of properties for which the corresponding detection problem (as classified by Khot and Raman [TCS 02]) is tractable but counting is hard. Moreover, even for properties which are already intractable in their decision version, our results yield significantly stronger lower bounds for the counting problem. As additional result, we also present an exhaustive and explicit parameterised complexity classification for all properties that are invariant under homomorphic equivalence. By covering one of the most natural and general notions of closure, namely, closure under vertex-deletion (hereditary), we generalise some of the earlier results on this problem. For instance, our results fully subsume and strengthen the existing classification of #IndSub(Φ) for monotone (subgraph-closed) properties due to Roth, Schmitt, and Wellnitz [FOCS 20]. A full version of our paper, containing all proofs, is available at https://arxiv.org/abs/2111.02277.

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.

We study the problems of counting the homomorphisms, the copies, and the induced copies of a$k$-vertex graph$H$in a$d$-degenerate$n$-vertex graph$G$. By leveraging a new family of graph-minor obstructions called F-gadgets, we establish explicit and exhaustive complexity classifications for counting copies and induced copies. For instance., we show that the copies of$H$in$G$can be counted in time$f(k, d)n^{\max(1,\mathsf{imn}(H))} \log n$, where$f$is some computable function and$\mathsf{imn} (H)$is the size of the largest induced matching of$H$; and that whenever the class of allowed patterns has arbitrarily large induced matchings, no algorithm runs in time$f(k, d)n^{o(\mathsf{imn}(H)/\log \mathsf{imn}(H))}$for any function$f$, unless the Exponential Time Hypothesis fails. A similar result holds for counting induced copies, with the independence number$\alpha(H)$in place of$\mathsf{imn}(H)$. These results imply complexity dichotomies, into fixed-parameter tractable versus #W[1]-hard cases, which parallel the well-known dichotomies when$d$is not a parameter. Our results also imply the #W[1]-hardness of counting several patterns, such as$k$-matchings and$k$-trees, in$d$- degenerate graphs. We also give new hardness results and approximation algorithms for generalized pattern counting (i.e., counting patterns with a given property) in degenerate graphs.

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$.

We study the problem of computing the parity of the number of homomorphisms from an input graph G to a fixed graph H. Faben and Jerrum [ToC'15] introduced an explicit criterion on the graph H and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class ⊕P of parity problems. We verify their conjecture for all graphs H that exclude the complete graph on 4 vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the ⊕P-complete cases, assuming the randomised Exponential Time Hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph H. Using this, we subsume all prior progress towards resolving the conjecture (Faben and Jerrum [ToC'15]; Göbel, Goldberg and Richerby [ToCT'14,'16]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2. A full version of our paper, containing all proofs, is available at https://arxiv.org/abs/2006.16632v2. Here we number key lemmas to match the numbering in the full version.

Abstract We study the parameterized complexity of the problem of counting graph homomorphisms with given partial injectivity constraints, i.e., inequalities between pairs of vertices, which subsumes counting of graph homomorphisms, subgraph counting and, more generally, counting of answers to equi-join queries with inequalities. Our main result presents an exhaustive complexity classification for the problem in fixed-parameter tractable and $$\#\mathsf {W[1]}$$ # W [ 1 ] -complete cases. The proof relies on the framework of linear combinations of homomorphisms as independently discovered by Chen and Mengel (PODS 16) and by Curticapean, Dell and Marx in the recent breakthrough result regarding the exact complexity of the subgraph counting problem (STOC 17). Moreover, we invoke Rota’s NBC-Theorem to obtain an explicit criterion for fixed-parameter tractability based on treewidth. The abstract classification theorem is then applied to the problem of counting locally injective graph homomorphisms from small pattern graphs to large target graphs. As a consequence, we are able to fully classify its parameterized complexity depending on the class of allowed pattern graphs.

We study the problem of computing the parity of the number of homomorphisms from an input graph $G$ to a fixed graph $H$. Faben and Jerrum [ Theory Comput., 11 (2015), pp. 35--57] introduced an explicit criterion on the graph $H$ and conjectured that, if satisfied, the problem is solvable in polynomial time and, otherwise, the problem is complete for the complexity class $\oplus{P}$ of parity problems. We verify their conjecture for all graphs $H$ that exclude the complete graph on four vertices as a minor. Further, we rule out the existence of a subexponential-time algorithm for the $\oplus{P}$-complete cases, assuming the randomized exponential time hypothesis. Our proofs introduce a novel method of deriving hardness from globally defined substructures of the fixed graph $H$. Using this, we subsume all prior progress toward resolving the conjecture (Faben and Jerrum [ Theory Comput., 11 (2015), pp. 35--57]; Göbel, Goldberg, and Richerby [ ACM Trans. Comput. Theory, 6 (2014), 17; ACM Trans. Comput. Theory, 8 (2016), 12]). As special cases, our machinery also yields a proof of the conjecture for graphs with maximum degree at most 3, as well as a full classification for the problem of counting list homomorphisms, modulo 2.

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.

Counting homomorphisms from a graph H into another graph G is a fundamental problem of (parameterized) counting complexity theory. In this work, we study the case where both graphs H and G stem from given classes of graphs: H ϵ and G ϵ . By this, we combine the structurally restricted version of this problem (where the class = ┬ is the set of all graphs), with the language-restricted version (where the class = ┬ is the set of all graphs). The structurally restricted version allows an exhaustive complexity classification for classes : Either we can count all homomorphisms in polynomial time (if the treewidth of is bounded), or the problem becomes #W[1]-hard [Dalmau, Jonsson, Th.Comp.Sci’04]. In contrast, in this work, we show that the combined view most likely does not admit such a complexity dichotomy. Our main result is a construction based on Kneser graphs that associates every problem P in #W[1] with two classes of graphs and such that the problem P is equivalent to the problem #Hom( → ) of counting homomorphisms from a graph in to a graph in . In view of Ladner's seminal work on the existence of NP-intermediate problems [J.ACM’75] and its adaptations to the parameterized setting, a classification of the class #W[1] in fixed-parameter tractable and #W[1]-complete cases is unlikely. Hence, obtaining a complete classification for the problem #Hom( → ) seems unlikely. Further, our proofs easily adapt to W[1] and the problem of deciding whether a homomorphism between graphs exists. In search of complexity dichotomies, we hence turn to special graph classes. Those classes include line graphs, claw-free graphs, perfect graphs, and combinations thereof, and F-colorable graphs for fixed graphs F. As a special case, we obtain an easy proof of the parameterized intractability result of the problem of counting k-matchings in bipartite graphs.

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 weak call-by-value $\lambda$-calculus as a model for computational complexity theory and establish the natural measures for time and space -- the number of beta-reductions and the size of the largest term in a computation -- as reasonable measures with respect to the invariance thesis of Slot and van Emde Boas [STOC~84]. More precisely, we show that, using those measures, Turing machines and the weak call-by-value $\lambda$-calculus can simulate each other within a polynomial overhead in time and a constant factor overhead in space for all computations that terminate in (encodings) of 'true' or 'false'. We consider this result as a solution to the long-standing open problem, explicitly posed by Accattoli [ENTCS~18], of whether the natural measures for time and space of the $\lambda$-calculus are reasonable, at least in case of weak call-by-value evaluation. Our proof relies on a hybrid of two simulation strategies of reductions in the weak call-by-value $\lambda$-calculus by Turing machines, both of which are insufficient if taken alone. The first strategy is the most naive one in the sense that a reduction sequence is simulated precisely as given by the reduction rules; in particular, all substitutions are executed immediately. This simulation runs within a constant overhead in space, but the overhead in time might be exponential. The second strategy is heap-based and relies on structure sharing, similar to existing compilers of eager functional languages. This strategy only has a polynomial overhead in time, but the space consumption might require an additional factor of $\log n$, which is essentially due to the size of the pointers required for this strategy. Our main contribution is the construction and verification of a space-aware interleaving of the two strategies, which is shown to yield both a constant overhead in space and a polynomial overhead in time.

Conjunctive queries select and are expected to return certain tuples from a relational database. We study the potentially easier problem of counting all selected tuples, rather than enumerating them. In particular, we are interested in the problem’s parameterized and data complexity, where the query is considered to be small or even fixed, and the database is considered to be large. We identify two structural parameters for conjunctive queries that capture their inherent complexity: The dominating star size and the linked matching number. If the dominating star size of a conjunctive query is large, then we show that counting solution tuples to the query is at least as hard as counting dominating sets, which yields a fine-grained complexity lower bound under the Strong Exponential Time Hypothesis (SETH) as well as a #W[2]-hardness result in parameterized complexity. Moreover, if the linked matching number of a conjunctive query is large, then we show that the structure of the query is so rich that arbitrary queries up to a certain size can be encoded into it; in the language of parameterized complexity, this essentially establishes a #A[2]-completeness result. Using ideas stemming from Lovász (1967), we lift complexity results from the class of conjunctive queries to arbitrary existential or universal formulas that might contain inequalities and negations on constraints over the free variables. As a consequence, we obtain a complexity classification that refines and generalizes previous results of Chen, Durand, and Mengel (ToCS 2015; ICDT 2015; PODS 2016) for conjunctive queries and of Curticapean and Marx (FOCS 2014) for the subgraph counting problem. Our proof also relies on graph minors, and we show a strengthening of the Excluded-Grid-Theorem which might be of independent interest: If the linked matching number (and thus the treewidth) is large, then not only can we find a large grid somewhere in the graph, but we can find a large grid whose diagonal has disjoint paths leading into an assumed node-well-linked set.

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.

Jaeger et al. (Math Proc Camb Philos Soc 108(1):35–53, 1990) proved a dichotomy for the complexity of evaluating the Tutte polynomial at fixed points: the evaluation is #P-hard almost everywhere, and the remaining points admit polynomial-time algorithms. Dell, Husfeldt, and Wahlén (in: ICALP 2010, vol. 6198, pp. 426–437, Springer, Berlin, Heidelberg, 2010) and Husfeldt and Taslaman (in: IPEC 2010, vol. 6478, pp. 192–203, Springer, Berlin, Heidelberg, 2010) in combination with the results of Curticapean (in: ICALP 2015, pp. 380–392, Springer, 2015), extended the #P-hardness results to tight lower bounds under the counting exponential time hypothesis #ETH, with the exception of the line $$y=1$$ , which was left open. We complete the dichotomy theorem for the Tutte polynomial under #ETH by proving that the number of all acyclic subgraphs of a given n-vertex graph cannot be determined in time unless #ETH fails. Another dichotomy theorem we strengthen is the one of Creignou and Hermann (Inf Comput 125(1):1–12, 1996) for counting the number of satisfying assignments to a constraint satisfaction problem instance over the Boolean domain. We prove that the #P-hard cases cannot be solved in time unless #ETH fails. The main ingredient is to prove that the number of independent sets in bipartite graphs with n vertices cannot be computed in time unless #ETH fails. In order to prove our results, we use the block interpolation idea by Curticapean and transfer it to systems of linear equations that might not directly correspond to interpolation.

We consider the #W[1]-hard problem of counting all matchings with exactly k edges in a given input graph G; we prove that it remains #W[1]-hard on graphs G that are line graphs or bipartite graphs with degree 2 on one side. In our proofs, we use that k-matchings in line graphs can be equivalently viewed as edge-injective homomorphisms from the disjoint union of k length-2 paths into (arbitrary) host graphs. Here, a homomorphism from H to G is edge-injective if it maps any two distinct edges of H to distinct edges in G. We show that edge-injective homomorphisms from a pattern graph H can be counted in polynomial time if H has bounded vertex-cover number after removing isolated edges. For hereditary classes $\mathcal {H}$ of pattern graphs, we complement this result: If the graphs in $\mathcal {H}$ have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from $\mathcal {H}$ is #W[1]-hard. Our proofs rely on an edge-colored variant of Holant problems and a delicate interpolation argument; both may be of independent interest.

We present a framework for the complexity classification of parameterized counting problems that can be formulated as the summation over the numbers of homomorphisms from small pattern graphs H_1,...,H_l to a big host graph G with the restriction that the coefficients correspond to evaluations of the Möbius function over the lattice of a graphic matroid. This generalizes the idea of Curticapean, Dell and Marx [STOC 17] who used a result of Lovász stating that the number of subgraph embeddings from a graph H to a graph G can be expressed as such a sum over the lattice of partitions of H. In the first step we introduce what we call graphically restricted homomorphisms that, inter alia, generalize subgraph embeddings as well as locally injective homomorphisms. We provide a complete parameterized complexity dichotomy for counting such homomorphisms, that is, we identify classes of patterns for which the problem is fixed-parameter tractable (FPT), including an algorithm, and prove that all other pattern classes lead to #W[1]-hard problems. The main ingredients of the proof are the complexity classification of linear combinations of homomorphisms due to Curticapean, Dell and Marx [STOC 17] as well as a corollary of Rota's NBC Theorem which states that the sign of the Möbius function over a geometric lattice only depends on the rank of its arguments. We apply the general theorem to the problem of counting locally injective homomorphisms from small pattern graphs to big host graphs yielding a concrete dichotomy criterion. It turns out that - in contrast to subgraph embeddings - counting locally injective homomorphisms has "real" FPT cases, that is, cases that are fixed-parameter tractable but not polynomial time solvable under standard complexity assumptions. To prove this we show in an intermediate step that the subgraph counting problem remains #P-hard when both the pattern and the host graphs are restricted to be trees. We then investigate the more general problem of counting homomorphisms that are injective in the r-neighborhood of every vertex. As those are graphically restricted as well, they can also easily be classified via the general theorem. Finally we show that the dichotomy for counting graphically restricted homomorphisms readily extends to so-called linear combinations.