The complexity of bilinear maps (equivalently, of 3-mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and tensor rank coincide asymptotically for 3-mode tensors, this correspondence breaks down for d ≥ 4 modes. As a result, the complexity of d-mode tensors for larger fixed d remains poorly understood, despite its relevance, e.g., in fine-grained complexity. Our paper explores this intermediate regime. First, we give a "graph-theoretic" proof of Strassen’s 2ω/3 bound on the asymptotic rank exponent of 3-mode tensors. Our proof directly generalizes to an upper bound of (d-1)ω/3 for d-mode tensors. Using refined techniques available only for d ≥ 4 modes, we improve this bound beyond the current state of the art for ω. We also obtain a bound of d/2+1 on the asymptotic exponent of circuit complexity of generic d-mode tensors and optimized bounds for d ∈ {4,5}. To the best of our knowledge, asymptotic circuit complexity (rather than rank) of tensors has not been studied before. To obtain a robust theory, we first ask whether low complexity of T and U imply low complexity of their Kronecker product T ⊗ U. While this crucially holds for rank (and thus for circuit complexity in 3 modes), we show that assumptions from fine-grained complexity rule out such a submultiplicativity for the circuit complexity of tensors with many modes. In particular, assuming the Hyperclique Conjecture, this failure occurs already for d = 8 modes. Nevertheless, we can salvage a restricted notion of submultiplicativity. From a technical perspective, our proofs heavily make use of the graph tensors T_H, as employed by Christandl and Zuiddam (Comput. Complexity 28 (2019) 27-56) and Christandl, Vrana and Zuiddam (Comput. Complexity 28 (2019) 57-111), whose modes correspond to the vertices of undirected graphs H. We make the simple but conceptually crucial observation that Kronecker products T_G ⊗ T_H are isomorphic to T_{G+H}, and that G and H may also be fractional graphs. By asymptotically converting generic tensors to specific graph tensors, we can use nontrivial results from algorithmic graph theory to study the rank and complexity of d-mode tensors for fixed d.

A central result by Marx [ToC '10] constructs k-vertex graphs H of maximum degree 3 such that n^o(k/log k) time algorithms for detecting colorful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH. Our first contribution is a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity γ(H), and show that detecting colorful H-subgraphs in time n^o(γ(H)) refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain k-vertex graphs of maximum degree 3 and linkage capacity Ω(k/log k), avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph H of treewidth t has linkage capacity Ω(t/log t), thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof. Additionally, we obtain new tight lower bounds on the complexity of subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all k-vertex graphs of polynomial average degree Ω(k^β) for β > 0 have linkage capacity Θ(k), which implies tight lower bounds for finding such patterns H. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property Φ, improving bounds from, e.g., [Roth et al., FOCS 2020].

In the parameterized problem #IndSub(Φ) for fixed graph properties Φ, given as input a graph G and an integer k, the task is to compute the number of induced k-vertex subgraphs satisfying Φ. Dörfler et al. [Algorithmica 2022] and Roth et al. [SICOMP 2024] conjectured that #IndSub(Φ) is #W[1]-hard for all non-meager properties Φ, i.e., properties that are nontrivial for infinitely many k. This conjecture has been confirmed for several restricted types of properties, including all hereditary properties [STOC 2022] and all edge-monotone properties [STOC 2024]. We refute this conjecture by showing that induced k-vertex graphs that are scorpions can be counted in time O(n⁴) for all k. Scorpions were introduced more than 50 years ago in the context of the evasiveness conjecture. A simple variant of this construction results in graph properties that achieve arbitrary intermediate complexity assuming ETH. Moreover, we formulate an updated conjecture on the complexity of #IndSub(Φ) that correctly captures the complexity status of scorpions and related constructions.

For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Progr. Math. 1994] and the three-way partitioning problem. We show that under the asymptotic rank conjecture, the chromatic number of an n-vertex graph can be computed deterministically in O (1.99982n ) time, thus giving a conditional answer to a question of Zamir [ICALP 2021], and questioning the optimality of the 2n poly(n ) time algorithm for chromatic number by Björklund, Husfeldt, and Koivisto [SICOMP 2009].

For a fixed graph property Φ and integer k ≥ 1, consider the problem of counting the induced k-vertex subgraphs satisfying Φ in an input graph G. This problem can be solved by brute-force in time O (nk ). Under ETH, we prove several lower bounds on the optimal exponent in this running time.

A central result by Marx [ToC '10] constructs k-vertex graphs H of maximum degree 3 such that n^o(k/log k) time algorithms for detecting colorful H-subgraphs would refute the Exponential-Time Hypothesis (ETH). This result is widely used to obtain almost-tight conditional lower bounds for parameterized problems under ETH. Our first contribution is a new and fully self-contained proof of this result that further simplifies a recent work by Karthik et al. [SOSA 2024]. In our proof, we introduce a novel graph parameter of independent interest, the linkage capacity γ(H), and show that detecting colorful H-subgraphs in time n^o(γ(H)) refutes ETH. Then, we use a simple construction of communication networks credited to Beneš to obtain k-vertex graphs of maximum degree 3 and linkage capacity Ω(k/log k), avoiding arguments involving expander graphs, which were required in previous papers. We also show that every graph H of treewidth t has linkage capacity Ω(t/log t), thus recovering a stronger result shown by Marx [ToC '10] with a simplified proof. Additionally, we obtain new tight lower bounds on the complexity of subgraph detection for certain types of patterns by analyzing their linkage capacity: We prove that almost all k-vertex graphs of polynomial average degree Ω(k^β) for β > 0 have linkage capacity Θ(k), which implies tight lower bounds for finding such patterns H. As an application of these results, we also obtain tight lower bounds for counting small induced subgraphs having a fixed property Φ, improving bounds from, e.g., [Roth et al., FOCS 2020].

A homomorphism between graphs H and G, possibly with vertex-colors, is a function f : V(ℋ) → V(G) that preserves colors and edges. Many interesting graph parameters are finite linear combinations p(·) = Ση αH hom(ℋ, ·) of homomorphism counts from fixed pattern graphs H; this includes (induced) subgraph counts for fixed patterns. Interpreting graph parameters as linear combinations of homomorphism counts has proven to be useful in understanding their computational complexity, as it is known that such linear combinations are as hard to evaluate as their hardest terms, whose complexity in turn is governed by the treewidth of the pattern graph. More formally, given oracle access to a linear combination of homomorphism counts p as above and a graph S with coefficient αs ≠ 0, it is possible to compute hom(S, G) for any n-vertex input graph G in 2|E(S)|poly(s, n) time, where s is the maximum size of graphs in the defining linear combination of p. This reduction runs in polynomial time when p and S are fixed or small in comparison to G; this is the relevant setting in several results based on this reduction.

We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-logarithmic space algorithms for the determinant. Our new explanation avoids linear-algebraic arguments and instead exploits a classical connection between subgraph and homomorphism counts.

A polynomial P ∈ 𝔽[x_1,…,x_n] is said to be symmetric if it is invariant under any permutation of its input variables. The study of symmetric polynomials is a classical topic in mathematics, specifically in algebraic combinatorics and representation theory. More recently, they have been studied in several works in computer science, especially in algebraic complexity theory. In this paper, we prove the computational hardness of one of the most basic kinds of symmetric polynomials: the monomial symmetric polynomials, which are obtained by summing all distinct permutations of a single monomial. This family of symmetric functions is a natural basis for the space of symmetric polynomials (over any field), and generalizes many well-studied families such as the elementary symmetric polynomials and the power-sum symmetric polynomials. We show that certain families of monomial symmetric polynomials are VNP-complete with respect to oracle reductions. This stands in stark contrast to the case of elementary and power symmetric polynomials, both of which have constant-depth circuits of polynomial size.

We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of $k$-matchings can be determined in polynomial time by a simple reduction to the determinant. We generalize this to an $n^{f(t,s)}$-time algorithm to compute modulo $2^t$ the number of subgraph occurrences of patterns that are $s$ vertices away from being matchings. This shows that the known polynomial-time cases of subgraph detection (Jansen and Marx, SODA 2015) carry over into the setting of counting modulo $2^t$. Complementing our algorithm, we also give a simple and self-contained proof that counting $k$-matchings modulo odd integers $q$ is Mod_q-W[1]-complete and prove that counting $k$-paths modulo $2$ is Parity-W[1]-complete, answering an open question by Björklund, Dell, and Husfeldt (ICALP 2015).

Given an integer n ≥ 1 and an irreducible character χλ of Sn for some partition λ of n, the immanant immλ:ℂn× n→ℂ maps matrices A∈ℂn× n to immλ(A)=∑π∈ Snχλ(π)∏i=1nAi,π(i). Important special cases include the determinant and permanent, which are obtained from the sign and trivial character, respectively.

In this work, we initiate the study of the Min-Ones d-SAT problem in the parameterized streaming model. An instance of the problem consists of a d-CNF formula F and an integer k, and the objective is to determine if F has a satisfying assignment which sets at most k variables to 1. In the parameterized streaming model, input is provided as a stream, just as in the usual streaming model. A key difference is that the bound on the read-write memory available to the algorithm is O(f(k) log n) (f: N -> N, a computable function) as opposed to the O(log n) bound of the usual streaming model. The other important difference is that the number of passes the algorithm makes over its input must be a (preferably small) function of k. We design a (k + 1)-pass parameterized streaming algorithm that solves Min-Ones d-SAT (d >= 2) using space O((kd^(ck) + k^d)log n) (c > 0, a constant) and a (d + 1)^k-pass algorithm that uses space O(k log n). We also design a streaming kernelization for Min-Ones 2-SAT that makes (k + 2) passes and uses space O(k^6 log n) to produce a kernel with O(k^6) clauses. To complement these positive results, we show that any k-pass algorithm for or Min-Ones d-SAT (d >= 2) requires space Omega(max{n^(1/k) / 2^k, log(n / k)}) on instances (F, k). This is achieved via a reduction from the streaming problem POT Pointer Chasing (Guha and McGregor [ICALP 2008]), which might be of independent interest. Given this, our (k + 1)-pass parameterized streaming algorithm is the best possible, inasmuch as the number of passes is concerned. In contrast to the results of Fafianie and Kratsch [MFCS 2014] and Chitnis et al. [SODA 2015], who independently showed that there are 1-pass parameterized streaming algorithms for Vertex Cover (a restriction of Min-Ones 2-SAT), we show using lower bounds from Communication Complexity that for any d >= 1, a 1-pass streaming algorithm for Min-Ones d-SAT requires space Omega(n). This excludes the possibility of a 1-pass parameterized streaming algorithm for the problem. Additionally, we show that any p-pass algorithm for the problem requires space Omega(n/p).

The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexity class $$\mathsf {\#RH}\Pi _1$$ . It is believed that #BIS does not have an efficient approximation algorithm but also that it is not NP-hard. We study the robustness of the intermediate complexity of #BIS by considering variants of the problem parameterised by the size of the independent set. We map the complexity landscape for three problems, with respect to exact computation and approximation and with respect to conventional and parameterised complexity. The three problems are counting independent sets of a given size, counting independent sets with a given number of vertices in one vertex class and counting maximum independent sets amongst those with a given number of vertices in one vertex class. Among other things, we show that all of these problems are NP-hard to approximate within any polynomial ratio. (This is surprising because the corresponding problems without the size parameter are complete in $$\mathsf {\#RH}\Pi _1$$ , and hence are not believed to be NP-hard.) We also show that the first problem is #W[1]-hard to solve exactly but admits an FPTRAS, whereas the other two are W[1]-hard to approximate even within any polynomial ratio. Finally, we show that, when restricted to graphs of bounded degree, all three problems have efficient exact fixed-parameter algorithms.

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 consider the following natural “above-guarantee” parameterization of the classical Longest Path problem: For given vertices $s$ and $t$ of a graph $G$ and integer $k$, the Longest Detour problem asks for an $(s,t)$-path in $G$ that is at least $k$ longer than a shortest $(s,t)$-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time $2^{O(k)} \cdot n^{O(1)}$. Up to the base of the exponential, this running time matches the best algorithms for finding a path of length at least $k$. Furthermore, we study the related Exact Detour problem, which asks whether a graph $G$ contains an $(s,t)$-path that is exactly $k$ longer than a shortest $(s,t)$-path. For this problem, we obtain randomized algorithms with running times $2.746^k\cdot n^{O(1)}$ (for undirected graphs) and $4^k\cdot n^{O(1)}$ (for directed graphs) and a deterministic algorithm with running time $6.745^{k}\cdot n^{O(1)}$, showing that this problem is fixed-parameter tractable as well.

This survey is an invitation to parameterized counting problems for readers with a background in parameterized algorithms and complexity. After an introduction to the peculiarities of counting complexity, we survey the parameterized approach to counting problems, with a focus on two topics of recent interest: Counting small patterns in large graphs, and counting perfect matchings and Hamiltonian cycles in well-structured graphs. While this survey presupposes familiarity with parameterized algorithms and complexity, we aim at explaining all relevant notions from counting complexity in a self-contained way.

For even k ∊ ℕ, the matchings connectivity matrix Mk is a binary matrix indexed by perfect matchings on k vertices; the entry at (M, M‘) is 1 iff M ∪ M‘ forms a single cycle. Cygan et al. (STOC 2013) showed that the rank of Mk over ℤ is and used this to give an time algorithm for counting Hamiltonian cycles modulo 2 on graphs of pathwidth pw, carrying over to the decision problem via witness isolation. The same authors complemented their algorithm by an essentially tight lower bound under the Strong Exponential Time Hypothesis (SETH). This bound crucially relied on a large permutation submatrix within Mk, which enabled a “pattern propagation” commonly used in previous related lower bounds, as initiated by Lokshtanov et al. (SODA 2011). We present a new technique for a similar “pattern propagation” when only a black-box lower bound on the asymptotic rank of Mk is given; no stronger structural insights such as the existence of large permutation submatrices in Mk are needed. Given appropriate rank bounds, our technique yields lower bounds for counting Hamiltonian cycles (also modulo fixed primes p) parameterized by pathwidth. To apply this technique, we prove that the rank of Mk over the rationals is 4k/poly(k), using the representation theory of the symmetric group and various insights from algebraic combinatorics. We also show that the rank of Mk over ℤp is Ω(1.57k) for any prime p ≠ 2. Combining our rank bounds with the new pattern propagation technique, we show that Hamiltonian cycles cannot be counted in time O*((6 – ε)pw) for any ε > 0 unless SETH fails. This bound is tight due to a O*(6pw) time algorithm by Bodlaender et al. (ICALP 2013). Under SETH, we also obtain that Hamiltonian cycles cannot be counted modulo primes p ≠ 2 in time O*(3.57pw), indicating that the modulus can affect the complexity in intricate ways.

We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem Longest Detour asks for an (s,t)-path in G that is at least k longer than a shortest (s,t)-path. Using insights into structural graph theory, we prove that Longest Detour is fixed-parameter tractable (FPT) on undirected graphs and actually even admits a single-exponential algorithm, that is, one of running time exp(O(k)) poly(n). This matches (up to the base of the exponential) the best algorithms for finding a path of length at least k. Furthermore, we study the related problem Exact Detour that asks whether a graph G contains an (s,t)-path that is exactly k longer than a shortest (s,t)-path. For this problem, we obtain a randomized algorithm with running time about 2.746^k, and a deterministic algorithm with running time about 6.745^k, showing that this problem is FPT as well. Our algorithms for Exact Detour apply to both undirected and directed graphs.

We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many interesting quantities have this form, including, for fixed graphs H, the number of H-copies (induced or not) in an input graph G, and the number of homomorphisms from H to G.

We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomial-time algorithm [Kasteleyn 1961], the problem of counting all matchings (possibly containing unmatched vertices, also known as defects) is known to be #P-complete on planar graphs [Jerrum 1987]. To interpolate between matchings and perfect matchings, we study the parameterized problem of counting matchings with k unmatched vertices in a planar graph G, on input G and k. This setting has a natural interpretation in statistical physics, and it is a special case of counting perfect matchings in k-apex graphs (graphs that become planar after removing k vertices). Starting from a recent #W[1]-hardness proof for counting perfect matchings on k-apex graphs [Curtican and Xia 2015], we obtain: - Counting matchings with k unmatched vertices in planar graphs is #W[1]-hard. - In contrast, given a plane graph G with s distinguished faces, there is an O(2^s n^3) time algorithm for counting those matchings with k unmatched vertices such that all unmatched vertices lie on the distinguished faces. This implies an f(k,s)n^O(1) time algorithm for counting perfect matchings in k-apex graphs whose apex neighborhood is covered by s faces.

Given an edge-weighted graph G, let PerfMatch(G) denote the weighted sum over all perfect matchings M in G, weighting each matching M by the product of weights of edges in M. If G is unweighted, this plainly counts the perfect matchings of G. In this paper, we introduce parity separation, a new method for reducing PerfMatch to unweighted instances: For graphs G with edge-weights 1 and -1, we construct two unweighted graphs G1 and G2 such that PerfMatch(G) = PerfMatch(G1) - PerfMatch(G2). This yields a novel weight removal technique for counting perfect matchings, in addition to those known from classical #P-hardness proofs. Our technique is based upon the Holant framework and matchgates. We derive the following applications: Firstly, an alternative #P-completeness proof for counting unweighted perfect matchings. Secondly, C=P-completeness for deciding whether two given unweighted graphs have the same number of perfect matchings. To the best of our knowledge, this is the first C=P-completeness result for the “equality-testing version” of any natural counting problem that is not already #P-hard under parsimonious reductions. Thirdly, an alternative tight lower bound for counting unweighted perfect matchings under the counting exponential-time hypothesis #ETH.

By now, we have a good understanding of how NP-hard problems become easier on graphs of bounded treewidth and bounded cliquewidth: for various problems, matching upper bounds and conditional lower bounds describe exactly how the running time has to depend on treewidth or cliquewidth. In particular, Fomin et al. (2009, 2010) have shown a significant difference between these two parameters: assuming the Exponential-Time Hypothesis (ETH), the optimal algorithms for problems such as Max Cut and Edge Dominating Set have running time 2O(t) nO(1) when parameterized by treewidth, but nO(t) when parameterized by cliquewidth. In this paper, we show that a similar phenomenon occurs also for counting problems. Specifically, we prove that, assuming the counting version of the Strong Exponential-Time Hypothesis (#SETH), the problem of counting perfect matchings has no (2 – ∊)knO(1) time algorithm for any ∊ > 0 on graphs of treewidth k (but it is known to be solvable in time 2knO(1) if a tree decomposition of width k is given), and has no O(n(1–∊)k) time algorithm for any ∊ > 0 on graphs of cliquewidth k (but it can be solved in time O(nk+1) if a k-expression is given). A celebrated result of Fisher, Kasteleyn, and Temperley from the 1960s shows that counting perfect matchings in planar graphs is polynomial-time solvable. This was later extended by Gallucio and Loebl (1999), Tesler (2000) and Regge and Zechina (2000) who gave 4k · nO(1) time algorithms for graphs of genus k. We show that the dependence on the genus k has to be exponential: assuming #ETH, the counting version of ETH, there is no 2o(k) · nO(1) time algorithm for the problem on graphs of genus k.

We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph C. These generalize the well-known tractable planar case, and they include the genus of C, its apex number (the minimum number of vertices whose removal renders C planar), and its Hadwiger number (the size of a largest clique minor). To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain nonexisting gadgets F as linear combinations of L = O(1) existing gadgets. If a graph C features k occurrences of F, we can then reduce C to tkgraphs that feature only existing gadgets, thus enabling parameterized reductions. As applications of this technique, we simplify known 4gnO(1)time algorithms for PerfMatch on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its ⊕W[1]-hardness under the Hadwiger number. Additionally, we rule out no(k/ log k)time algorithms under the counting exponential-time hypothesis #ETH. Finally, we use combined matchgates to prove $W[1]-hardness of evaluating the permanent modulo 2k, complementing an O(n4k-3) time algorithm by Valiant and answering an open question of Bjϋrklund. We also obtain a lower bound of nΩ(k/ log k)under the parity version $ETH of the exponential-time hypothesis.

For a class C of graphs, #Sub(C) is the counting problem that, given a graph H from C and an arbitrary graph G, asks for the number of subgraphs of G isomorphic to H. It is known that if C has bounded vertex-cover number (equivalently, the size of the maximum matching in C is bounded), then #Sub(C) is polynomial-time solvable. We complement this result with a corresponding lower bound: if C is any recursively enumerable class of graphs with unbounded vertexcover number, then #Sub(C) is #W[1]-hard parameterized by the size of H and hence not polynomial-time solvable and not even fixed-parameter tractable, unless FPT is equal to #W[1]. As a first step of the proof, we show that counting kmatchings in bipartite graphs is #W[1]-hard. Recently, Curticapean [ICALP 2013] proved the #W[1]-hardness of counting k-matchings in general graphs; our result strengthens this statement to bipartite graphs with a considerably simpler proof and even shows that, assuming the Exponential Time Hypothesis (ETH), there is no f(k)*n^o(k/log(k)) time algorithm for counting k-matchings in bipartite graphs for any computable function f. As a consequence, we obtain an independent and somewhat simpler proof of the classical result of Flum and Grohe [SICOMP 2004] stating that counting paths of length k is #W[1]-hard, as well as a similar almost-tight ETH-based lower bound on the exponent.

Let P be a set of $n$ points in the plane. A crossing-free structure on P is a straight-edge planar graph with vertex set in P. Examples of crossing-free structures include triangulations of P, and spanning cycles of P, also known as polygonalizations of P, among others. There has been a large amount of research trying to bound the number of such structures. In particular, bounding the number of triangulations spanned by P has received considerable attention. It is currently known that every set of n points has at most O(30n) and at least Ω(2.43n) triangulations. However, much less is known about the algorithmic problem of counting crossing-free structures of a given set P. For example, no algorithm for counting triangulations is known that, on all instances, performs faster than enumerating all triangulations. In this paper we develop a general technique for computing the number of crossing-free structures of an input set P. We apply the technique to obtain algorithms for computing the number of triangulations and spanning cycles of P. The running time of our algorithms is upper bounded by nO(k), where k is the number of onion layers of P. In particular, we show that our algorithm for counting triangulations is not slower than O(3.1414n). Given that there are several well-studied configurations of points with at least Ω(3.464n) triangulations, and some even with Ω(8n) triangulations, our algorithm is the first to asymptotically outperform any enumeration algorithm for such instances. In fact, it is widely believed that any set of n points must have at least Ω(3.464n) triangulations. If this is true, then our algorithm is strictly sub-linear in the number of triangulations counted. We also show that our techniques are general enough to solve the restricted triangulation counting problem, which we prove to be W[2]-hard in the parameter k. This implies a "no free lunch" result: In order to be fixed-parameter tractable, our general algorithm must rely on additional properties that are specific to the considered class of structures.