Structural Tractability of Counting of Solutions to Conjunctive Queries

Abstract

We explore the complexity of counting solutions to conjunctive queries, a basic class of queries from database theory. We introduce a parameter, called the quantified star size of a query ϕ, which measures how the free variables are spread in ϕ. As usual in database theory, we associate a hypergraph to a query ϕ. We show that for classes of queries for which these associated hypergraphs admit good decompositions, e.g., bounded width generalized hypertree decompositions, bounded quantified star size exactly characterizes the subclasses of hypergraphs for which counting the number of solutions is tractable. In the case of bounded arity, this allows us to fully characterize the classes of hypergraphs for which counting the solutions is tractable. Finally, we also analyze the complexity of computing the quantified star size of a conjunctive query.

1 Introduction

Conjunctive queries are a fundamental class of queries from database theory. Equivalent to Select-Project-Join queries, they are the most basic class of database queries and at the same time play an important role in practice. Furthermore, as Kolaitis and Vardi [26] showed, conjunctive queries are intimitely connected to constraint satisfaction problems, a central area from artificial intelligence. These features make conjunctive queries the best-studied type of database queries.

A CQ-instance $({\mathcal {A}}, \phi )$ consists of a query ϕ, which is a logical first-order {∃, ∧}-formula, also called primitive positive formula, and a finite structure (i.e., database) 𝓐. The query result is

$$\phi({\mathcal{A}}):=\{\mathrm{\mathbf{a}} \mid ({\mathcal{A}}, \mathrm{\mathbf{a}})\models \phi(\mathrm{x})\}, $$

that is, the set of assignments that make the query ϕ true.

The focus of most research on conjunctive queries has been the Boolean conjunctive query problem (short CQ) which is, given an instance, to decide if the query result of the instance is empty or not. This problem is well known to be NP-complete and thus the main interest of study has been to identify tractable subclasses, so-called “islands of tractability”, where CQ is tractable, i.e., can be solved in polynomial time.

One main direction in finding tractable classes of CQ-instances has been imposing structural restrictions on the queries—or often more exactly on the hypergraph associated to it—while the database is assumed to be arbitrary. In a seminal paper Yannakakis [33] proved that ACQ, the restriction of CQ to acyclic queries, is tractable. The main idea behind other structural restrictions is to extend this result by generalizing it to “nearly acyclic” queries. This has lead to many different decompositions for graphs and hypergraphs and associated width measures (see e.g., [10, 18, 30]). The common approach for these decompositions is to group together vertices or edges (of the graphs or hypergraphs) into clusters of some fixed constant size and to arrange these clusters into a tree satisfying certain conditions. The resulting width measures are often sought to have two desirable properties:

• For every k the class of queries of width k should be tractable, i.e., CQ should be solvable in polynomial time.

• Given an instance, it should be possible to decide if there is a decomposition of width k and construct one if it exists.

While decomposition techniques without the first property do not make any sense in the context of conjunctive queries, the second property is sometimes relaxed. For some decomposition techniques one does not actually need the decomposition to solve CQ [8], a promise of the existence is enough. For other decompositions one only knows approximation algorithms that construct decompositions of a width that is near the optimal width, which is enough to guarantee tractability of CQ [2, 28].

More recently there has also been interest in enumerating all solutions to conjunctive queries and in the corresponding counting question #CQ which is, given a CQ-instance, to determine the size of the query result. For enumeration of the query answers it turns out that the picture is less clear than for decision [3, 6, 21]. Also the situation for counting is more subtle: For quantifier free queries—which correspond to queries without projections in the database perspective—most commonly considered structural restrictions yield tractable counting problems (see, e.g., [31]). While this is nice, it is not fully satisfying, because quantifiers—which correspond to projections in database theory—are very natural and essential in database queries. While introducing projections does not make any difference for the complexity of CQ, the situation for #CQ is dramatically different. In [31] it is shown that even one single existentially quantified variable is enough to make counting answers to CQ-instances #P-hard, even when the associated hypergraph of the query is a tree (which implies width 1 for all commonly considered decomposition techniques). It follows that the decomposition techniques used for CQ are not enough to guarantee tractability for counting.

In a previous paper [15] the authors of this paper have proposed a way out of this dilemma for counting by introducing a parameter called quantified star size for acyclic conjunctive queries. This parameter measures how the free variables are spread in the query. We associated to a query ϕ(x) the list x of free variables, thus extending the hypergraph 𝓗 = (V, E) associated to ϕ(x) with a set S ⊆ V. Then the quantified star size is the size of a maximum independent set consisting of vertices from the set S in some specified subhypergraphs of 𝓗. It turns out that, under a widely believed assumption from parameterized complexity, this measure precisely characterizes the tractable subclasses of acyclic conjunctive queries.

1.1 Overview of the Results

1.1.1 Counting Solutions to Queries

In this paper we extend the results of [15] from acyclic queries to classes of queries defined by commonly considered decomposition techniques. To do so we generalize the notion of quantified star size from acyclic queries to general conjunctive queries. We show that every class of conjunctive queries that allows efficient counting must be of bounded quantified star size—again under the same assumption from parameterized complexity. We then go on showing that for all decomposition techniques for conjunctive queries commonly considered in the literature, combining them with bounded quantified star size leads to tractable counting problems. The key feature that makes this result work is the organization of atoms and variables into a tree of clusters that is prominent in all decomposition methods for CQ known so far. Combining the results we get an exact characterization of the subclasses of CQ-instances that allow tractable counting for commonly considered classes defined by decomposition techniques. Let us illustrate these results for the example of generalized hypertree decomposition [18], which is one of the most general decomposition methods and one of the most studied too [18, 20, 30]. We have that, under the assumption that FPT ≠ #W[1], for any (recursively enumerable) class ${\mathcal {C}}$ of hypergraphs of bounded generalized hypertreewidth the following statements are equivalent:

• #CQ for instances in ${\mathcal {C}}$ can be solved in polynomial time

• ${\mathcal {C}}$ is of bounded quantified star size.

In our considerations, the arity of atoms of queries is not a priori bounded. In this setting, there is no known ultimate measure resulting from a decomposition method that fully characterizes tractability even for the decision problem CQ. This explains why our characterizations are stated for each decomposition method.

For bounded arity however, the situation is different. It is known that being of bounded treewidth completely characterizes tractability for decision [22, 24] and counting [12] for quantifier free instances. Combining [22, 24] and our results from above we derive a complete characterization of tractability for #CQ in terms of tree width and quantified star size of the underlying hypergraph for the bounded arity case.

Note that our results are for counting with set semantics, i.e., we count each solution only once. Counting for bag semantics in which multiple occurences of identical tuples are counted has already been essentially solved in [31].

1.1.2 Discovering Quantified Star Size

To exploit tractability results of the above kind it is helpful if the membership in a tractable class can be decided efficiently, i.e., in our case if computing the quantified star size of an instance is tractable. Therefore, we consider this “discovery problem” of determining the quantified star size of queries in the second part of the paper.

In [15] it is shown that quantified star size of acyclic conjunctive queries can be determined in polynomial time.

We show that computing the quantified star size of an instance is equivalent to computing maximum independent sets in hypergraphs. Consequently, we cannot expect a polynomial time algorithm for computing the quantified star size of general CQ-instances. Fortunately, it turns out that for queries ϕ of generalized hypertree width k and thus for all more restrictive decomposition techniques like hingetree width (see [10]) or treewidth, there is an algorithm that computes in time |ϕ|^O(k) the quantified star size of ϕ. We show that this is in a sense optimal, because computing the quantified star size of a given query ϕ is W[1]-hard parameterized by the generalized hypertree width of ϕ. Thus, under the standard assumption FPT ≠ W[1], there is no fixed-parameter algorithm for this problem.

Still, if we parameterize the computation of quantified star size by more restrictive width measures, computing the quantified star size of conjunctive queries in some cases becomes fixed-parameter tractable. We prove that this is the case queries if we parameterize by hingetree width. Because of the connection between quantified star size and maximum independent set, this result provides a new parameter of hypergraphs for which computing maximum independent sets is fixed-parameter tractable. Note that the W[1]-hardness result from above shows that fixed-parameter tractability of computing maximum independent sets is unlikely to hold for other hypergraph decomposition techniques.

We then turn our attention to the approximation of quantified star size. We show that there is a polynomial time algorithm that, given a query ϕ and a decomposition of ϕ of width k, computes in time independent of k a k-approximation of the quantified star size of ϕ.

Summing these results up, quantified star size does not only imply tractable counting if combined with well known decomposition techniques, but in case the decomposition is given or can be efficiently computed (treewidth, hingetree width) or approximated (generalized hypertreewidth), then computing quantified star size is itself tractable.

We show that this is in a sense optimal, because under the assumption FPT ≠ W[1] there is no efficient (fixed paramater tractable in k) algorithm computing the quantified star size for queries parameterized by generalized hypertree width.

Finally, we investigate the problem of counting solution and computing quantified star size for queries of bounded fractional hypertree width [23, 28]. This decomposition method is of a somewhat different nature than the ones studied before so we treat it individually. We again prove that counting is tractable in this setting and that the discovery problem can be decided in $O(n^{k^{O(1)}})$, i.e., with a slightly bigger dependency in k than before.

2 Preliminaries

In this section, we introduce the basic definitions and the notation we will use throughout the paper. We start off with a formal definition of conjunctive queries, introduce some notions from parameterized complexity and then survey the graph and hypergraph decompositions we will consider.

2.1 Conjunctive Queries

We give a brief introduction to conjunctive queries. More on the subject and, in general, on database theory and finite model theory can be found in [1, 27]

A relational vocabulary is a set of relation symbols $\tau :=\{{\mathcal {R}}_{1}, {\mathcal {R}}_{2}, \ldots , {\mathcal {R}}_{\ell }\}$ where each ${\mathcal {R}}_{i}$ has an arity r _i which we denote by ${\text {arity}({\mathcal {R}_{i}})}$. A finite (relational) structure 𝓐 over τ, a τ-structure for short, is a tuple $\left (A, {\mathcal {R}}_{1}^{{\mathcal {A}}}, \ldots , {\mathcal {R}}_{\ell }^{{\mathcal {A}}}\right )$ where A is a finite set called the domain of 𝓐 and ${\mathcal {R}}_{i}^{{\mathcal {A}}} \subseteq A^{r_{i}}$ is a relation of arity r _i called the interpretation of ${\mathcal {R}}_{i}$.

We denote structures by calligraphic letters, e.g., ${\mathcal {A}}, {\mathcal {B}}, \ldots$. For the corresponding domains we use the corresponding roman letters, i.e., A is the domain of 𝓐, B the domain of ℬ and so on.

Let ${\mathcal {R}}\in \tau$ with $\text {arity}({\mathcal {R}})=r$ and $\bar {z}$ be a sequence z ₁, … , z _r of (not necessarily distinct) variables. Then, the expression ${\mathcal {R}}(z_{1}, \ldots , z_{r})$ (short ${\mathcal {R}}(\bar {z})$) is called an atomic formula or atom. The scope $\textsf {var}({\mathcal {R}}(\bar {z}))$ of this atom is defined as the set of variables appearing in (z ₁, … , z _r ).

A quantifier free conjunctive query ϕ over a vocabulary τ is a logical formula of the form

$$\phi= {\mathcal{R}}_{i_{1}}(\bar{z}_{1}) \land \ldots \land {\mathcal{R}}_{i_{s}}(\bar{z}_{s}), $$

where ${\mathcal {R}}_{i_{j}}(\bar {z}_{1})$ are atomic formulas with ${\mathcal {R}}_{i_{j}}\in \tau$. We denote the set of variables of ϕ by $\textsf {var}(\phi ):=\bigcup _{j\in [s]} \textsf {var}({\mathcal {R}}_{i_{j}}(\bar {z}_{j}))$. The set of all atoms of ϕ is denoted by atom (ϕ).

A conjunctive query ϕ over τ is a formula ϕ = ∃x ₁ … ∃x _t ϕ′ where ϕ′ is a quantifier free conjunctive query over τ and x _j ∈ var(ϕ) for all j ≤ t. The x _j are called quantified variables. The set of variables of ϕ is defined as var(ϕ) : = var(ϕ′ ). The set of free variables of ϕ is defined as free(ϕ) : = var(ϕ)∖{x ₁, … , x _t }. We often write $\phi (\bar {y})$ where $\{\bar {y}\}={\textsf {free}({{\phi }})}$, to stress the free variables.

A conjunctive query instance over τ, short CQ-instance, is a pair $\Phi =({\mathcal {A}}, \phi )$ where 𝓐 is a finite τ-structure and ϕ is a conjunctive query over τ. Φ is called quantifier free if the query ϕ is quantifier free.

Let $\Phi =({\mathcal {A}}, \phi )$ be a quantifier free CQ-instance. An assignment to Φ is a mapping a : var(ϕ) → A. A partial assignment to Φ is a mapping a : X → A for a subset X of var(ϕ). Let a : X → A and b : Y → A be two partial assignments. We call a and bcompatible, in symbols a ∼ b, if they agree on their common variables, i.e., for all x ∈ X ∩ Y we have a(x) = b(x). Let ${\mathcal {R}}(z_{1}, \ldots , z_{r})$ be an atom of ϕ. We say that asatisfies ${\mathcal {R}}(z_{1}, \ldots , z_{r})$ if $(a(z_{1}), \ldots , a(z_{r}))\in {\mathcal {R}}^{{\mathcal {A}}}$. We say that a satisfies Φ if it satisfies all of its atoms. In this case we write $({\mathcal {A}}, a)\models \phi$.

An assignment to a general, not necessarily quantifer free, CQ-instance $\Phi =({\mathcal {A}}, \phi )$ is a mapping a : free(ϕ) → A. An assignment a can alternatively be seen as a tuple of dimension |free(ϕ)| indexed by the variables free(ϕ). Consequently, relations will also be seen either as sets of tuples or as list of assignments. An assignment a:free(ϕ) → A satisfies Φ if there is an assignment a′ : var(ϕ) → A with a ∼ a′ such that the quantifier free query instance $({\mathcal {A}},\phi ^{\prime })$, where we get ϕ′ by deleting all quantifiers from ϕ, is satisfied by a′ . Again we write $({\mathcal {A}}, a)\models \phi$. Observe that a′ is in general not unique.

The query result $\phi ({\mathcal {A}})$ of a CQ-instance $\Phi =({\mathcal {A}}, \phi )$ is defined as

$$\phi({\mathcal{A}}):=\{a \mid ({\mathcal{A}}, a)\models \phi(\bar{x})\}. $$

The elements of the query result are called solutions of the query instance or satisfying assignments or query answers. We call two instances $\Phi = ({\mathcal {A}}, \phi ), \Phi ^{\prime } = ({\mathcal {A}}^{\prime }, \phi ^{\prime })$ solution equivalent, if free(ϕ)=free(ϕ′ ) and $\phi ({\mathcal {A}}) = \phi ^{\prime }({\mathcal {A}}^{\prime })$.

Let a : X → A be an assignment and Y ⊆ X. By a| _Y we denote the restriction of a onto Y. Similarly, if ${\mathcal {R}}$ is a relation indexed by X, i.e., such that each $a\in {\mathcal {R}}$ is interpreted as an assignment a : X → A then, $\pi _{Y}({\mathcal {R}}) := \{a|_{Y} \mid a\in {\mathcal {R}}\}$ denotes the projection of ${\mathcal {R}}$ onto Y. Throughout the paper we will make use of the following classical database operations on relations.

Definition 1

Let ${\mathcal {R}}_{1}$ and ${\mathcal {R}}_{2}$ be two relations indexed by the variables X and Y, respectively (X and Y being not necessarily disjoints). The natural join of ${\mathcal {R}}_{1}$ and ${\mathcal {R}}_{2}$ is

$${\mathcal{R}}_{1}\bowtie {\mathcal{R}}_{2} := \{ a: X\cup Y \rightarrow A \mid a|_{X}\in {\mathcal{R}}_{1}, b|_{Y}\in{\mathcal{R}}_{2}\}. $$

The semi-join of ${\mathcal {R}}_{1}$ and ${\mathcal {R}}_{2}$ is defined as ${\mathcal {R}}_{1} \ltimes {\mathcal {R}}_{2} := \pi _{X}({\mathcal {R}}_{1} \bowtie {\mathcal {R}}_{2})$.

2.2 Model of Computation and Encoding of Instances

The underlying model of computation for our algorithms will be the RAM model with addition as basic operation and with unit costs measure. We assume the relations of a finite structure 𝓐 to be encoded by listing their tuples. Apart from this convention we will not specify an encoding but only give estimates on its size in O-notation that will be satisfied by any reasonable encoding.

Let 𝓐 be a τ-structure. For a relation ${\mathcal {R}}^{{\mathcal {A}}}$ let $|{\mathcal {R}}^{{\mathcal {A}}}|$ denote the cardinality of ${\mathcal {R}}^{{\mathcal {A}}}$. Then we define for ${\mathcal {R}}^{{\mathcal {A}}}$

$$\|{\mathcal{R}}^{{\mathcal{A}}}\| := \text{arity}({\mathcal{R}}) \cdot |{\mathcal{R}}^{{\mathcal{A}}}|. $$

For the vocabulary τ let |τ| be the number of predicate symbols. Finally, let |A| be the cardinality of a domain A. Then for a structure 𝓐 over the vocabulary τ with domain A we define

$$\|{\mathcal{A}}\| := |\tau| + |A| +\sum_{{\mathcal{R}}\in \tau} \|{\mathcal{R}}^{{\mathcal{A}}}\|.$$

Furthermore, we define for a conjunctive query

$$|\phi| :=\sum_{\substack{\phi^{\prime}\in \textsf{atom}({\phi}),\\{\mathcal{R}} \text{ relation symbol of }\phi^{\prime} }} \mathrm{arity({\mathcal{R}})}.$$

Finally, for a CQ-instance $\Phi = ({\mathcal {A}}, \phi )$ we define

$$\|\Phi\| := |\phi| + \|{\mathcal{A}}\|.$$

Note that for any reasonable encoding, up to constant factors, $\|{\mathcal {A}}\|$ is the size of an encoding of 𝓐, ∥ϕ∥ is the size of an encoding of ϕ and ∥Φ∥ is the size of an encoding of Φ. For a detailed discussion and justification of these conventions see [16, Section 2.3].

The following lemma states that the basic database operations we considered above can be performed efficiently.

Lemma 1

([16]) Given relations ${\mathcal {R}}_{1}$ and ${\mathcal {R}}_{2}$ and $Y\subseteq \textsf {var}({{\mathcal {R}}})$, one can compute

• ${\mathcal {R}}_{1}\bowtie {\mathcal {R}}_{2}$ in time $O(\|{\mathcal {R}}_{1}\|+ \|{\mathcal {R}}_{2}\| + \|{\mathcal {R}}_{1}\bowtie {\mathcal {R}}_{2}\|)$,

• $\pi _{Y}({\mathcal {R}}_{1})$ in time $O(\|{\mathcal {R}}_{1}\|)$,

• ${\mathcal {R}}_{1}\ltimes {\mathcal {R}}_{2}$ in time $O(\|{\mathcal {R}}_{1}\| + \|{\mathcal {R}}_{2}\|)$.

We will use Lemma 1 throughout the paper, most of the time without explicitly referencing it.

2.3 Query Problems

The basic computational question on CQ-instances is the Conjunctive query answering problem.

Clearly, $\|\phi ({\mathcal {A}})\|$ can be exponential in ∥Φ∥ and thus we cannot have a polynomial time algorithm. The Boolean conjunctive query problem is defined as follows.

The main focus in this paper will be on the associated counting problem #CQ.

2.4 Parameterized Complexity

This section is a very short introduction to some notions from parameterized complexity used in the remainder of this paper. For more details see [17].

A parameterized decision problem over an alphabet Σ is a language L ⊆ Σ^∗ together with a computable parameterization κ : Σ^∗ → ℕ. The problem (L, κ) is said to be fixed-parameter tractable, or (L, κ) ∈ FPT, if there is a computable function $f:\mathbb {N}\rightarrow \mathbb {N}$ such that there is an algorithm that decides for x ∈ Σ^∗ in time f(κ(x))|x|^O(1) if x is in L.

Let (L, κ) and (L′ , κ′ ) be two parameterized decision problems over the alphabets Σ, resp. π. A parameterized many-one reduction from (L, κ) to (L′ , κ′ ) is a function r : Σ^∗ → Π^∗ such that for all x ∈ Σ^∗:

• x ∈ L ⇔ r(x) ∈ L′ ,

• r(x) can be computed in time f(κ(x))|x|^c for a computable function f and a constant c, and

• κ′ (r(x)) ≤ g(κ(x)) for a computable function g.

It is easy to see that FPT is closed under parameterized many-one reductions.

Let p- Clique be the following parameterized problem.

Here the parameterization κ is simply defined by κ(G, k) := k. The class W[1] consists of all parameterized problems that are parameterized many-one reducible to p- Clique. A problem (L, κ) is called W[1]-hard, if there is a parameterized many-one reduction from p-Clique to (L, κ).

It is widely believed that FPT ≠ W[1] and thus in particular p- Clique and all W[1]-hard problems are not fixed-parameter tractable.

Parameterized counting complexity theory is developed similarly to decision complexity. A parameterized counting problem is a function F : Σ^∗ × ℕ → ℕ, for an alphabet Σ. Let (x, k) ∈ Σ^∗ × ℕ, then we call x the input of F and k the parameter. A parameterized counting problem F is fixed-parameter tractable, or F ∈ FPT, if there is an algorithm computing F(x, k) in time f(k)⋅|x|^c for a computable function f : ℕ → ℕ and a constant c ∈ ℕ.

Let F : Σ^∗ × ℕ → ℕ and G : Π^∗ × ℕ → ℕ be two parameterized counting problems. A parameterized parsimonious reduction from F to G is an algorithm that computes, for every instance (x, k) of F, an instance (y, l) of G in time f(k)⋅|x|^c such that l ≤ g(k) and F(x, k) = G(y, l) for computable functions f, g : ℕ → ℕ and a constant c ∈ ℕ. A parameterizedT-reduction from F to G is an algorithm with an oracle for G that solves any instance (x, k) of F in time f(k)⋅|x|^c in such a way that for all oracle queries the instances (y, l) satisfy l ≤ g(k) for computable functions f, g and a constant c ∈ ℕ.

Let p- #Clique be the following problem.

A parameterized problem F is in #W[1] if there is a parameterized T-reduction from F to p- #Clique. F is #W[1]-hard, if there is a parameterized T-reduction from p- #Clique to F. As usual, F is #W[1]-complete if it is in #W[1] and hard for it, too.

Again, it is widely believed that there are problems in #W[1] (in particular the #W[1]-complete problems) that are not fixed-parameter tractable. Thus, from showing that a problem F is #W[1]-hard it follows that F can be assumed to be not fixed-parameter tractable.

We will mainly deal with two parameterized problems that are versions of CQ and #CQ parameterized by the size of the input query. This parameterization is justified by the origins from database theory. In a typical database application the query is usually far smaller than the database, so it makes sense to use the size of the query as a parameter.

2.5 Graphs and Hypergraphs Associated to Queries

As remarked before, CQ and #CQ are hard computational problems. One way to isolate islands of tractability, is to analyze structural aspects of the query. A key idea for this is to associated graphs and hypergraphs to queries.

A (finite) hypergraph 𝓗 is a pair (V, E) where V is a finite set and $E\subseteq {\mathcal {P}}(V)$ where ${\mathcal {P}}(V)$ is the power set of V. The arity of 𝓗 is maxe ∈ E|e|. We associate a hypergraph $\mathcal {H}=\mathcal {H}_{\phi }=(V,E)$ to a query ϕ by setting V := var(ϕ) and E := {var(ϕ _t )∣ϕ _t ∈ atom(ϕ)}.

Example 1

Consider the query

$$\begin{array}{@{}rcl@{}}\phi &:=& \exists u_{1} \exists u_{2} \exists u_{3} \exists u_{4} \exists u_{5} \exists u_{6} \exists u_{7} \exists u_{8} \\ && P_{1}(v_{1}, u_{1}) \land P_{2}(v_{2}, u_{1}, u_{2})\land P_{3}(v_{2}, v_{4}, u_{2}, u_{3})\\&&\land P_{4}(v_{3}, v_{4}, v_{5}, u_{3}, u_{4}, u_{5})\land P_{5}(v_{4}, v_{5}, v_{6}, v_{8}) \\&&\land P_{6}(v_{7}, v_{8}, u_{5}, u_{6})\land P_{2}(v_{6}, v_{9}, u_{7})\land P_{2}(v_{8}, v_{9}, u_{8})\end{array} $$

The associated hypergraph is illustrated in Fig. 1.

Fig. 1

The hypergraph associated to the query ϕ of Example 1

One also associates graphs to queries as follows: Let ϕ be a query with the associated hypergraph 𝓗 = (V, E), then one associates to ϕ the so-called primal graph 𝓗 _P = (V, E _p ) where for every u, v ∈ V we have uv ∈ E _p if and only if there is an edge e ∈ E with u, v ∈ E.

2.6 Graph and Hypergraph Decompositions

We now introduce several decomposition techniques for graphs and hypergraphs that will be used in the rest of this paper to analyze the complexity of counting solutions to queries.

2.6.1 Treewidth

We first present some basic facts on treewidth. All proofs can be found in the survey by Bodlaender [5] and the references therein.

Unless stated otherwise all graphs are nonempty, finite, undirected and simple, i.e., they have no parallel edges or loops. In contrast, trees are always assumed to be rooted and thus directed.

The treewidth of a graph G is a measure of how similar G is to a tree. There are several equivalent definitions for treewidth of which we will first present the one by Robertson and Seymour [32].

Definition 2

A tree decomposition of a graph G = (V, E) is a pair $({\mathcal {T}}, (\chi _{t})_{t\in T})$ where ${\mathcal {T}} = (T,F)$ is a rooted tree and χ _t ⊆ V for every t ∈ T satisfying the following properties:

• 1. For every v ∈ V there is a t ∈ T with v ∈ χ _t .

• 2. For every e ∈ E there is a t ∈ T such that e ⊆ χ _t .

• 3. For every v ∈ V the set {t ∈ T∣v ∈ χ _t } induces a subtree of 𝓣.

The third property is called the connectedness condition. The sets χ _t are called blocks or bags of the decomposition.

We call maxt ∈T(|χ _t |)−1 the width of the tree composition $({\mathcal {T}}, (\chi _{t})_{t\in T})$. The treewidth tw(G) of G is the minimum width over all tree decompositions of G.

To ease notation we sometimes identify a vertex t ∈ T with the corresponding bag χ _t .

We remark that the class of graphs of treewidth 1 consists exactly of all forests, i.e., the graphs that have trees as their connected components. In particular, trees have treewidth 1.

Example 2

Given the graph G from Fig. 2, a tree decomposition of G is given in Fig. 3.

Fig. 2

The graph G of Example 2

Fig. 3

A tree decomposition of width 2 of the graph G of Fig. 2

Given a graph G and an integer k, it is NP-complete to decide if G has treewidth G at most k, but if we take k as a parameter the problem becomes fixed-parameter tractable.

Theorem 1

([4]) There is a polynomial p and an algorithm that, given a graph G = (V, E), computes a tree decomposition of G of width k := tw(G) in time at most 2^p(k)|V|.

We will use the following folklore results.

Lemma 2

([13], Chap. 12) Let G = (V, E) be a graph, C ⊆ V a clique in G and $(\mathcal {T}, (\chi _{t})_{t\in T})$ a tree decomposition of G. Then there is a bag χ _t such that C ⊆ χ _t .

Lemma 3

([17], Chap. 11) Every graph G of treewidth at most k has a vertex of degree at most k.

We will also use an alternative definition of treewidth by so-called elimination orders.

Definition 3

Let G = (V, E) be a graph with |V| = n. A bijection π : V → [n] is called an elimination order. We say that u is higher-numbered than v with respect to π if π(u) > π(v). The fill-in graph G _π of G with respect to π is constructed iteratively: Starting from G, for i = 1, … , |V| we add an edge between all pairs u, w of neighbors of π ⁻¹(i) that are higher-numbered than π ⁻¹(i).

The width of π is the minimum integer k such that in G _π each vertex v ∈ V has at most k higher-numbered neighbors.

The elimination width elim-width(G) of G is the minimum width over all elimination orders of G.

Example 3

We consider again the graph G of Fig. 2. An elimination order π is defined by the sequence A, B, I, H, G, C, D, E, F. The fill-in graph G _π is shown in Fig. 4. The width of π is 2.

Fig. 4

The fill-in graph G _π of Example 3 defined by the sequence A, B, I, H, G, C, D, E, F. The edges added during the construction of G _π from G are represented as dotted lines

Elimination orders give the following characterization of treewidth which appears to be folklore. A proof can be found e.g., in [5].

Lemma 4

For every graph G we have elim-width(G) = tw(G).

2.6.2 Hypergraph Decomposition Techniques

In this section we present some well known hypergraph decomposition techniques. For more details on hypergraph decompositions see e.g., [10, 18, 30]. For all decomposition techniques defined below, the width of a CQ-instance $\Phi =({\mathcal {A}}, \phi )$ is simply defined as the width of the hypergraph associated to ϕ.

The simplest idea to generalize treewidth to hypergraphs is considering primal graphs and to define the treewidth of a hypergraph 𝓗 to be treewidth of its primal graph 𝓗 _P . By Lemma 2, classes of hypergraphs that have unbounded edge size are of unbounded treewidth even when the hypergraphs are intuitively very simple. Consequently, treewidth is, for some considerations on hypergraphs, not the right measure of the complexity of a hypergraph. Thus research focussed on finding decompositions that work with hypergraphs directly and not with their primal graphs. The base class of hypergraphs that roughly corresponds to trees in the setting of treewidth are acyclic hypergraphs which are defined with the help of join trees which organize the edges of a hypergraph in a tree with a connectivity condition similar to that for treewidth.

Definition 4

A join tree of a hypergraph 𝓗 = (V, E) is a pair $({\mathcal {T}}, (\lambda _{t})_{t\in T})$ where ${\mathcal {T}}=(T,F)$ is a rooted tree and for each t ∈ T we have λ _t ∈ E such that

• for each e ∈ E there is a t ∈ T such that λ _t = e,

• For each v ∈ V the set {t ∈ T∣v ∈ λ _t } induces a subtree of T.

A hypergraph is called acyclic if it has a join tree.

When there is no ambiguity, we often identify vertices t ∈ T with their edges λ _t .

Lemma 5

([33]) There is a polynomial time algorithm that, given a hypergraph 𝓗, decides if 𝓗 is acyclic. Moreover, if 𝓗 is acyclic the algorithm computes a join tree of 𝓗.

A conjunctive query ϕ is called acyclic if its associated hypergraph is acyclic.

Acyclic conjunctive queries play an important role in database theory, because of the following result by Yannakakis [33].

Theorem 2

([33]) ACQ can be solved in polynomial time.

Theorem 2 served as a starting point to finding more general classes of hypergraphs on which CQ is tractable, by trying to identify classes of “nearly” acyclic hypergraphs. There are lots of different decomposition techniques and associated width measures for hypergraphs. One of the most general width measures is generalized hypertree width.

The approach of generalized hypertree decomposition is similarly to that of tree decompositions: We want to organize a hypergraph into clusters that form a tree with a connectivity condition. Instead of bags that contain vertices and that must cover all edges, the basic clusters of generalized hypertree decompositions are guarded blocks (λ _t , χ _t ) where λ _t contains edges while χ _t contains vertices. To make sure that the vertices χ _t of a guarded block form a sufficiently simple set, we demand that χ _t is covered by the edges in λ _t and that λ _t is small. To make sure that the decomposition represents the hypergraph well, we require that every edge must be contained in a set χ _t (but not necessarily in a λ _t ). We now give the exact definition.

Definition 5

A generalized hypertree decomposition of a hypergraph 𝓗 = (V, E) is a triple $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ where $\mathcal {T} = (T,F)$ is a rooted tree and λ _t ⊆ E and χ _t ⊆ V for every t ∈ T satisfying the following properties:

• For every e ∈ E there is a t ∈ T such that e ⊆ χ _t .

• For every t ∈ T we have $\chi _{t} \subseteq \bigcup _{e\in \lambda _{t}} e$.

• For every v ∈ V the set {t ∈ T∣v ∈ χ _t } induces a subtree of 𝓣.

The third property is again called the connectedness condition. The sets χ _t are called blocks or bags of the decomposition, while the sets λ _t are called the guards of the decomposition. A pair (λ _t , χ _t ) is called guarded block.

The width of a decomposition $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ is maxt ∈ T(|λ _t |). The generalized hypertree width of 𝓗𝓗 is the minimum width over all generalized hypertree decompositions of 𝓗.

Again, we sometimes identify a guarded block (λ _t , χ _t ) with the vertex t.

Example 4

Figure 5 shows a generalized hypertree decomposition of width 3 for the hypergraph from Fig. 1.

Fig. 5

A generalized hypertree decomposition of width 3 for the hypergraph from Fig. 1. The boxes are the guarded blocks. In the upper parts the guards are given while the lower parts show the blocks. On the left part, a name is given to each node

We give the following very easy upper bound for generalized hypertree width.

Observation 3

Let 𝓗 = (V, E) be a hypergraph such that there are k edges e ₁, … , e _k in E with $V\subseteq \bigcup _{i=1}^{k} e_{i}$. Then 𝓗 has generalized hypertree width at most k.

Proof 1

We will construct a trivial width k generalized hypertree decomposition $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ of 𝓗. The tree 𝓣 only consists of one single vertex t, the block of t is χ _t := V and the guard is λ _t := {e ₁, … , e _k}. It is easily seen that this satisfies all desired properties of a hypertree decomposition. Furthermore, the decomposition has width k. □

It turns out the generalized hypertree width is strictly more general than treewidth in the following sense.

Lemma 6

([18]) For every hypergraph 𝓗 the generalized hypertree width is less than or equal to 1 + tw (𝓗). Moreover, for every ℓ there are hypergraphs of treewidth ℓ and generalized hypertree width 1.

Unfortunately, deciding if a hypergraph has generalized hypertree width at most k is NP-complete even for k = 3 [20]. This unpleasant result is amended by the fact that there is an approximation algorithm.

Theorem 4

([2, 19]) There is an algorithm that, given a hypergraph 𝓗 of generalized hypertree width k, constructs a generalized hypertree decomposition of width O(k) of 𝓗 in time $|\mathcal {H}|^{O(k)}$.

A hypergraph is acyclic if and only if it has generalized hypertree width 1. With this result the following lemma is easy to prove.

Lemma 7

Let $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ be a generalized hypertree decomposition of a hypergraph 𝓗. Let $\mathcal {H}^{\prime }=(V,E^{\prime })$ where E′ := {χ _t ∣t ∈ T}. Then 𝓗′ is acyclic and $(\mathcal {T}, (\chi _{t})_{t\in T})$ is a join tree of 𝓗′.

Next we state a lemma that in different forms is (implicitly) used in most papers that deal with the application of hypergraph decomposition techniques to CQ, see e.g., [19]. The main observation here is that we make explicit that the construction is solution equivalent.

Lemma 8

Given a CQ-instance Φ with associated hypergraph 𝓗 and a generalized hypertree decomposition of 𝓗 of width k, one can compute an ACQ-instance Ψ in time ∥Φ∥^O(k) such that Φ and Ψ are solution equivalent.

Proof

Let $\Phi =({\mathcal {A}}, \phi )$ and let the given generalized hypertree decomposition be $({\mathcal {T}}^{\prime }, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$. We construct $\Psi =({\mathcal {B}}, \psi )$ with var(ψ) = var(ϕ) as follows: For every t ∈ T the query ψ has an atom ψ _t with relation symbol ${\mathcal {R}}_{t}$ and var(ψ _t ) := χ _t . The quantifiers are the same as for ϕ. For every t ∈ T let ϕ ₁, … , ϕ _s be the atoms associated to the edges in λ _t . We have s ≤ k. Let $\phi _{1}^{\prime }, \ldots , \phi _{\ell }^{\prime }$ be the atoms associated to the edges e with e ⊆ χ _t . Then we define the relation ${\mathcal {R}}_{t}^{{\mathcal {B}}}$ as

$${\mathcal{R}}_{t}^{{\mathcal{B}}}:= \pi_{\chi_{t}}(\phi_{1}({\mathcal{A}})\bowtie \ldots \bowtie \phi_{s}({\mathcal{A}})) \bowtie \phi_{1}^{\prime}({\mathcal{A}})\bowtie \ldots \bowtie \phi_{\ell}^{\prime}({\mathcal{A}}). $$

We claim that ϕ and ψ are solution equivalent. First consider an assignment a that satisfies all atoms of ϕ. Then we have for every subset $\phi _{1}^{\prime }, \ldots , \phi _{r}^{\prime }$ of atom(ϕ) that the assignment a is compatible to an assignment in $\phi _{1}^{\prime }\bowtie \ldots \bowtie \phi _{r}^{\prime }$. If follows that for each t the new atom ψ _t is satisfied by a. Consequently, $\phi ({\mathcal {A}})\subseteq \psi ({\mathcal {B}})$.

Let now a be an assignment that satisfies all atoms of ψ. Then a must for each t satisfy the atoms $\phi _{i}^{\prime }$ from the construction of ${\mathcal {R}}^{{\mathcal {B}}}$. But since each edge e of 𝓗 is covered by a set $\chi _{t^{\prime }}$, every atom in atom(ϕ) contributes as a $\phi _{i}^{\prime }$ in the construction of a ϕ _t . Consequently, a satisfies all atoms of ϕ and thus $\psi ({\mathcal {B}})\subseteq \phi ({\mathcal {A}})$.

We claim that this construction can be done in time ∥Φ∥^O(k). To see this, observe that the relation $A_{\lambda _{t}}:=\pi _{\chi _{t}}(\phi _{1}({\mathcal {A}})\bowtie \ldots \bowtie \phi _{s}({\mathcal {A}}))$ has size at most $\|{\mathcal {A}}\|^{s} \le \|{\mathcal {A}}\|^{k}$. Since for the $\phi _{i}^{\prime }$ we have $\textsf {var}(\phi _{i}^{\prime })\subseteq \chi _{t}$, it follows that ${\mathcal {R}}_{t}^{{\mathcal {B}}}\subseteq A_{\lambda _{t}}$ and thus consequently $\|{\mathcal {R}}_{t}^{{\mathcal {B}}}\|\le \|{\mathcal {A}}\|^{k}$. With Lemma 1 it follows that we can compute ${\mathcal {R}}_{t}^{{\mathcal {B}}}$ in time $|\phi |\|{\mathcal {A}}\|^{O(k)}$. Thus computing the instance Ψ takes time ∥Φ∥^O(k).

Finally, by Lemma 7 we have that Ψ is acyclic. □

The combination of Theorem 2 and Lemma 8 allows to solve CQ-instances in time ∥Φ∥^O(k) provided that a generalized hypertree decomposition of width k is given. Thus the bottleneck for solving CQ-instances for many proposed decomposition techniques is the efficient computation of a good decomposition of the instance.

Let us fix some notation: For an edge set λ ⊆ E we use the shorthand $\bigcup \lambda := \bigcup _{e\in \lambda } e$. For a decomposition $(\mathcal {T}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ we write $\mathcal {T}_{t}$ for the subtree of 𝓣 that has t as its root and denote by $V(\mathcal {T}_{t})\subseteq T$ its vertex set. We also write $\chi (\mathcal {T}_{t}) := \bigcup _{t^{\prime }\in V(\mathcal {T}_{t})} \chi _{t^{\prime }}$. We use these notations for tree decompositions as well.

It is sometimes helpful to consider restrictions of generalized hypertree decompositions, because those might have better structural or algorithmic properties. A number of them have been defined and studied in the past, among others biconnected component, cycle-cutset, cycle-hypercutset, hingetree, hypertree decomposition (see [30] for a survey). Hingetree decomposition will play a role in this paper and we define it formally below.

Definition 6

A generalized hypertree decomposition is called hingetree decomposition if it satisfies the following conditions:

• For each pair t ₁, t ₂ ∈ T with t ₁ ≠ t ₂ there are edges e ₁ ∈ ${\lambda}_{t_{1}}$ and e ₂ ∈ ${\lambda}_{t_{2}}$ such that $\chi _{t_{1}} \cap \chi _{t_{2}} \subseteq e_{1}\cap e_{2}$.

• For each t ∈ T we have $\bigcup \lambda _{t} = \chi _{t}$.

• For each e ∈ E there is a t ∈ T such that e ∈ λ _t .

The hingetree width (also called degree of cyclicity) of 𝓗 is the minimum width over all hingetree decompositions of 𝓗.

Note that this is not the original definition from [25] but an alternative, equivalent definition from [10].

Example 5

The decomposition from Fig. 5 is also a hingetree decomposition since:

• $\chi _{b_{1}}\cap \chi _{b}=\{v_{4},u_{3}\}\subseteq \{v_{2},v_{4},u_{2},u_{3}\}\cap \{v_{3},v_{4},v_{5},u_{3},u_{4},u_{5}\} \in \lambda _{b_{1}}\cap \lambda _{b}$

• $\chi _{b_{2}}\cap \chi _{b}=\{v_{4},v_{5},v_{6},v_{8}\}\in \lambda _{b_{2}}\cap \lambda _{b}\vspace *{6pt}$

Like treewidth, hingetree width is strictly less general than generalized hypertree width in the following sense.

Lemma 9

([18]) For every hypergraph the generalized hypertree width is less than or equal to the hingetree width. Moreover, there are hypergraphs for which the generalized hypertree width is strictly less than the hingetree width.

Hingetree width makes up for this lack of generality by the fact that optimal decompositions can be computed very efficiently.

Lemma 10

([25]) There is an algorithm that, given a hypergraph 𝓗 = (V, E), computes a minimum width hingetree decomposition of 𝓗 in time |V|⋅|E|².

Since the presented decomposition techniques are all easy to compute, we get the following lemma.

Lemma 11

(see e.g., [10]) For all of the width measures defined above CQ restricted to instances Φ of width k can be solved in time ∥Φ∥^p(k) for a polynomial p.

3 Quantified Star Size

As proved in [31], even introducing one single existential quantifier in acyclic conjunctive queries leads to #P-complete counting problems. It follows that bounding the number of quantified variables does not yield tractable instances. In [15] we have shown a corresponding #W[1]-hardness result for p-#ACQ: We presented a class of hard instances for parameterized complexity which have a very simple form.

Lemma 12

([15]) Let $\phi _{\text {star},n} := \exists z \bigwedge _{i\in [n]} \mathcal {R}_{i}(z, y_{i})$ and let ${\mathcal {C}}_{\text {star}}:=\{ \phi _{{\text {star}},n}\mid n\in \mathbb {N}\}$. Then p-#CQ is #W[1]-hard for instances restricted to queries in ${\mathcal {C}}_{{\text {star}}}$.

For an alternative proof of Lemma 12 see [29].

A basic observation on the hard instances of Lemma 12 is that their associated hypergraphs are stars whose center is the single quantified variable. Abstracting this observation, we shall define the parameter called quantified star size which, when bounded and combined with known decomposition techniques, leads to tractable #CQ-instances. This parameter has been introduced in [15] for acyclic queries and we generalize it here to the general setting. As we will see, not the number of quantified variables in a query is crucial but how they are distributed in the associated hypergraph.

Before we introduce quantified star size, we make several other definitions.

Let ${\mathcal {H}}= (V,E)$ be a hypergraph and V′ ⊆ V. A subhypergraph 𝓗′ = (V′, E′) of 𝓗 is a hypergraph with E′ ⊆ {e ∩ V′ ∣e ∈ E, e ∩ V′ ≠ ∅}. The induced subhypergraph 𝓗 [V′] of 𝓗 is the hypergraph 𝓗 [V′] = (V′, E′) where, this time, E′ ={e ∩ V′ ∣e ∈ E, e ∩ V′ ≠ ∅}. Let x, y ∈ V, a path between x and y is a sequence of vertices x = v ₁,..., v _k = y such that for each i ∈ [k − 1] there is an edge e _i ∈ E with v _i , v _i+1 ∈ e _i .

A (connected) component of 𝓗 is an induced subhypergraph 𝓗 [V′] where V′ is a maximal vertex set such that for each pair x, y ∈ V′ there is a path between x and y in 𝓗. These definitions apply to graphs as well.

We will use the following observation on induced subgraphs of acyclic hypergraphs.

Observation 5

Let β be any decomposition technique defined in Section 2.6. Let 𝓗 = (V, E) be a hypergraph of β-width k. Then for every V′ ⊆ V the induced subhypergraph 𝓗 [V′] has β-width at most k.

Proof

Let $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t_{i}n T})$ be a β-decomposition of 𝓗 of width k. For each guarded block (λ _t , χ _t ) compute a guarded block $(\lambda ^{\prime }_{t}, \chi ^{\prime }_{t})$ with χ _t := χ _t ∩ V′ and λ _t := {e ∩ V′ ∣e ∈ λ}. It is easy to check that $(\mathcal {T}, (\lambda ^{\prime }_{t})_{t\in T}, (\chi ^{\prime }_{t})_{t_{i}n T})$ is a β-decomposition of width at most k. □

Since acyclic hypergraphs are the hypergraphs of generalized hypertree width 1, we get the following special case.

Observation 6

If 𝓗 = (V, E) is an acyclic hypergraph and V′ ⊆ V, then 𝓗 [V′] is acyclic. More specifically, let $(\mathcal {T}, (\lambda )_{t_{\in } T})$ with $\mathcal {T}=(T,F)$ be a join tree of 𝓗. Then $(\mathcal {T}[T^{\prime }],(\lambda _{t}\cap V^{\prime })_{t\in T^{\prime }})$ where T′ := {t ∈ T ∣ λ _t ∩ V′ ≠ ∅} can be made into a join tree of 𝓗 [V′] by connecting the components of $\mathcal {T}[T^{\prime }]$ arbitrarily.

Observe that there is no version of Observation 5 or Observation 6 for subhypergraphs instead of induced subhypergraphs. To see this consider an arbitrary hypergraph 𝓗 = (V, E). Adding the edge V to E yields an acyclic hypergraph, independent of the generalized hypertree width of 𝓗.

Definition 7

An S-hypergraph is a pair 𝓗, S) where 𝓗 = (V, E) is a hypergraph and S ⊆ V. If 𝓗 is a graph, we also call (𝓗, S) an S-graph.

The S-hypergraph associated to a CQ-instance $\Phi =({\mathcal {A}}, \phi )$ consists of the hypergraph associated to ϕ and S := free(ϕ). The primalS-graph of 𝓗 is defined as (𝓗 _P , S).

Definition 8

Let 𝒢 be a class of S-hypergraphs. By #CQ on 𝒢 we denote the restriction of #CQ to instances whose associated S-hypergraph is in 𝒢. Analogously, by p-#CQ on 𝒢 we denote the restriction of p-#CQ to instances whose associated S-hypergraph is in 𝒢.

Definition 9

We call an S-hypergraph S-connected if for every pair of vertices x, y there is a path x = v ₁, v ₂, … , v _k−1, v _k = y such that v _i ∉ S for i ∉ {1, k}.

Let us consider some examples of queries that have S-connected S-hypergraphs.

Example 6

Path queries (of arbitrary length), for example

$$\phi(x,y):= \exists t_{1} \exists t_{2} \exists t_{3} {\mathcal{R}}(x,t_{1}) \wedge {\mathcal{R}}(t_{1},t_{2}) \wedge {\mathcal{R}}(t_{2},t_{3}) \wedge {\mathcal{R}}(t_{3},y)$$

have as their associated S-hypergraph a path in which only the end vertices are in S. Thus their S-hypergraph is S-connected.

Example 7

The associated graph of the query ϕ _{star, n} of Lemma 12 is the star G _n = (V _n , E _n ) where V _n = {z, y ₁, … , y _n } and E _n = {zy ₁, … , zy _n }. Furthermore, the free variables are S _n = {y ₁, … , y _n }. Every vertex in V _n is connected to every other vertex via z ∉ S _n . Thus (G _n , S _n ) is S _n -connected.

Definition 10

An independent setI in a hypergraph 𝓗 = (V, E) is a set I ⊆ V such that there are no distinct vertices x, y ∈ I that lie in a common edge e ∈ E.

Note that independent sets defined this way are in the hypergraphs literature often called strong independent sets. There is also the notion of weak independent set where we only require that no edge lies completely in the set I. Since we will only talk about strong independent sets and there is thus no danger of confusing the two notions, we will simply talk about independent sets always implying the strongness implicitly.

Definition 11

The S-star size of an S-connected S-hypergraph is the maximum size of an independent set consisting of vertices in S only. We say that such an independent set forms an S-star.

We remark that the S-star size of an S-connected S-hypergraph can equivalently be expressed as the the size of a maximum independent set in 𝓗 [S].

Example 8

The S-hypergraphs associated to the path queries of Example 6 have S-star size 2, because the two end vertices of the paths are independent.

Now consider the S _n -hypergraph (G _n , S _n ) from Example 7. The vertices of S _n are all independent. Consequently, the S _n -star size of (G _n , S _n ) is n.

Note that while the quantified star size of instances whose associated hypergraph is a path is bounded by 2, the S-star size of bounded pathwidth instances is unbounded. To see this, observe that the S _n -hypergraph (G _n , S _n ) from above has pathwidth 1: The decomposition $({\mathcal {P}}, (\chi _{t})_{t\in T})$ where ${\mathcal {P}}$ is the path with vertex set [n] and χ _i := {z, y _i }, is a path decomposition of G _n of width 1.

We want to extend the notion of S-star size to S-hypergraphs that are not necessarily S-connected. To this end, we consider certain S-connected subhypergraphs that we call S-components. We make the following crucial definition.

Definition 12

Let 𝓗 = (V, E) be a hypergraph and S ⊆ V. Let C be the vertex set of a connected component of 𝓗 [V − S]. Let E _C be the set of hyperedges {e ∈ E∣e ∩ C ≠ ∅} and $V_{C}^{\prime }:= \bigcup _{e\in E_{C}} e$. Then $\mathcal {H}[V_{C}^{\prime }]$ is called an S-component of 𝓗.

Example 9

Let us consider the S-hypergraph of the query from Example 1. The associated hypergraph 𝓗 was already illustrated in Fig. 1. We have S = {v ₁, ... , v ₉}. Then 𝓗 [V∖S] has three components with the vertex sets C ₁ := {u ₇}, C ₂ := {u ₈} and C ₃ := {u ₁, … , u ₆}. Thus

• $E_{C_{1}}= \big \{ \{u_{7}, v_{6}, v_{9}\}\big \}$,

• $E_{C_{2}}= \big \{\{u_{8}, v_{8}, v_{9}\}\big \}$, and

• $E_{C_{3}}= \big \{\{u_{1},v_{1}\}, \{u_{1}, u_{2}, v_{2}\}, \{u_{2}, u_{3}, v_{2}, v_{4}\},$ {u ₃, u ₄, u ₅, v ₃, v ₄, v ₅}, {u ₅, u ₆, v ₇, v ₈}}.

Hence, the vertex sets of the components are: $V_{C_{1}}^{\prime }= \{u_{7}, v_{6}, v_{9}\}$, $V_{C_{2}}^{\prime }= \{u_{8}, v_{8}, v_{9}\}$ and $V_{C_{3}}^{\prime } = \{u_{1}, u_{2}, u_{3}, u_{4},$ u ₅, u ₆, v ₁, v ₂, v ₃, v ₄, v ₅, v ₇, v ₈}. The three resulting S-components are depicted in Fig. 6.

Fig. 6

The S-components of the S-hypergraph discussed in Example 9

The following observations are evident from the definition.

Observation 7

To an S-hypergraph (𝓗, S) one can in polynomial time compute all its S-components.

Observation 8

The only S-component of an S-connected S-hypergraph (𝓗, S) is 𝓗. Moreover, the S-components of S-hypergraphs are S-connected.

Observation 8 allows to extend the definition of S-star size to not necessarily S-connected hypergraphs.

Definition 13

For an S-hypergraph 𝓗, S) we define S-star size as the maximum S-star size of its S-components.

Example 10

Let us compute the S-star size of the S-hypergraph of Example 9. The S-components induced by $V_{C_{1}}^{\prime }$ and $V_{C_{2}}^{\prime }$ are completely covered by the edges {u ₇, v ₆, v ₉}, resp., {u ₈, v ₈, v ₉}. It follows that the S-star size of these S-components is 1. We have $V_{C_{3}}\cap <Emphasis Type="Italic">S</Emphasis> = \{v_{1}, v_{2}, v_{3}, v_{4}, v_{5}, v_{7}, v_{8}\}$. There are several maximum independent sets of vertices in $V_{C_{3}}\cap S$ in the S-component induced by $V_{C_{3}}$, all of size 4. An example is {v ₁, v ₂, v ₃, v ₇}. It follows that the S-star size of (𝓗, S) is 4

Now we can finally come back to CQ-instances and define the promised parameter quantified star size.

Definition 14

The quantified star size of a conjunctive query is defined as the S-star size of the associated S-hypergraph. The quantified star size of a CQ-instance is that of its query.

Example 11

The query from Example 1 has quantified starsize 4 as we have seen in Example 10. From Example 8 we get that the queries ϕ _{star, n} of Lemma 12 are of quantified star size n, which is nearly the size of the query.

4 Quantified Star Size is Sufficient and Necessary for Efficient Counting

In this section we analyze the effect of quantified star size on the complexity of #CQ.

4.1 An Algorithm for Instances of Bounded Quantified Star Size

In this section we show that the decomposition techniques introduced in Section 2.6 lead to efficient counting when combined with bounded quantified star size. We proceed with the following rather technical lemma.

Lemma 13

There is an algorithm that, given a CQ-instance $\Phi =({\mathcal {A}},\phi )$ of quantified starsize ℓ and a generalized hypertree decomposition $\varXi = (\mathcal {T},$ (λ _t )t ∈ T, (χ _t )t ∈ T) of Φ of width k, constructs a CQ-instance $\Psi =({\mathcal {B}},\psi )$ in time ∥Φ∥^p(k,ℓ) for a fixed polynomial p such that

• Φ and Ψ are solution equivalent,

• Ψ is acyclic, and

• ψ is quantifier free.

In the proof we will use the following lemma from [15]. An edge cover of a hypergraph 𝓗 = (V, E) is a set E ^∗ of edges of 𝓗 such that $V\subseteq \bigcup _{e\in E^{*}} e$.

Lemma 14

([15]) For acyclic hypergraphs the size of a maximum independent set and a minimum edge cover coincide. Moreover, there is a polynomial time algorithm that given an acyclic hypergraph 𝓗 computes a maximum independent set I and a minimum edge cover E ^∗ of 𝓗.

Proof of Lemma 13

Given $\Phi =({\mathcal {A}},\phi )$, we construct Ψ in several steps.

Let 𝓗 = (V, E) be the hypergraph of ϕ. Let V ₁, … , V _m be the vertex sets of the connected components of 𝓗 [V∖S] and let $V_{1}^{\prime }, \ldots , V_{m}^{\prime }$ be the vertex sets of the corresponding S-components of 𝓗. Clearly, we have $V_{i}\subseteq V_{i}^{\prime }$ and $V_{i}^{\prime }\setminus V_{i} = V_{i}^{\prime }\cap <Emphasis Type="Italic">S</Emphasis> =: S_{i}$. Let Φ _i be the CQ-instance whose query ϕ _i is obtained by restricting all atoms of ϕ to the variables in $V_{i}^{\prime }$ and whose structure ${\mathcal {A}}_{i}$ is obtained by projecting all relations of 𝓐 accordingly. The associated hypergraph of ϕ _i is $\mathcal {H}[V_{i}^{\prime }]$. Moreover, $\mathcal {H}[V_{i}^{\prime }]$ has a generalized hypertree decomposition Ξ _i of width at most k with a tree $\mathcal {T}_{i}$ that is a subtree of 𝓣 (see Observation 5).

Now fix i. To Φ _i we construct a solution equivalent ACQ-instance $\Phi _{i}^{\prime }=({\mathcal {A}}_{i}^{\prime },\phi _{i}^{\prime })$ as in the proof of Lemma 8: For each t ∈ T we construct an atom ϕ _t in the variables χ _t . The associated relation is given by

$$\pi_{\chi_{t}}\left(\begin{array}{cc} \bowtie &\phi^{\prime}({\mathcal{A}}_{i})\\ \phi^{\prime}\in \textsf{atom}({\phi})\colon&\\ \textsf{var}({\phi^{\prime}})\in \lambda_{t}& \end{array}\right)\bowtie\left(\begin{array}{cc} \bowtie&\phi^{\prime}({\mathcal{A}}_{i})\\ \phi^{\prime} \in \textsf{atom}({\phi_{i}})\colon&\\ \textsf{var}({\phi^{\prime}}) \subseteq \chi_{t} \end{array}\right), $$

i.e., by taking the natural join of the relations belonging to the atoms of the guard λ _t projected to χ _t and all relations of the atoms in ϕ _i whose variables lie in χ _t . The decomposition Ξ _i has width at most k so this construction can be done in time ∥Φ∥^O(k) as seen in the proof of Lemma 8. The query $\phi _{i}^{\prime }$ of $\phi _{i}^{\prime }$ is defined as the conjunction of the ϕ _t over all t ∈ T _i and with the same quantified variables as ϕ. By Lemma 8, Φ _i and $\Phi ^{\prime }_{i}$ are solution equivalent, we have $\|\Phi _{i}^{\prime }\|\le \|\Phi _{i}\|^{O(k)}$ and $\Phi ^{\prime }_{i}$ is acyclic.

Let 𝓗 _i be the associated hypergraph of $\phi _{i}^{\prime }$, then 𝓗 _i , S _i ) has only one single S _i -component, because all the vertices in V _i are connected in 𝓗 and thus also in 𝓗 _i .

We claim that the S _i -star size of ${\mathcal {H}}_{i}$ is at most the S _i -star size of ${\mathcal {H}}[V_{i}^{\prime }]$. To see this, consider two independent vertices u,v in $\mathcal {H}_{i}$. The edges e of $\mathcal {H}_{i}$ are equal to the blocks χ _t of Ξ _i . Because u and v are independent in $\mathcal {H}_{i}$, they do not appear in a common block χ _t in Ξ _i . But then u and v cannot lie in one common edge in $\mathcal {H}[V_{i}]$, because every edge in $\mathcal {H}\left [V_{i}^{\prime }\right ]$ is contained in a block χ _t by definition of generalized hypertree decompositions. So u and v are independent in $\mathcal {H}\left [V_{i}^{\prime }\right ]$ as well. Thus every independent set in $\mathcal {H}_{i}$ is also independent in $\mathcal {H}\left [V_{i}^{\prime }\right ]$. So the S _i -star size of $\mathcal {H}_{i}$ indeed is at most the S _i -star size of $\mathcal {H}\left [V_{i}^{\prime }\right ]$ which is at most ℓ by assumption.

Thus by Lemma 14 the vertices in S _i can be covered by at most ℓ edges e ₁, … , e _ℓ in $\mathcal {H}_{i}$ which we can compute in polynomial time. Let α ₁, … , α_ℓ be the atoms corresponding to the edges e ₁, … , e _ℓ.

We construct a new atomic formula $\phi _{i}^{\prime \prime }$ in the variables S _i and an associated relation ${\mathcal {R}}_{i}^{\prime \prime }$ as follows: For each combination a₁, … , a_ℓ of compatible tuples in $\alpha _{1}\left ({\mathcal {A}}_{i}^{\prime }\right ), \ldots , \alpha _{\ell }\left ({\mathcal {A}}_{i}^{\prime }\right )$ let a be the single tuple in $\pi _{S_{i}}(\{a_{1}\}\bowtie \ldots \bowtie \{a_{\ell }\})$. We fix the free variables in $\phi _{i}^{\prime }$ to the constants prescribed by a. The result is a CQ-instance Φ_a with the associated hypergraph $\mathcal {H}[V_{i}]$. By Observation 6 Φ_a is acyclic and can thus be solved in polynomial time with Theorem 2. If Φ_a has a solution, add a to the relation ${\mathcal {R}}_{i}^{\prime \prime }$. This completes the construction of ${\mathcal {R}}_{i}^{\prime \prime }$.

Let ${\mathcal {A}}_{i}^{\prime \prime }$ be the structure containing only the relation ${\mathcal {R}}_{i}^{\prime \prime }$. By construction, $\Phi _{i}^{\prime \prime }:=\left ({\mathcal {A}}_{i}^{\prime \prime },\phi _{i}^{\prime \prime }\right )$ is solution equivalent to $\phi _{i}^{\prime }$ and thus also to Φ _i . Observe that the instances Φ_a can be solved in polynomial time by Theorem 2. Moreover, since $\|\Phi _{i}^{\prime }\|\le \|\Phi \|^{O(k)}$, only ∥Φ∥^O(kℓ) tuples a need to be considered. Thus $\phi _{i}^{\prime \prime }$ can be constructed in time ∥Φ _i ∥^p(k,ℓ) for a polynomial p.

We now return to the original instance Φ and eliminate the quantified variables in the query ϕ. To do so, we add the atom $\phi _{i}^{\prime \prime }$ for i ∈ [m] and delete all atoms that contain any quantified variable. Moreover, we add the relation ${\mathcal {R}}_{i}^{\prime \prime }$ to the structure 𝓐. We call the resulting #CQ instance $\Phi ^{\prime \prime }=({\mathcal {A}}^{\prime \prime },\phi ^{\prime \prime })$. The overall runtime of the construction is at most ∥Φ∥^p(k,ℓ). Also Φ″ is solution equivalent to Φ, because $\left ({\mathcal {A}}_{i}^{\prime \prime },\phi _{i}^{\prime \prime }\right )$ is solution equivalent to $\phi _{i}^{\prime }$.

We claim that Φ″ has generalized hypertree width at most k. To show this we construct a generalized hypertree decomposition Ξ″ of ϕ″ by doing the following: For each t ∈ T with χ _t ∩ V _i ≠ ∅ we construct a guarded block $\left (\lambda ^{\prime }_{t}, \chi ^{\prime }_{t}\right )$ by deleting all edges e with e ∩ V _i ≠ ∅ from λ _t and adding the edge S _i for $\phi _{i}^{\prime \prime }$. Furthermore we set $\chi _{t}^{\prime } = (\chi _{t}\setminus V_{i})\cup S_{i}$. It is easy to see that the result is indeed a generalized hypertree decomposition of ϕ″ of width at most k.

Finally, we construct an ACQ-instance $\Psi :=({{\mathcal {B}}},\psi )$ equivalent to Φ″ with Lemma 8. □

We now directly get the desired counting result:

Corollary 1

#CQ on instances Φ of generalized hypertree width k and quantified star size ℓ can be solved in time ∥Φ∥^{p(k, l)} for a polynomial p.

Proof

Use Theorem 4 to construct a generalized hypertree decomposition of width O(k), then apply Lemma 13 and count with the algorithm of [31] or [15]. □

4.2 Bounded Quantified Star Size is Necessary

In this section we will show that bounded quantified star size is a necessary restriction for tractable #CQ: Under the assumption FPT ≠ #W[1], all classes 𝒢 of S-hypergraphs for which p-#CQ is fixed-parameter tractable must have bounded quantified star size. As polynomial time tractability trivially implies fixed-parameter tractability, it follows that bounded quantified star size must also be necessary for classes 𝒢 of S-hypergraphs that allow polynomial time algorithms.

Let 𝒢 be a class of S-hypergraphs. Remember that by #CQ on 𝒢 we denote the restriction of #CQ to instances whose associated S-hypergraph is in 𝒢. Analogously, by p-#CQ on 𝒢 we denote the restriction of p-#CQ to instances whose associated S-hypergraph is in 𝒢.

We will use the fact that #CQ is already hard for very restricted S-hypergraphs, namely those of the queries from the class ${\mathcal {C}}_{{\text {star}}}$ from Lemma 12.

Theorem 9

Assume FPT ≠ #W[1], and let 𝒢 be a recursively enumerable class of S-hypergraphs. If p-#CQ is fixed-parameter tractable for 𝒢, then 𝒢 is of bounded S-star size.

Before proving Theorem 9, let us take some time to discuss its assumption, because we will see this and similar assumptions throughout the rest of this paper. The reader might feel that it would be more satisfying to prove a version of this theorem not under the assumption FPT ≠ #W[1] from parameterized complexity but instead to prove it based on a more standard assumption like FP ≠ #P. Clearly, the statement would then have to change from “fixed-parameter tractable” to “polynomial time tractable”, but this could still be preferable. Unfortunately, it is unlikely that such a version of Theorem 9 can be proved. One can show that assuming FP ≠ #P there are classes of S-graphs on which #CQ is neither in FP nor #P-complete (see [29, Chapter 5.3]). Thus is seems unlikely that the theory of #P-completeness suffices to identify the classes of S-hypergraphs on which #CQ is tractable.

Furthermore, let us remark that if the reader feels uncomfortable with parameterized complexity, he can safely exchange the assumption FPT ≠ #W[1] against the so-called exponential time hypothesis which is the following conjecture.

Conjecture 1

(Exponential time hypothesis) 3- SAT cannot be solved in time 2^o(n) where n is the number of variables of the input.

The exponential time hypothesis implies FPT ≠ W[1] [14, Chapter 17] and thus also FPT ≠ #W[1]. Hence Theorem 9 and several other results of this paper could also be formulated with the assumption that the exponential time hypothesis is true if the reader prefers an assumption from more classical complexity theory.

We will use the following lemma to prove Theorem 9.

Lemma 15

Let 𝒢 be a recursively enumerable class of S-hypergraphs of unbounded S-star size. Then p-#CQ on 𝒢 is # W[ 1]-hard.

Let ${\mathcal {G}}_{\text {star}}$ be the class of S-graphs (G _n , S _n ) where G _n is the star with n leaves and S _n consists of all vertices but the center of G _n . Note that the S-hypergraphs of the queries ${\mathcal {C}}_{{\text {star}}}$ from Lemma 12 are the S-graphs in ${\mathcal {G}}_{{\text {star}}}$ (see Example 7). Since by Lemma 12 p-#CQ restricted to instances with queries in ${\mathcal {C}}_{{\text {star}}}$ is #W[1]-hard, it follows directly that p-#CQ on ${\mathcal {G}}_{{\text {star}}}$ is #W[1]-hard. The idea of the proof of Lemma 15 is to show that ${\mathcal {G}}_{{\text {star}}}$ can be embedded in an appropriate way into any class 𝒢 of S-hypergraphs of unbounded S-star size to show that p-#CQ on 𝒢 is #W[1]-hard.

We feel that it is more transparent to show Lemma 15 for the restricted case of S-connected S-hypergraphs and to sketch afterwards how to generalize the proof to the general case. Remember that an S-hypergraph (𝓗, S) is called S-connected if for every pair of vertices x, y there is a path x = v ₁, v ₂, … , v _k−1, v _k = y such that v _i ∉ S for i ∉ {1, k}.

Lemma 16

Let 𝒢 be a recursively enumerable class of S-connected S-hypergraphs of unbounded S-star size. Then p-#CQ on 𝒢 is # W[ 1]-hard.

Proof

Let 𝒢 be a class of S-connected S-hypergraphs of unbounded S-star size.

Remember ${\mathcal {C}}_{\text {star}}:=\{ \phi _{\text {star},n}\mid n\in \mathbb {N}\}$ is defined with $\phi _{\text {star},n} = \exists z \bigwedge _{i\in [n]} \mathcal {R}_{i}(z, y_{i})$ (see Lemma 12). We will show a parameterized parsimonious reduction from p-#CQ, restricted to instances that have queries in ${\mathcal {C}}_{{\text {star}}}$, to p-#CQ on 𝒢. As p-#CQ on the former class of instances is #W[1]-hard by Lemma 12, the claim will follow.

Let $\Phi =({\mathcal {A}},\phi )$ be an instance of #CQ restricted to queries in ${\mathcal {C}}_{\text {star}}$, i.e., ϕ has the form $\phi = \exists z \bigwedge _{i=1}^{k} {\mathcal {R}}_{i}(z, y_{i})$. Because 𝒢 is recursively enumerable and of unbounded S-star size, there is a computable function g : ℕ → ℕ such that for given k ∈ ℕ one can in time g(k) compute an S-connected S-hypergraph $(\mathcal {H}, S)\in {\mathcal {G}}$ of S-star size at least k. We will embed Φ into $\mathcal {H}=(V,E)$ to construct a #CQ-instance $\Psi :=({\mathcal {B}}, \psi )$ of size at most g(k)∥Φ∥². The instance Ψ will have the S-hypergraph (𝓗, S) and the same domain B := A as Φ.

For each e ∈ E let ψ _e be an atom with the relation symbol ${\mathcal {E}}_{e}$ and the set of variables var(ψ _e ) = e. Let

$$\psi^{\prime}:=\bigwedge_{e\in E} \psi_{e},$$

then ψ is the query we get from ψ′ by existentially quantifying all variables in V∖S. This completes the construction of the query ψ.

We now construct the structure ℬ. Let Y = {y ₁, … , y _k} ⊆ S be a set of independent vertices. Such a set Y must exist, because (𝓗, S) has S-star size at least k. Let d be an arbitrary but fixed element of A. We define ${\mathcal {E}}_{e}^{{\mathcal {B}}}$ depending on the vertices in e as follows:

• Case 1 Let first e ∈ E be an edge that contains y _i for some i ∈ [k]. Observe that y _i is uniquely determined, because no two of the vertices y _i share an edge. The atom ψ _e has the relation symbol ${\mathcal {E}}_{e}$ and as variables the vertices of e. We assume that the order of the variables in ψ _e is as follows: y _i is the first variable, followed by the other variables in e ∩ S and after those the variables in e∖S. We define ${\mathcal {E}}_{e}^{{\mathcal {B}}} := \{(v_{2}, <Emphasis Type="Italic">d</Emphasis>, \ldots , <Emphasis Type="Italic">d</Emphasis>, v_{1}, \ldots , v_{1})\mid (v_{1},v_{2})\in {\mathcal {R}}_{i}^{{\mathcal {A}}}\}$, where ${\mathcal {R}}_{i}^{{\mathcal {A}}}$ is the relation of ${\mathcal {R}}_{i}$ in 𝓐. Observe that this forces all variables in (e ∩ S)∖{y _i } to be equal to the value d in satisfying assignments, while the variables in e∖S must all have a common value v ₁. Furthermore, because y _i is uniquely determined, the relation ${\mathcal {E}}_{e}^{{\mathcal {B}}}$ is well defined.

• Case 2 Let now e ∈ E with e ∩ Y = ∅. We assume that the variables in ψ _e are ordered such that all variables in S ∩ e appear before those in e∖S. Then we define ${\mathcal {E}}_{e}^{{\mathcal {B}}}:=\{(d,\ldots , <Emphasis Type="Italic">d</Emphasis>, v_{1}, \ldots , v_{1})\mid v_{1}\in A\}$. Again in the satisfying assignments all variables in e ∩ S are forced to be equal to d, while the variables in e∖S can take an arbitrary but equal value.

This completes the construction of ℬ and thus that of $\Psi =({{\mathcal {B}}}, \psi )$. □

Claim 1

$|\phi ({\mathcal {A}})|=|\psi ({{\mathcal {B}}})|$.

Proof

Let ϕ′, resp., ψ′ be the quantifier free queries we get from ϕ, resp., ψ by deleting all quantifiers.

We construct a function B that to an assignment $a\in \phi ^{\prime }({\mathcal {A}})$ constructs an assignment B(a):=a′ with a′:V→B. We define

$$a^{\prime}(x):=\begin{cases} a(x), &x\in Y,\\ d, &x\in S\setminus Y,\\ a(z), & x\in V\setminus Y \end{cases}.$$

We claim that B is a bijection from $\phi ({\mathcal {A}})$ to $\psi ({{\mathcal {B}}})$. It is easily seen from the construction of ψ that a′ satisfies all atoms of ψ and thus $a^{\prime }\in \psi ^{\prime }({\mathcal {B}})$. Furthermore, B is obviously injective. Thus it only remains to prove that B is surjective. To see this, consider $b^{\prime }\in \psi ({\mathcal {B}})$. By construction of Ψ, we have b′(x)=d for all x∈S∖Y. Because $\mathcal {H}$ is S-connected, we have that $\mathcal {H}[V\setminus S]$ is connected. From the construction of Ψ it follows by an easy induction that there is a v ₁∈A such that b′(x)=v ₁ for all x∈V∖S. We construct an assignment b:var(ϕ)→A by b(x):=b′(x) for x∈{y ₁,…,y _k } and b(z):=v ₁. Obviously, B(b)=b′. Moreover, from the construction of Ψ is follows that $b\in \phi ^{\prime }({\mathcal {A}})$. Thus B is a bijection from $\phi ^{\prime }({\mathcal {A}})$ to $\psi ^{\prime }({\mathcal {B}})$.

We now construct a mapping B′ from $\phi ({\mathcal {A}})$ to $\psi ({{\mathcal {B}}})$ as follows: For $a\in \phi ^{\prime }({\mathcal {A}})$ we map a|_free(ϕ) to B(a)|_free(ψ). Since B is a bijection, it follows that B′ is a bijection as well. This proves the claim.

Obviously, the S-hypergraph associated to ψ is (𝓗, S). Moreover, by construction we have |ψ| ≤ g(k) and Ψ can be constructed in time at most g(k)∥Φ∥², because 𝓗 has size at most g(k) and the size of the relations is bounded by |A|². Thus, with Claim 1, the construction of Ψ form Φ is a parameterized parsimonious reduction. This completes the proof of Lemma 16. □

We now sketch how to extend Lemma 16 from S-connected S-hypergraphs to general S-hypergraphs in a straightforward way.

Proof of Lemma 15 (Sketch))

The proof follows the same ideas as that of Lemma 16: We first compute an S-hypergraph 𝓗 in 𝒢 of S-star size at least k. Then we choose an S-component 𝓗′ of S-star size at least k in 𝒢. We construct the relations ${\mathcal {E}}_{e}^{{\mathcal {B}}}$ in such a way that in every satisfying assignment every variable not in 𝓗 is forced to the value d. For all other variables we construct the relations as in the proof of Lemma 16. Since 𝓗′ is S-connected by Observation 8, the same arguments as in the proof of Lemma 16 show that the construction is a parsimonious parameterized reduction. □

Proof of Theorem 9

Assume that p-#CQ on 𝒢 is fixed-parameter tractable. By Lemma 15 we directly get FPT = #W[1] which contradicts the assumption. □

Combining Corollary 1 with Theorem 9 yields a characterization of classes of S-hypergraphs of bounded generalized hypertree width that allow efficient algorithms for #CQ.

Theorem 10

Let 𝒢 be a recursively enumerable class of S-hypergraphs of bounded generalized hypertree width. Then (assuming FPT ≠ #W[1]) the following statements are equivalent:

• 1. #CQ on 𝒢 is polynomial time tractable.

• 2. p-#CQ on 𝒢 is fixed-parameter tractable.

• 3. 𝒢 is of bounded S-star size.

Proof

1 → 2 is trivial. 2 → 3 is Theorem 9. Finally, 3 → 1 is Corollary 1. □

As a corollary we get that for a wide range of decomposition techniques commonly considered in the database and artificial intelligence literature, we can characterize the tractable classes of S-graphs by bounded quantified star size. For the decomposition techniques not defined here see [18].

Corollary 2

Let β be one of the following decomposition techniques: biconnected component, cycle-cutset, cycle-hypercutset, hingetree, hypertree, or generalized hypertree decomposition. Let furthermore 𝒢 be a recursively enumerable class of S-hypergraphs of bounded β-width. Then (assuming FPT ≠ #W[1]), the following statements are equivalent:

• 1. #CQ on 𝒢 is polynomial time tractable.

• 2. p-#CQ on 𝒢 is fixed-parameter tractable.

• 3. 𝒢 is of bounded S-star size.

Proof

1 → 2 is trivial. 2 → 3 follows from Theorem 9. For 3 → 1 observe that for every β of the claim we have that for every hypergraph 𝓗 the β-width of 𝓗 is bounded from below by a function in the generalized hypertree width of 𝓗. Thus 𝒢 has bounded generalized hypertree width and the claim follows with Corollary 1. □

5 Queries of Bounded Arity

In this section we show that for bounded arity #CQ we can exactly characterize the classes of S-hypergraphs that allow polynomial time counting. In this section all CQ-instances and all S-hypergraphs are always assumed to be of bounded arity.

We will give two different characterizations of S-hypergraphs of bounded arity that allow tractable #CQ: The first characterization is presented in Section 5.1 and uses treewidth and S-star size, following the ideas of Section 4. In Section 5.2 we introduce a notion of elimination width for conjunctive queries. It will allow us to characterize the S-hypergraphs of bounded arity that allow tractable #CQ with a single parameter.

5.1 A Characterization by Treewidth and S-star size

In this section we characterize the S-hypergraphs of bounded arity that allow tractable #CQ by treewidth and S-star size. The result of this section is based on a combination of the results of Section 4 and a result by Grohe from [22] which is a follow up of results by Grohe, Schwentick and Segoufin [24]. We state the theorem in our slightly different wording.

Theorem 11

([22]) Let 𝒢 be a recursively enumerable class of hypergraphs of bounded arity. Assume FPT ≠ W[1]. Then the following three statements are equivalent:

• 1. CQ on 𝒢 can be decided in polynomial time.

• 2. p- CQ on 𝒢 is fixed parameter tractable.

• 3. There is a constant c such that the hypergraphs in 𝒢 have treewidth at most c.

Theorem 11 is originally stated even for every fixed vocabulary. Moreover, in [22] characterizes, more generally, tractability for any class of queries (and not only in function of their underlying hypergraph) of bounded arity. In this setting a class of queries is tractable if and only if its cores, certain equivalent subqueries, are of unbounded treewidth. In particular, this yields tractable classes of queries of unbounded treewidth. With the more coarse hypergraph view, these unbounded treewidth cases cannot be captured as witnessed by Theorem 11.

Our goal is to provide a complete characterization of classes of S-hypergraphs of bounded arity that yield tractability for #CQ. Not too surprisingly, tractability depends on both treewidth and star size of the underlying S-hypergraph.

Theorem 12

Let 𝒢 be a recursively enumerable class of S-hypergraphs of bounded arity. Assume that W[1] ≠ FPT. Then the following statements are equivalent:

• 1. #CQ on 𝒢 is solvable in polynomial time.

• 2. p-#CQ on 𝒢 is fixed-parameter tractable.

• 3. There is a constant c such that for each S-hypergraph (𝓗, S) in 𝒢 the treewidth of 𝓗 and the S-star size of 𝓗 are at most c.

Let us discuss how Theorem 12 and Theorem 10 relate. First, it is not hard to see that for bounded arity hypergraphs treewidth and generalized hypertree width differ only by a constant factor. So we could have formulated Theorem 12 with generalized hypertree width instead of treewidth as well.

The key difference between Theorem 12 and Theorem 10 is that we can show here that bounded treewidth is not only sufficient for tractable counting but also necessary. As we already directly get from [31], there are by Lemma 2 families of S-hypergraphs of unbounded arity, and thus also unbounded treewidth, on which #CQ is tractable, so treewidth is not the right notion for this case. It is an intriguing question if there is a width measure that completely characterizes tractable CQ or tractable #CQ for unbounded arity, similarly to Theorem 11 and Theorem 12 in the bounded arity case.

Before giving the proof of Theorem 12 we make an observation.

Observation 13

If there is a recursively enumerable class 𝒢 of S-hypergraphs of unbounded treewidth such that p-#CQ on 𝒢 is fixed-parameter tractable, then there is such a class ${\mathcal {G}}^{\prime }$ that is recursive.

Proof

Fix a Turing machine M that enumerates 𝒢. Let the order in which the S-hypergraphs of 𝒢 are enumerated by M be $(\mathcal {H}_{1},S_{1}),$ $(\mathcal {H}_{2},S_{2}), \ldots$. Then define ${\mathcal {G}}^{\prime }$ as containing the S-hypergraphs $(\mathcal {H}_{i}^{\prime },S_{i}^{\prime })$ where $\mathcal {H}_{i}^{\prime }$ is the disjoint union of the hypergraphs $\mathcal {H}_{1}, \ldots , \mathcal {H}_{i}$ and $S_{i}^{\prime }:= \bigcup _{j\in [i]} S_{i}$.

We claim that ${\mathcal {G}}^{\prime }$ is recursive. Indeed the definition of ${\mathcal {G}}^{\prime }$ directly gives an algorithm that enumerates the elements of ${\mathcal {G}}^{\prime }$ ordered by size. This yields an algorithm to decide membership in ${\mathcal {G}}^{\prime }$: Given an input (𝓗, S), enumerate the elements of ${\mathcal {G}}^{\prime }$ until (𝓗, S) is found or an element that has more vertices than (𝓗, S) is enumerated. The treewidth of 𝒢 is trivially unbounded.

Finally, we claim that #CQ on ${\mathcal {G}}^{\prime }$ is fixed-parameter tractable. Given an input $\Phi :=({\mathcal {A}}, \phi )$ first check if the associated S-hypergraph (𝓗, S) is in ${\mathcal {G}}^{\prime }$. If not, stop. It yes, the query ϕ must decompose into subqueries ϕ ₁, … , ϕ _i such that for eachj ∈ [i] the query ϕ _j has the S-hypergraph $(\mathcal {H}_{j}, S_{j})$ and the ϕ _j have disjoint variable sets. Using the enumerating machine M we can compute such a decomposition. Now since #CQ on 𝒢 is fixed-parameter tractable we can solve the instances $\Phi _{j}:=({\mathcal {A}}, \phi _{j})$ in time g(|ϕ _j |)∥Φ _j ∥^c for a computable function g and a constant c. It follows that $|\phi ({\mathcal {A}})| = \prod _{j\in [i]} |\phi _{j}({\mathcal {A}})|$ can be computed in time $\sum _{j\in [i]} g(|\phi _{j}|)\|\Phi _{j}\|^{c} \le |\phi | g(|\phi |) \|\Phi \|^{c}$ and thus #CQ on ${\mathcal {G}}^{\prime }$ is fixed-parameter tractable. □

Proof of Theorem 12

The direction 1 → 2 is trivial. Furthermore, 3 → 1 follows directly from Corollary 2. So it remains only to show 2 → 3.

By way of contradiction, we assume that there is a recursively enumerable class 𝒢 of S-hypergraphs such that counting solutions to #CQ-instances, whose S-hypergraph are in 𝒢, is fixed parameter tractable, but 3 is not satisfied by 𝒢. From Theorem 9 we know that the S-starsize of 𝒢 must be bounded, so it follows that the treewidth of 𝒢 is unbounded. With Observation 13 we may assume that 𝒢 is recursive.

We construct a class ${\mathcal {G}}^{\prime }$ of hypergraphs as

$${\mathcal{G}}^{\prime}:=\{{\mathcal{H}} \mid ({\mathcal{H}}, S)\in {\mathcal{G}}\}. $$

Clearly ${\mathcal {G}}^{\prime }$ is recursive and of unbounded treewidth. We will show that p- CQ on ${\mathcal {G}}^{\prime }$ is fixed-parameter tractable. This is a contradiction with Theorem 11.

Because 𝒢 is recursive, there is an algorithm that for each 𝓗 in ${\mathcal {G}}^{\prime }$ constructs an S-hypergraph (𝓗, S) in 𝒢. For example, one can simply try all vertex sets S and check if (𝓗, S) is in 𝒢. Let $f(\mathcal {H})$ be the number of steps the algorithm needs on input 𝓗. The function $f(\mathcal {H})$ is well defined and computable. We then define $g:\mathbb {N} \rightarrow \mathbb {N}$ by setting $g(k) := \max _{\mathcal {H}}(f(\mathcal {H}))$, where the maximum is over all hypergraphs 𝓗 of size k in ${\mathcal {G}}^{\prime }$. The function g is well defined and computable, because ${\mathcal {G}}^{\prime }$ is recursive. Thus for each 𝓗 in ${\mathcal {G}}^{\prime }$ we can compute in time $g(|\mathcal {H}|)$ an S-hypergraph (𝓗, S) in 𝒢.

Now let $\Phi =({\mathcal {A}},\phi )$ be a CQ-instance with hypergraph 𝓗 in ${\mathcal {G}}^{\prime }$. To solve it we first compute (𝓗, S) as above and construct a CQ-instance $\Psi = ({\mathcal {A}},\psi )$ with (𝓗, S) as associated S-hypergraph for ψ by adding existential quantifiers for all variables not in S. Obviously Φ has solutions if and only if Ψ has one. But by assumption the solutions of Ψ can be counted in time h(|ψ|)∥Ψ∥^O(1) for some computable function h, so Φ can be decided in time (g(|ϕ|)+h(|ϕ|))∥Φ∥^O(1). Thus p- CQ on ${\mathcal {G}}^{\prime }$ is fixed-parameter tractable. This is the desired contradiction to Theorem 11. □

We remark that Dalmau and Jonsson in [12] characterize the tractable classes of quantifier free queries for #CQ by bounded treewidth. This result is proved under the weaker assumption #W[1] ≠ FPT. Showing a version of this for general #CQ seems under that assumption is likely hard since our case also contains decision problems (e.g., #CQ with no free variables).

5.2 A Characterization by Elimination Orders

While the characterization of Theorem 12 is great because it completely characterizes the tractable classes of S-hypergraphs for #CQ, it has the somewhat unpleasant property that we have to bound two different parameters of the hypergraphs instead of just one. Also, it is not clear how robust and natural the defined classes of hypergraphs are. In contrast to this, treewidth is a very robust notion that has many equivalent definitions.

In this section we improve the situation by showing that there is a notion of elimination width for S-hypergraphs that is equivalent to the combination of treewidth and S-star size.

Recall the notion of elimination orders from Section 2.6.1.

Definition 15

Let (G, S) be an S-graph. We define an elimination order of an S-graph π of an S-graph (G, S) as an elimination order of G = (V, E) such that for each pair v ∈ S, u ∈ V∖S such that uv is an edge in the fill-in graph G _π we have π(u) < π(v).

The elimination width of an S-graph elim-width(G, S) of (G, S) is defined as the minimum width taken over all elimination orders of (G, S).

The elimination width $\mathrm {elim\text {-}width}({\mathcal {H}}, S)$ of an S-hypergraph (𝓗, S) is defined as the elimination width of its primal S-graph (see Definition 7). By $\mathcal {H}_{P,\pi }$ we denote the fill-in graph of the primal graph $\mathcal {H}_{P}$ of 𝓗 with respect to π.

Remark 1

Observe that for every S-graph (G, S) we have

$$\mathrm{elim\text{-}width}(G,S)\ge \mathrm{elim\text{-}width}(G), $$

because every elimination order of (G, S) is an elimination order of G.

Proposition 1

Let 𝒢 be a class of S-hypergraphs. Then the following statements are equivalent:

• The treewidth and the S-star size of the S-hypergraphs in 𝒢 are bounded by a constant c.

• The elimination width of the S-hypergraphs in 𝒢 is bounded by a constant c′.

The proof of Proposition 1 is somewhat lengthy, so we prove it in two individual lemmas.

Lemma 17

Let (𝓗, S) be an S-hypergraph of elimination width k. Then the treewidth of 𝓗 is at most k and the S-star size of (𝓗, S) is at most k + 1.

Proof

From Remark 1 and Lemma 4 it follows directly that the treewidth of 𝓗 is at most k. Thus we only have to show the bound on the S-star size of (𝓗, S). To this end, we define an S-path (P, S) as a path whose end vertices are in S but all other vertices are not in S.

Claim 2

Let u, v be the end vertices of an S-path (P, S) with P = ux ₁ …x _ℓ v. Then for every elimination order π of (P, S) we have π(v) > π(x _i ) and π(u) > π(x _i ) for all i ∈ [ℓ]. Furthermore, uv is an edge of the fill-in graph P _π .

Proof

We prove this by induction on ℓ. For ℓ = 0 there is nothing to show.

Now let ℓ ≥ 1. Let x _j be the vertex for which π is minimal, i.e., π(x _j )≤π(x _i ) for all i∈[ℓ]. By the definition of elimination orders we have π(x ₁)<π(u) and π(x _ℓ )<π(v), so π(x _j )< min(π(v),π(u)). Let P′ be the path that we get from P when deleting x _j and connecting x _j−1 and x _j+1 by an edge. P′ is a subgraph of the fill-in graph P _π and π induces an elimination order on P′ by π′ (w) := π(w) − 1. It follows that $P^{\prime }_{\pi ^{\prime }}$ is a subgraph of P _π . By induction π′(v)>π′(x _i ) and π′(u)>π′(x _i ) for all i∈[ℓ]∖{j} and thus π(v) > π(x _i ) and π(u) > π(x _i ) for all i∈[ℓ]. Furthermore, by induction u v is an edge of $P^{\prime }_{\pi ^{\prime }}$ and thus also of P _π . This completes the proof of the claim.

By definition of S-components, in every S-graph (G, S) every pair u, v ∈ S must be connected by an S-path.

Let ${\mathcal {H}}_{P}=(V, E_{P})$ be the primal graph of 𝓗. Let 𝓗′ be an S-component of 𝓗 with primal S-graph $\mathcal {H}_{P}^{\prime }=(V^{\prime }, E_{P}^{\prime })$ and let S′ := S ∩ V′.

Let π be an optimal elimination order of (𝓗, S) of width k. Then π induces for every subgraph 𝓗″ an elimination order of 𝓗″ of width at most k. To ease notation we will not differentiate between π and these induced elimination orders and simply call π an elimination order of all subgraphs, too.

As already remarked, all pairs u, v ∈ S′ are connected by S-paths in ${\mathcal {H}}_{P}^{\prime }$. The fill-in graph of every subgraph of $\mathcal {H}^{\prime }_{P}$ is a subgraph of the fill-in graph $\mathcal {H}^{\prime }_{P,\pi }$ of $\mathcal {H}^{\prime }_{P}$. Thus by Claim 2 we have that the vertices in S′ form a clique in $\mathcal {H}^{\prime }_{P,\pi }$. Because π has width k, it follows that |S′| ≤ k + 1. Hence the S-star size of 𝓗′ is at most k + 1. This completes the proof of Lemma 17.

For the other direction of Proposition 1 we will use the following lemma.

Lemma 18

Let (𝓗, S) be an S-hypergraph of treewidth at most c and S-star size at most k. Then every S-component of 𝓗 contains at most k(c + 1) vertices from S.

Proof

We prove this by induction on the S-star size k while keeping the treewidth fixed to c. If the S-star size is k = 1, then in every S-component all vertices from S are adjacent. But then they induce a clique in the primal graph of 𝓗 and thus by Lemma 2 there may be at most c + 1 of them.

Let now k > 1. Consider an S-component 𝓗′ of 𝓗. The graph ${\mathcal {H}}^{\prime }_{P}[S]$ has at most treewidth c because it is an induced subgraph of $\mathcal {H}^{\prime }_{P}$ which has by assumption treewidth at most c. By Lemma 3, there is a vertex v in $\mathcal {H}^{\prime }_{P}[S]$ of degree at most c. If follows that v has at most c neighbors in S in 𝓗′. Let 𝓗″ be the hypergraph we get from $\mathcal {H}^{\prime }=(V^{\prime }, E^{\prime })$ by deleting v and all of its neighbors in S. We claim that $(\mathcal {H}^{\prime \prime },S\cap V^{\prime })$ has S-star size at most k − 1.

Assuming this is false, there are k independent vertices v ₁, … , v _k ∈ S in 𝓗″. But then v ₁, … , v _k ,v are k + 1 independent vertices from S in 𝓗′, so the S-star size of 𝓗 is at most k + 1 which contradicts the assumption.

So the S-star size of 𝓗″ is indeed bounded by k − 1. By induction 𝓗″ contains at most (k − 1)(c + 1) vertices from S, and since we deleted at most c + 1 vertices during the construction of 𝓗″ we get that 𝓗′ contains at most k(c + 1) vertices from S.

We now prove the second direction of Proposition 1

Lemma 19

Let (𝓗, S) be an S-hypergraph such that the treewidth and the S-star size of (𝓗, S) are bounded by $c\in \mathbb {N}$. Then the elimination width of (𝓗, S) is at most (c + 1)³ + (c + 1)².

Proof

Let $({\mathcal {T}}, (\chi _{t})_{t\in T})$ be a tree decomposition of ${\mathcal {H}}=(V,E)$ of minimal width ℓ. Let S(v) for every v ∈ V∖S be the set of vertices from S in the S-component of v. For every t ∈ T we construct a new bag $\chi _{t}^{\prime }$ as

$$\chi_{t}^{\prime}:= \chi_{t} \cup \bigcup_{v\in (V\setminus S)\cap \chi_{t}} S(v). $$

Because the S-star size of 𝓗 is at most c we get by Lemma 18 that |S(v)| ≤ c(ℓ+1). It follows with ℓ ≤ c that

$$\begin{array}{@{}rcl@{}} |\chi_{t}^{\prime}| \le |\chi_{t}| + \sum\limits_{v\in (V\setminus S)\cap \chi_{t}}|S(v)| &\le& (\ell+1) + (\ell+1) c (\ell+1)\\ &\le& (\ell+1)(c+ 1) (\ell+1) \\ &\le& (c+ 1)^{3} \end{array} $$

It is easy to see that $({\mathcal {T}}, (\chi _{t}^{\prime })_{t\in T})$ is a tree decomposition. Remember that for each t ∈ T the tree $\mathcal {T}_{t}$ is the subtree of 𝓣 with t as its root. Let V _t be the set of vertices appearing in the bags $\chi _{t^{\prime }}^{\prime }$ of $\mathcal {T}_{t}$. For each y ∈ V let r(y) be the t ∈ T with $y\in \chi _{t}^{\prime }$ that is nearest to the root of 𝓣

Claim 3

There exists t∈T such that $\emptyset \ne V_{t}\setminus S \subseteq \chi _{t}^{\prime }$ with a vertex y ∈ V _t ∖S with t = r(y).

Proof

We find t and y by descending in ${\mathcal {T}}$. Let r be the root of ${\mathcal {T}}$. If $V_{r}\setminus S\subseteq \chi _{r}^{\prime }$ we are done. Otherwise let t _i be a child of r such that $V_{t_{i}} \setminus S\nsubseteq \chi _{r}^{\prime }$. Now check if $V_{t_{i}} \setminus S\subseteq \chi _{t_{i}}^{\prime }$ and if not go deeper in $\mathcal {T}$. Let t be the first vertex on this descent with $V_{t}\setminus S \subseteq \chi _{t}^{\prime }$. Then $\chi _{t}^{\prime }$ must contain a vertex y that is not in $\chi _{t^{\prime }}^{\prime }$ where t′ is the parent of t in $\mathcal {T}$. But then r(y)=t as desired.

We construct an elimination order π of 𝓗 inductively as follows, starting from the empty elimination order: While any bag of the tree decomposition $(\mathcal {T}, (\chi _{t}^{\prime })_{t\in T})$ contains a vertex from V∖S, do the following: Choose by Claim 3 t ∈ T such that $\emptyset \ne V_{t}\setminus S\subseteq \chi _{t}^{\prime }$ with a vertex y ∈ V _t ∖S with t = r(y), delete y from 𝓗 and all bags and add y as the next vertex to the elimination order π.

When the vertices from V∖S have all been deleted, we proceed with the vertices in S in a similar fashion: While there is a non-empty bag, choose one t ∈ T with $\emptyset \ne S\cap V_{t}\subseteq \chi _{t}^{\prime }$ and y ∈ S ∩ V _t with r(y) = t, delete y and add y as the next vertex in π. Again, such t and y can always be found.

All vertices in V∖S appear before all vertices in S in π, so π is an elimination order of (𝓗, S). We will now bound the width of π.

Claim 4

Let x,y∈V with x,y∈V∖S or x,y∈S such that there exists t∈T with $x,y\in \chi _{t}^{\prime }$ . If x is higher-numbered than y with respect to π, then x∈χ _r(y) .

Proof

x and y appear in a common bag $\chi _{t}^{\prime }$ and thus x∈V _r(y). But x is higher-numbered, so y was deleted before x. Hence, when y was chosen to be deleted the vertex x was still in V _r(y). But then x∈χ _r(y) because otherwise y would not have been chosen for deletion.

Claim 5

• a) For every vertex y ∈ V∖S the neighbors of y in ${\mathcal {H}}_{P,\pi }$ are vertices of the same S-component as y.

• b) When a vertex y ∈ V∖S is deleted, the bag $\chi _{r(y)}^{\prime }$ contains all higher-numbered neighbors of y in the fill-in graph $\mathcal {H}_{P,\pi }$ that are in V∖S.

• c) When a vertex y ∈ S is deleted, the bag $\chi _{r(y)}^{\prime }$ contains all higher-numbered neighbors of y in the fill-in graph $\mathcal {H}_{P,\pi }$.

Proof

We first prove a) and b) by induction along the elimination order π. So let first y be the vertex with π(y)=1. We claim that the higher-numbered neighbors of y in $\mathcal {H}_{P,\pi }$ are simply the neighbors of y in $\mathcal {H}_{P}$. Certainly, these are all higher-numbered. Also, in the construction of $\mathcal {H}_{P,\pi }$ from $\mathcal {H}_{P}$ edges incident to y may only be added by lower-numbered vertices. As there are none for y, all neighbors of y in $\mathcal {H}_{P,\pi }$ are already neighbors in $\mathcal {H}_{P}$. This proves the induction start for a). For b) consider a neighbor x∈V∖S of y in $\mathcal {H}$. By the definition of tree decompositions x and y must be in one common bag $\chi _{t}^{\prime }$. With Claim 4 it follows that x∈χ _r(y).

Consider now y∈V∖S with π(y)>1. All neighbors x∈V∖S of y in ${\mathcal {H}}_{P,\pi }$ are either already neighbors of y in $\mathcal {H}$ and thus in the same S-component as y or they are neighbors that originate from edges added in the construction of $\mathcal {H}_{P,\pi }$ from $\mathcal {H}_{P}$. In the latter case the edge x y must have been added because of a common lower-numbered neighbor v of y and x. Because v is lower-numbered than y it follows that v∈V∖S. By induction all higher-numbered neighbors of v in $\mathcal {H}_{P,\pi }$ are in the same S-component as v in $\mathcal {H}$, so y, x and v are all vertices of the same S-component which completes the proof of a).

Now let x∈V∖S be a higher-numbered neighbor of y∈V∖S in ${\mathcal {H}}_{P,\pi }$. Consider first the case that x y is already an edge in $\mathcal {H}_{P}$. Then there is a bag $\chi _{t}^{\prime }$ such that $x,y\in \chi _{t}^{\prime }$. With Claim 4 we get x∈χ _r(y) as desired. If x and y are not neighbors in $\mathcal {H}_{P}$, then there is a lower-numbered vertex v of x and y in $\mathcal {H}_{P,\pi }$ that led to the introduction of the edge x y. By induction x,y∈χ _r(v). We conclude with Claim 4 that x∈χ _r(y). This completes the proof of b).

To prove c) consider a vertex y∈S. Let x be a higher-numbered neighbor of y in ${\mathcal {H}}_{P,\pi }$. By construction x∈S. Assume first that x and y are in a common S-component. Let v∈V∖S be a vertex of this S-component, then, by construction of $(\mathcal {T},(\chi ^{\prime }_{t})_{t\in T})$, the vertices x and y both appear in any bag $\chi _{t}^{\prime }$ that contains v. We conclude with Claim 4 that x∈χ _r(y). If x and y are not in a common S-component, then the vertex v that leads to the introduction of the edge x y must be in S by a). Because v is a lower-numbered neighbor of x and y, we have by induction that x,y∈χ _r(v). By Claim 4 we get x∈χ _r(y) which completes the proof of Claim 5.

We claim that the width of π is at most (c + 1)³ + (c + 1)². As the bags $\chi _{t}^{\prime }$ have size at most (c + 1)³ + 1, every vertex y ∈ V∖S has at most (c + 1)³ higher-numbered neighbors in V∖S in $\mathcal {H}_{P,\pi }$ by Claim 5. Furthermore, y ∈ V∖S has by Claim 5 and Lemma 18 at most (c + 1)² neighbors in S in $\mathcal {H}_{P,\pi }$. Finally, y ∈ S has at most (c + 1)³ higher-numbered neighbors by Claim 5 and the bound on the size of the bags. This completes the proof of Lemma 19.

From Proposition 1 and Theorem 12 we get the following alternative characterization of S-hypergraphs of bounded arity that allow tractable #CQ.

Theorem 14

Let 𝒢 be a recursively enumerable class of S-hypergraphs of bounded arity. Assume that W[1] ≠ FPT. Then the following statements are equivalent:

• 1. #CQ on 𝒢 is solvable in polynomial time.

• 2. p-#CQ on 𝒢 is fixed-parameter tractable.

• 3. There is a constant c such that all S-hypergraphs in 𝒢 have elimination width at most c.

Let us remark that there is a similar notion of elimination width for quantified constraint satisfaction ( QCSP) which is a version of CQ in which also universal quantification is allowed. Chen and Dalmau [9] introduced this measure and showed that it characterizes the tractable classes of graphs for QCSP. We consider it as likely that an equivalent characterization of the same classes of graphs could be given by treewidth and an adapted notion of S-star size. This would probably also make it possible to get a better understanding of tractable classes of hypergraphs of unbounded arity for QCSP by exchanging treewidth for e.g., generalized hypertree width.

6 Computing Star Size

In this section we consider the problem of computing the quantified star size of hypergraphs that have small width for the decomposition techniques defined in Section 2.6. Note that the computation of quantified star size is not strictly necessary for tractable counting. The algorithm of Section 4 does not need to compute the S-star size for graphs of width k but only for acyclic hypergraphs which can be done with the help of Lemma 14 (see [15] for the details). Still it is of course desirable to know the quantified star size of an instance before applying the counting algorithm, because quantified star size has an exponential influence on the runtime.

We show that for all decomposition techniques considered in this paper the quantified star size can be computed rather efficiently, in time roughly |V|^O(k) where k is the width of the input. For small values of k, this bound is reasonable. We then proceed by showing that, on the one hand, for some decomposition measures such as treewidth or hingetree width, the computation of quantified star size is even fixed parameter tractable parameterized by the width. On the other hand, we show that for decomposition measures above hypertree width it is unlikely that fixed parameter tractability can be obtained (under standard assumptions).

Instead of tackling quantified star size directly, we consider the combinatorially less complicated notion of independent sets. This is justified by the following observation:

Observation 15

Let β be any decomposition technique considered in this paper. Then, for every $k\in \mathbb {N}$, computing the S-star size of S-hypergraphs of β-width at most k polynomial time Turing-reduces to computing the size of a maximum independent set for hypergraphs of β-width at most k. Furthermore, there is a polynomial time many one reduction from computing the size of a maximum independent set in hypergraphs of β-width at most k to computing the S-star size of hypergraphs of β-width at most k + 1.

Proof

By definition computing S-starsize reduces to the computation of independent sets of S-components. S-components are induced subhypergraphs, so we get the first direction from Observation 5.

For the other direction let ${\mathcal {H}}=(V,E)$ be a hypergraph for which we want to compute the size of a maximum independent set. Let x ∉ V. We construct the hypergraph 𝓗′ of vertex set V′ = V ∪ {x} and edge set E′ = {e ∪ {x}∣e ∈ E} and set S := V. The hypergraph is one single S-component, because x is in every edge. Furthermore, the S-starsize of 𝓗′ is obviously the size of a maximum independent set in 𝓗. It is easy to see that the construction increases the treewidth of the hypergraph by at most 1 and does not increase the β-width for all other decomposition considered here at all.

Because of Observation 15 we will not talk about S-star size in this section anymore but instead formulate everything with independent sets.

6.1 Exact Computation

Proposition 2

There is an algorithm that, given a hypergraph ${\mathcal {H}}=(V,E)$ and a generalized hypertree decomposition $({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ of width k of 𝓗, computes a maximum independent set of 𝓗 in time k|V|^O(k).

Proof

We apply dynamic programming along the decomposition. Let b = (λ, χ) be a guarded block of 𝓣. Let ${\mathcal {T}}_{b}$ be the subtree of 𝓣 with b as its root. We set $V_{b} := \chi (\mathcal {T}_{b})$. Observe that I ⊆ V _b is independent in 𝓗 if and only if it is independent in $\mathcal {H}[V_{b}]$ so we do not differentiate between the two notions. For each independent set σ ⊆ χ we will compute an independent set I _{b, σ} ⊆ V _b that is maximum under the independent sets containing exactly the vertices σ from χ. Observe that because λ contains at most k edges that cover χ we have to compute at most kn^k independent sets I _{b, σ} for each b.

If b is a leaf of 𝓣, the construction of the I _{b, σ} is straightforward and can certainly be done in time k|V|^O(k).

Let now b = (λ, χ) be an inner vertex of 𝓣 with children b ₁, … , b _r and let b _i = (λ _i , χ _i ). For each independent set σ ⊆ χ we do the following: For each i, let σ _i be an independent set of χ _i such that σ ∩ χ ∩ χ _i = σ _i ∩ χ ∩ χ _i and $|I_{b_{i}, \sigma _{i}}|$ is maximal. We claim that we can set $I_{b, \sigma } := \sigma \cup I_{b_{1}, \sigma _{1}} \cup \ldots \cup I_{b_{r}, \sigma _{r}}$.

We first show that I _{b, σ} defined this way is independent. Assume this is not true, then I _{b, σ} contains x, y that are in one common edge e in $\mathcal {H}[V_{b}]$. But then x, y do not lie both in χ, because I _{b, σ} ∩ χ = σ and σ is independent. By induction x, y do not lie in one $V_{b_{i}}$ either. Assume that x ∈ χ and $y \in V_{b_{i}}$ for some i. Then certainly $x\notin V_{b_{i}}$ and y ∉ χ. But the edge e must lie in one block χ′. Because of the connectivity condition for y, the guarded block (λ′, χ′) must lie in the subtree with root b _i , which contradicts x ∈ e. Finally, assume that $x\in V_{b_{i}}$ and $y \in V_{b_{j}}$ for i≠j and x, y ∉ χ. Then x and y cannot be adjacent because of the connectivity condition. This shows that I _{b, σ} is indeed independent.

Now assume that I _{b, σ} is not of maximum size and let J ⊆ V _b be an independent set with |J|>|I _{b, σ} | and J ∩ χ = σ. Because J and I _{b, σ} are fixed to σ on χ there must be a b _i such that $|J \cap V_{b_{i}}| > |I_{b_{i}, \sigma _{i}}|$. This contradicts the choice of σ _i . So I _{b, σ} is indeed of maximum size.

Because each block has at most k|V|^k independent sets, all computations can be done in time k|V|^O(k).

6.2 Parameterized Complexity

While the algorithm in the last section is nice in that it is a polynomial time algorithm for fixed k, it is somewhat unsatisfying for some decomposition techniques: If we can compute the decomposition quickly, we would ideally want to be able to compute the S-star size efficiently, too. Naturally we cannot expect a polynomial time algorithm independent of the width k for any of the decomposition techniques we consider, because computing maximum independent sets is NP-hard. Instead, we can hope for independent set to be at least fixed-parameter tractable with respect to k. We will show that for general hypertree width even this is unlikely, because independent set parameterized by generalized hypertree width is W[1]-hard. More positively, we will show that computing maximum independent sets is fixed-parameter tractable for some other decomposition techniques, in particular tree decompositions and hingetree decompositions.

Lemma 20

Computing maximum independent sets on hypergraphs is W[1]-hard parameterized by generalized hypertree width.

Proof

We will show a parameterized many-one reduction from the problem p-IndependentSet defined as follows:

Because p-IndependentSet is well known to be W[1]-hard, this suffices to establish W[1]-hardness of independent sets on hypergraphs parameterized by generalized hypertree width.

So let G = (V, E) be a graph and let k be a positive integer. We construct a hypergraph ${\mathcal {H}}=(V^{\prime }, E^{\prime })$ in the following way: For each vertex v the hypergraph 𝓗 has k vertices v ₁, … , v _k . For i = 1, … , k we have an edge V _i := {v _i ∣v ∈ V} in E′. Furthermore, for each v ∈ V we add an edge H _v := {v _i ∣i ∈ [k]}. Finally we add the edge sets E _ij := {v _i u _j ∣uv ∈ E} for i, j ∈ [k]. 𝓗 has no other vertices or edges. The construction is illustrated in Fig. 7.

Fig. 7

We illustrate the construction for Lemma 20 by an example. A graph G on the left with the associated hypergraph $\mathcal {H}$ for k=4 on the right. To keep the illustration more transparent the edge sets E _{i j} are not shown except for E _1,2 and E _2,1

We claim that G has an independent set of size k if and only if 𝓗 has an independent set of size k. Indeed, if G has an independent set v ¹, … , v ^k, then ${v_{1}^{1}}, \ldots {v_{k}^{k}}$ is easily seen to be an independent set of size k in 𝓗. Now assume that 𝓗 has an independent set I of size k. Then for each v ∈ I we can choose a vertex π(v) ∈ V such that v ∈ H_π(v). Furthermore for distinct v,u ∈ I the corresponding vertices π(v),π(u) have to be distinct, too, so π(I) ⊆ V has size k. Finally, we claim that π(I) is independent in G. Assume this is not true, then there are vertices π(v) , π(u) such that π(v)π(u) ∈ E. But then vu ∈ E′ by construction which is a contradiction. So, indeed G has an independent set of size k if and only if 𝓗 has one.

From Observation 3 we get that 𝓗 has generalized hypertreewidth at most k, because V ₁, … , V _k cover V′.

Observing that the construction of 𝓗 from G can be done in time polynomial in |V| and k completes the proof.

We start our fixed-parameter tractability results with an easy observation.

Proposition 3

Given a hypergraph 𝓗 computing a maximum independent set in 𝓗 is fixed parameter tractable parameterized by the treewidth of 𝓗.

This can be seen either by applying an optimization version of Courcelle’s Theorem [11] or by straightforward dynamic programming. Interestingly, one can show the same result also for bounded hingetree width. For this decomposition technique blocks are of unbounded size which makes the dynamic programming in the proof far more involved than for treewidth.

Proposition 4

Given a hypergraph ${\mathcal {H}}=(V,E)$ of hingetree width k, a maximum independent set in 𝓗 can be computed in time $k 2^{k^{2}} |E|^{O(1)}$. It follows that independent set is fixed parameter tractable parameterized by hingetree width.

Proof

First observe that minimum width hingetree decompositions can be computed in polynomial time by Lemma 10, so we simply assume that a decomposition is given in the rest of the proof.

The proof has some similarity with that of Proposition 2, so we use some notation from there. For guarded block (λ, χ) we will again compute maximum independent sets containing prescribed vertices. The difference is, that we can take these prescribed sets to be of size 1: because of the hingetree condition, only one vertex of a block may be reused in any independent set in the parent. The second idea is that we can use equivalence classes of vertices in the computation of independent sets in the considered guarded blocks, which limits the number of independent sets we have to consider. We now describe the computation in detail.

Let $\varXi = ({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ be a hingetree decomposition of 𝓗 of width k. Let b = (λ, χ) be a guarded block of Ξ and let b′ = (λ′, χ′) be its parent. As before, let $\mathcal {T}_{b}$ be the subtree of 𝓣 with b as its root and $V_{b} := \chi (\mathcal {T}_{b})$. Set $\mathcal {H}_{b} := (V_{b}, E_{b})$ with $E_{b} := \bigcup \lambda ^{*}$ with the union being over all guarded blocks in $\mathcal {T}_{b}$. The main idea is to iteratively compute, for all vertices v ∈ χ′ ∩ χ, a maximum independent set J _{v, b} in $\mathcal {H}_{b} = (V_{b}, E_{b})$ containing v. Furthermore, we also compute an independent set J _{∅, b} that contains no vertices of χ′ ∩ χ. Note that, since $\chi \subseteq \bigcup _{e\in \lambda } e$, there are no isolated vertices in χ and the size of a maximum independent set is bounded by k in each block.

For a node b = (λ, χ), we organize the vertices in χ into at most 2^k equivalence classes by defining v and u to be equivalent if they lie in the same subset of edges of λ. The equivalence class of v is denoted by c(v). For each class, a representant is fixed. We denote by $\bar {v}$, the representant of the equivalence class of v and by $\bar {\chi }\subseteq \chi$, the restriction of χ on these at most 2^k representants.

Let first b be a leaf. We first compute independent sets on $\bar \chi$. Observe that the independent sets are invariant under the choice of representants. For each equivalence class c(v), we compute $J_{\bar {v},b}\subseteq \bar \chi$ as a maximum independent set containing $\bar {v}$. Computing the classes and a choice of maximum independent sets containing each $\bar {v}$ can be done in time $k 2^{k^{2}}$ because independent sets cannot be bigger than k. Clearly, J _{v, b} , a maximum independent set containing v, can be easily computed from the set $J_{\bar {v},b}$. Thus, one can compute all the J _{v, b} in time $k 2^{k^{2}}n$. The computation of J _∅,b can be done on representants, too, by simply excluding the vertices from χ′ ∩ χ.

Let b now be an inner vertex and b ₁,b₂, ... , b _m be its children with b _i = (λ _i , χ _i ), i ∈ [m]. We again consider equivalence classes on χ. Fix v ∈ χ and compute the list $L_{\bar {v},b}$ of all independent sets $\sigma \subseteq \bar \chi$ containing $\bar {v}$. Fix now $\sigma \in L_{\bar {v},b}$. We first compute a set $J_{v,b}^{\sigma }$ as a maximum independent set of $\mathcal {H}_{b}$ containing v and whose vertices in χ have the representants σ. We will distinguish for a given vertex $\bar {u}\in \sigma$ if it is the representant of a vertex belonging to the block of some (or several) children of b or if it represents vertices of $\chi \backslash (\bigcup _{i= 1}^{m} \chi _{i})$ only. Therefore we partition σ into σ′, σ″ accordingly:

• σ := σ′∪ σ″

• $\sigma ^{\prime } := \bar \chi \cap \{\bar {u} \mid u \in \bigcup _{i= 1}^{m} \chi _{i}\}$.

• $\sigma ^{\prime \prime }:= \bar {\chi } \backslash \{\bar {u} \mid u \in \bigcup _{i= 1}^{m} \chi _{i}\}$

Set $\sigma ^{\prime }:=\{\bar {u}_{1},...,\bar {u}_{h}\}$ with h ≤ m. Let us examine the consequences of 𝓣 being a hingetree decomposition. We have that, for all i ∈ [m], there exists e _i ∈ λ, such that χ ∩ χ _i ⊆ e _i . Thus, since σ is an independent set in $\bar {\chi }\subseteq \chi$, at most one vertex in σ′ is a representant of a vertex in χ _i . Thus

$$ \forall u\neq u^{\prime} \in \sigma \colon \chi_{i}\cap \mathbf{c}(u)= \emptyset \vee \chi_{i}\cap \mathbf{c}(u^{\prime})= \emptyset . $$

(1)

We denote by S _i = {j∣c(u _i ) ∩ χ _j ≠ ∅} and by $S=[m]\backslash \bigcup S_{i}$. By (1) the sets S ₁,...,S _h , S form a partition of [m]. To construct $J_{v,b}^{\sigma }$, we now determine for each i ≤ h, which vertex u of c(u _i ) can contribute the most, by taking the union of all the maximum independent sets $J_{u,b_{j}}$,j ∈ S _i , that u induces at the level of the children of b.

For each fixed u ∈ c(u _i ), let

$$I_{i,u}= \{u\}\cup \bigcup_{j\in S_{i}} J_{u,b_{j}}, $$

where we set $J_{u,b_{j}}:=J_{\emptyset ,b_{j}}$ if u ∉ χ _j . Let then I _i = I_i,u for some u ∈ c(u _i ) for which the size of I _i,u is maximal.

The set $J_{v,b}^{\sigma }$ is now obtained as follows depending on whether $\bar {v}\in \sigma ^{\prime \prime }$ or $\bar {v}\in \sigma ^{\prime }$. If $\bar {v}\in \sigma ^{\prime \prime }$, we claim that $J_{v,b}^{\sigma }$ can be chosen as

$$J_{v,b}^{\sigma}:=\{v\} \cup (\sigma^{\prime\prime}\backslash \{\bar{v}\} ) \cup \bigcup_{i=1}^{h} I_{i} \cup \bigcup_{i\in S} J_{\emptyset,b_{i}}. $$

If $\bar {v}\in \sigma ^{\prime }$, say $\bar {v}=u_{1}$, we claim that $J_{v,b}^{\sigma }$ can be chosen as

$$J_{v,b}^{\sigma}:=\sigma^{\prime\prime} \cup\bigcup_{j\in S_{1}: v\in \chi_{j}} J_{v,b_{j}}\cup\bigcup_{j\in S_{1}: v\notin \chi_{j}} J_{\emptyset,b_{j}} \cup \bigcup_{i=2}^{h} I_{i} \cup \bigcup_{i\in S} J_{\emptyset,b_{i}}. $$

The set J _{v, b} is taken as one of the sets $J_{v,b}^{\sigma }$ of maximal size for a σ ∈ L _{v, b} . To compute J _∅,b, the arguments are similar.

We first show that all J _{v, b} are indeed independent sets in ${\mathcal {H}}_{b}$. Clearly, it is enough to prove this for any $J_{v,b}^{\sigma }$. There will be no reason to distinguish whether $\bar {v}\in \sigma ^{\prime \prime }$ or $\bar {v}\in \sigma ^{\prime }$, because our arguments will apply to all $J_{v, b}^{\sigma }$ independent of the choice of a distinguished element v. We will make extensive use of the two following facts.

• Let j, j′ ∈ [m] and $I\subseteq V_{b_{j}},I^{\prime }\subseteq V_{b_{j^{\prime }}}$ independent sets of $\mathcal {H}_{b_{j}}$ and $\mathcal {H}_{b_{j}^{\prime }}$ respectively. By the connectivity condition for tree decomposition we have

  $$I\cap I^{\prime} \subseteq \chi_{j}\cap \chi_{j^{\prime}}\cap \chi. $$

  This permits to investigate the intersection of two independent sets I, I′ by looking at their restriction on χ.

• Let now $I\subseteq V_{b_{j}}$ be an independent set of ${\mathcal {H}}_{b_{j}}$. Then, I remains an independent set in $\mathcal {H}_{b}$. Indeed, suppose there is a e ∈ E _b ∖${E}_{b_{j}}$ containing two vertices y ₁, y ₂ ∈ I. Since all edges must belong to a guard, there exists a node b^∗ = (λ ^∗, χ ^∗) such that e ∈ λ ^∗. Then, since in a hingetree decomposition we have $\chi ^{*}=\bigcup \lambda ^{*}$, then {y ₁, y ₂} ⊆ e ⊆ χ ^∗. But then, by the connectivity condition it follows that {y ₁, y ₂} ⊆ χ. Hence, by the intersection property of hingetree decomposition, there exists e _j ∈ χ _j such that

  $$\{y_{1},y_{2}\}\subseteq \chi \cap \chi_{j} \cap e_{j} $$

  which implies that y ₁ and y ₂ are adjacent in $\mathcal {H}_{b_{j}}$. Contradiction.

We now start the proof that $J_{v,b}^{\sigma }$ is independent incrementally. Let i ∈ [h], u ∈ c(u _i ) andj ∈ S _i and consider the set $I:=J_{u,b_{j}}$. By induction, the set I is independent in $\mathcal {H}_{b_{j}}$. By the hingetree condition, there exists e _j ∈ λ _j such that χ ∩ χ _j ⊆ e _j . By the connectivity condition, this implies χ ∩ I ⊆ e _j . Then, since I is an independent set, no two vertices of χ can belong to I, i.e., |χ ∩ I| ≤ 1. The connectivity condition also implies that, for j′ ≠ j, $V_{b_{j^{\prime }}}\cap I\subseteq \chi \cap \chi _{j}$, hence $|V_{b_{j^{\prime }}}\cap I|\leq 1$ and I is an independent set of $\mathcal {H}_{b}$. Finally, the set $I_{i}=\bigcup _{j\in S_{i}} J_{u,b_{j}}$ is also an independent set of $\mathcal {H}_{b}$, since for any distinct j, j′ ∈ S _i :

$$J_{u,b_{j}}\cap J_{u,b_{j^{\prime}}} \subseteq \chi_{j}\cap \chi_{j^{\prime}} \cap \chi \subseteq e_{j}. $$

Hence $J_{u,b_{j}}\cap J_{u,b_{j^{\prime }}}$ contains at most one vertex (which is in χ and could then only be u).

Let now i, i′ ∈ [m] be distinct. By the arguments above, I _i (resp. $I_{i^{\prime }}$) contains at most one element u (resp. u′) such that u ∈ c(u _i ) (resp. $u^{\prime }\in {\mathbf {c}({u_{i^{\prime }}})}$). By Eq. 1, we have that the two classes are distinct and that $u_{i}\neq u_{i^{\prime }}$. But $u_{i},u_{i^{\prime }}\in \sigma$ and σ is independent in χ. Hence, $u_{i},u_{i^{\prime }}$ cannot be adjacent in $\mathcal {H}_{b}$. Consequently,

$$ \bigcup_{i=1}^{h} I_{i} $$

is an independent set in ${\mathcal {H}}_{b}$.

Let j ∈ S. $J_{\emptyset ,b_{j}}$ is independent in ${\mathcal {H}}_{b_{j}}$ and $J_{\emptyset ,b_{j}}\subseteq V_{b_{j}}\backslash \chi$. Hence, $J_{\emptyset ,b_{j}}$ is independent in $\mathcal {H}_{b}$. This also implies that, given j′ ∈ [m] distinct from j, $J_{\emptyset ,b_{j}}\cap V_{b_{j^{\prime }}}=\emptyset$. Thus,

$$\bigcup_{i=1}^{h} I_{i} \cup \bigcup_{i\in S} J_{\emptyset,b_{i}}. $$

is independent in ${\mathcal {H}}_{b}$.

Finally, by construction, for all i ∈ [h], I _i ∩ χ = {u} with $\bar {u}=\bar {u}_{i}\in \sigma ^{\prime }$. Also σ = σ′ ∪ σ″ is independent in χ hence in $\mathcal {H}_{b}$. No vertices y ₁ ∈ I _i and y ₂ ∈ σ″ can be adjacent because, again, this would imply that {y ₁, y ₂} ⊆ χ and contradict the fact that $\bar {y}_{1},\bar {y}_{2}$ are independent in σ. Thus $J_{v,b}^{\sigma }$ is independent.

We now prove that J _{v, b} is of maximum size. Observe that it suffices to show this again for each $J_{v,b}^{\sigma }$. Each maximum independent set J of $\mathcal {H}_{b}$ that contains v and whose vertices in χ have exactly the representants σ can be expressed as τ∪J₁ ∪ J ₂ ∪... ∪ J _m . Here τ ⊆ χ is an independent set of b containing v and whose representants are σ. Furthermore, J _i is an independent set of $\mathcal {H}_{b}$ that contains only vertices of $V_{b_{i}}$. The set J _i may only contain one vertex u _i from χ ∩ χ _i . But then exchanging J _i for $J_{u_{i}, b_{i}}$ may only increase the size of the independent set, so we can assume that I has the form $\tau \cup J_{u_{1}, b_{i}} \cup J_{u_{2}, b_{2}} \cup \ldots \cup J_{u_{m}, b_{m}}$ where u _i may also stand for ∅.

Assume now that $J_{v,b}^{\sigma }$ is not a maximum independent set, i.e., there is an independent set J containing v whose vertices in χ have the representants σ and J is bigger than $J_{v,b}^{\sigma }$. Then one of four following things must happen:

• There is an i such that v ∈ χ _i and $J\cap V_{b_{i}}$ is bigger than $J_{v,b_{i}}$. But this case cannot occur by induction.

• v = u ₁ and there is aj ∈ S ₁ such that v ∉ χ _j and $|J\cap V_{b_{j}}|> |J_{\emptyset ,b_{j}}|$. By induction we know that $J_{\emptyset ,b_{j}}$ is optimal under all independent sets of $\mathcal {H}_{b_{j}}$ not containing any vertex of χ _j ∩ χ, so there must be a vertex u ∈ J ∩ χ ∩ χ _j . Since J is independent, v and u share no edge in λ and then $\bar {v} \ne \bar {u}$. Sincej ∈ S ₁, it holds that c(v) ∩ χ _j ≠ ∅ and by Eq. 1, c(u) ∩ χ _j = ∅. Contradiction.

• There is an i ∈ S such that $J\cap V_{b_{i}}$ is bigger than $J_{\emptyset , b_{i}}$. But from i ∈ S it follows by definition that χ ∩ χ _i ∩ J = ∅, so this case can not occur by induction, either.

• There is an i ∈ [h] such that $|J\cap (\bigcup _{j\in S_{i}} V_{j})|> |I_{i}|$. We claim that $(\bigcup _{j\in S_{i}} \chi _{j}) \cap \chi \cap J$ contains only one vertex. Assume there are two such vertices x and y.By definition, $\bar {x}, \bar {y}\in \bar \tau$. Since J is independent, $\bar {x}$ and $\bar {y}$ are not adjacent in $\bar \chi$ and $\bar {x} \ne \bar {y}$. At least one of these, say y, must be in c(u _i ), because $\bar {u}_{i} \in \bar \tau$ by definition. Let $x\in V_{j^{\prime }}$ with j′ ∈ S _i , then there is a vertex w ∈ c(u _i )=c(y) in $\chi _{j^{\prime }}\cap \chi \subseteq e_{j}$ by definition of S _i . But then $\bar {x}$ and $\bar {y}$ are adjacent in $\bar \chi$ which is a contradiction.

  So there is exactly one vertex u in $(\bigcup _{j\in S_{i}} \chi _{j}) \cap \chi \cap J$. But then $|J\cap (\bigcup _{j\in S_{i}} V_{j})| > I_{i,u}$. Thus either there must be aj ∈ S _i with u ∈ V _j such that $|J\cap V_{j}|> |J_{u, b_{j}}|$ or there must be aj ∈ S _i with u ∉ V _j such that $|J\cap V_{j}|> |J_{\emptyset , b_{j}}|$. The former clearly contradicts the optimality of $J_{u, b_{j}}$, while the latter leads to a contradiction completely analogously to the second item above.

Because only $k 2^{k^{2}} n^{2}$ sets have to be considered for each guarded block, this results in an algorithm with runtime $k 2^{k^{2}} |V|^{O(1)}$.

6.3 Approximation

We have seen that computing maximum independent sets of hypergraphs with decompositions of width k can be done in polynomial time for fixed width k and that for some decompositions it is even fixed parameter tractable with respect to k. Still, the exponential influence of k is troubling. In this section we will show that we can get rid of it if we are willing to sacrifice the optimality of the solution. We give a polynomial time k-approximation algorithm for computing maximum independent sets of graphs with generalized hypertree width k assuming that a decomposition is given. We start by formulating a lemma.

Lemma 21

Let ${\mathcal {H}}=(V,E)$ be a hypergraph with a generalized hypertree decomposition $\varXi = ({\mathcal {T}}, (\lambda _{t})_{t\in T}, (\chi _{t})_{t\in T})$ of width k. Let $\mathcal {H}^{\prime }=(V,E^{\prime })$ where E′ := {χ _t ∣t ∈ T}. Let ℓ be the size of a maximum independent set in 𝓗 and let ℓ′ be the size of a maximum independent set in 𝓗′. Then

$$\frac{\ell}{k}\le \ell^{\prime} \le \ell.$$

Before we prove Lemma 21 we will show how to get the approximation algorithm from it.

Observation 16

Every independent set of 𝓗′ is also an independent set of 𝓗.

Proof

Each pair of independent vertices x, y in 𝓗′ is by definition in different blocks χ _t in 𝓗. For each edge e ∈ E there must (by definition of generalized hypertree decompositions) be a block χ such than e ⊆ χ. Thus no edge e ∈ E can contain both x and y, so x and y are independent in 𝓗 as well.

Corollary 3

There is a polynomial time algorithm that, given a hypergraph 𝓗 and a generalized hypertree decomposition of width k, computes an independent set I of 𝓗 such that $|I|\ge \frac {\ell }{k}$ where ℓ is the size of a maximum independent set of 𝓗.

Proof

Observe that 𝓗′ is acyclic by Lemma 7. By Lemma 14, we compute in polynomial time a maximum independent set I of 𝓗′ whose size by Lemma 21 only differs by a factor $\frac {1}{k}$ from ℓ. By Observation 16, we know that I is also an independent set of 𝓗.

Proof of Lemma 21

The second inequality follows directly from Observation 16.

For the first inequality consider a maximum independent set I of 𝓗. Observe that a set I′ is an independent set of 𝓗′ if and only if it is an independent set of its primal graph $\mathcal {H}^{\prime }_{P}$, so it suffices to show the same result for $\mathcal {H}^{\prime }_{P}$.

Claim 6

The graph ${\mathcal {H}}^{\prime }_{P}[I]$ has treewidth at most k−1.

Proof

First observe that vertices v that appear in no edge e ∈ E change neither the treewidth nor the generalized hypertree width of a graph or hypergraph. Thus we assume that every vertex v ∈ V is in at least one edge e ∈ E.

We construct a tree decomposition $({\mathcal {T}}^{\prime }, (\chi _{t}^{\prime })_{t\in T^{\prime }})$ of ${\mathcal {H}}^{\prime }_{P}[I]$ from Ξ as follows: We set $\mathcal {T}^{\prime }:=\mathcal {T}[T^{\prime }]$ where T′:={t∈T∣χ _t ∩I≠∅}. Furthermore, $\chi _{t}^{\prime } := \chi _{t}\cap I$ for t∈T′. For every v∈I there is an edge e∈E and t∈T such that v∈e⊆χ _t and thus $v\in \chi _{t}^{\prime }$. It follows that the bags $\chi _{t}^{\prime }$ cover I. Moreover, the connectivity condition for I is satisfied, because it is satisfied for Ξ. Finally, for each edge u v in $\mathcal {H}^{\prime }_{P}[I]$ there is a guarded block (λ _t ,χ _t ) such that u,v∈χ _t and thus $u,v\in \chi _{t}^{\prime }$. Hence, $(\mathcal {T}^{\prime }, (\chi _{t}^{\prime })_{t\in T^{\prime }})$ is indeed a tree decomposition.

Thus we only have to show $|\chi _{t}^{\prime }|\le k$. To see this, observe that for each t the bag $\chi _{t}^{\prime }\subseteq \chi _{t}$ is covered by λ _t . But the vertices in $\chi _{t}^{\prime }\subseteq I$ are independent in $\mathcal {H}$ and thus each e∈λ _t can contain only a single vertex from $\chi _{t}^{\prime }$. Thus $|\chi _{t}^{\prime }| \le |\lambda _{t}| \le k$.

Claim 7

The graph ${\mathcal {H}}^{\prime }_{P}[I]$ has an independent set I′ of size at least $\frac {|I|}{k}$.

Proof

From Claim 6 it follows with Lemma 3 that ${\mathcal {H}}^{\prime }[I]$ and all of its induced subgraphs have a vertex of degree at most k. We construct I′ iteratively by choosing a vertex of minimum degree and deleting it and its neighbors from the graph. In each round we delete at most k vertices, so we can choose a vertex in at least $\frac {|I|}{k}$ rounds. Obviously the chosen vertices are independent.

Every independent set of ${\mathcal {H}}^{\prime }_{P}[I]$ is also an independent set of ${\mathcal {H}}^{\prime }_{P}$ which completes the proof of Lemma 21.

7 Fractional Hypertree Width

In this section we extend the main results of the paper to fractional hypertree width, which is the most general notion known so far that leads to tractable CQ [23]. In particular it is strictly more general than generalized hypertree width.

Definition 16

Let ${\mathcal {H}} = (V,E)$ be a hypergraph. A fractional edge cover of a vertex set S ⊆ V is a mapping ψ : E → [0,1] such that for every vS we have $\sum _{e\in E: v\in e} \psi (e) \ge 1$. The weight of ψ is $\sum _{e\in E} \psi (e)$. The fractional edge cover number of S, denoted by $\rho _{\mathcal {H}}^{*}(S)$ is the minimum weight taken over all fractional edge covers of S.

A fractional hypertree decomposition of 𝓗 is a triple $({\mathcal {T}}, (\chi _{t})_{t\in T}, (\psi _{t})_{t\in T})$ where $\mathcal {T} = (T,F)$ is a tree, and χ _t ⊆ V and ψ _t is a fractional edge cover of χ _t for every t ∈ T satisfying the following properties:

• 1. For every v ∈ V the set {t ∈ T∣v ∈ χ _t } induces a subtree of 𝓣.

• 2. For every e ∈ E there is a t ∈ T such that e ⊆ χ _t .

The width of a fractional hypertree decomposition $({\mathcal {T}}, (\chi _{t})_{t\in T},$ $((\psi_{t})_{t_{i}nT})$is defined as $\max _{t\in T}(\rho _{\mathcal {H}}^{*}(\chi _{t}))$. The fractional hypertree width of 𝓗 is the minimum width over all fractional hypertree decompositions of 𝓗.

Together with the previous results of this paper, the two following Theorems will serve as key ingredients to prove the main results of this section.

Theorem 17 ([23])

The solutions of a CQ-instance Φ with hypergraph ${\mathcal {H}}=(V,E)$ can be enumerated in time $\|\Phi \|^{\rho ^{*}_{\mathcal {H}}(V) + O(1)}$.

Theorem 18

([28]) Given a hypergraph 𝓗 and a rational number w ≥ 1, it is possible in time $\|\mathcal {H}\|^{O(w^{3})}$ to either

• compute a fractional hypertree decomposition of 𝓗 with width at most 7w ³ + 31w + 7, or

• correctly conclude that $\text {fhw}({\mathcal {H}})\ge w$.

7.1 Tractable Counting

We start of with the quantifier free case which we will use as a building block for the more general result later.

Lemma 22

The solutions of a quantifier free CQ-instance Φ with hypergraph 𝓗 can be counted in time $\|\Phi \|^{{\text {fhw}}(\mathcal {H})^{O(1)}}$.

Proof

With Theorem 18 we can compute a fractional hypertree decomposition $({\mathcal {T}}, (\chi _{t})_{t\in T}, (\psi _{t})_{t\in T})$ of width at most $k:=O({\text {fhw}}(\mathcal {H})^{3})$. For each bag χ _t we can with Theorem 17 in time ∥Φ∥^k compute all solutions to the CQ-instance Φ[χ _t ] that is induced by the variables in χ _t . Let these solutions form a new relation ${\mathcal {R}}_{t}$ belonging to a new atom $\phi ^{\prime }_{t}$. Then $\bigwedge _{t\in T} \phi ^{\prime }_{t}$ gives a solution equivalent, acyclic, quantifier free #CQ instance of size ∥Φ∥^O(k). Now we can count the solutions with the algorithm [31] or [15].

We can now prove a version of Corollary 1 for fractional hypertree width.

Theorem 19

There is an algorithm that given a #CQ-instance Φ of quantified starsize ℓ and fractional hypertree width k counts the solutions of Φ in time ∥Φ∥^p(k,ℓ) for a polynomial p.

Proof

This is a minor modification of the proof of Lemma 13. Let ${\mathcal {H}}= (V,E)$ be the hypergraph of Φ. Because of Theorem 18 we may assume that we have a fractional hypertree decomposition $\varXi :=(\mathcal {T}, (\chi _{t})_{t\in T}, (\psi _{t})_{t\in T})$ of width k′ := k ^O(1) of 𝓗. For each edge e ∈ E we let φ(e) be the atom of Φ that induces e.

Let V ₁, … , V _m be the vertex sets of the components of ${\mathcal {H}}[V\backslash S]$ and let $V_{1}^{\prime }, \ldots , V_{m}^{\prime }$ be the vertex sets of the S-components of 𝓗. Clearly, $V_{i}\subseteq V_{i}^{\prime }$ and $V_{i}^{\prime }-V_{i} = V_{i}^{\prime }\cap S=: S_{i}$. Let Φ _i be the restriction of Φ to the variables in $V_{i}^{\prime }$ and let Ξ _i be the corresponding fractional hypertree decomposition. Then Ξ _i has a tree $\mathcal {T}_{i}$ that is a subtree of 𝓣.

For each Φ _i we construct a new #CQ-instance $\phi _{i}^{\prime }$ by computing for each bag t ∈ T an atom ϕ _t in the variables χ _t that contains the solutions of Φ _i [χ _t ] that is induced by the variables of χ _t . The decomposition Ξ has width at most k′ so this can be done in time $\|\Phi \|^{O(k^{\prime })}$ by Theorem 17. Obviously Φ _i and $\Phi ^{\prime }_{i}$ are solution equivalent and $\Phi ^{\prime }_{i}$ is acyclic. Furthermore, $\phi _{i}^{\prime }$ has only one single S _i -component, because all the vertices in V _i are connected in Φ and thus also in $\phi _{i}^{\prime }$. Let $\mathcal {H}_{i}$ be the hypergraph of $\phi _{i}^{\prime }$, then $\mathcal {H}_{i}$ has S _i -star size at most ℓ. Thus the vertices in S _i can be covered by at most ℓ edges in $\mathcal {H}_{i}$ by Lemma 14.

Now we construct a CQ-instance $({\mathcal {A}}_{i}^{\prime \prime }, \phi _{i}^{\prime \prime })$ such that $\phi _{i}^{\prime \prime }$ is an atomic formula in the variables S _i exactly as in the proof of Lemma 13.

We now eliminate all quantified variables in Φ. To do so we add the atom $\phi _{i}^{\prime \prime }$ for i ∈ [m] and delete all atoms that contain any quantified variable, i.e., we delete all $\phi _{i}^{\prime }$. Call the resulting CQ-instance Φ″. Because $\left ({\mathcal {A}}_{i}^{\prime \prime }, \phi _{i}^{\prime \prime }\right )$ is solution equivalent to $\phi _{i}^{\prime }$, we have that Φ and Φ″ are solution equivalent, too.

We now construct a fractional hypertree decomposition of Φ″ by doing the following: we set $\chi _{t}^{\prime } = (\chi _{t}\setminus \bigcup _{i\in I_{t}}V_{i})\cup \bigcup _{i\in I_{t}} S_{i}$ for each bag χ _t where I _t := {i∣χ _t ∩ V _i ≠ 0}. For each bag χ _t we construct a fractional edge cover $\psi _{t}^{\prime }$ of $\chi _{t}^{\prime }$ by setting $\psi _{t}^{\prime }(e) := \psi _{t}(e)$ for all old edges and setting ψ _t (S _i ) = 1 for i ∈ I _t where S _i corresponds to the newly added constraint ϕ _i with χ _t ∩ V _i ≠ 0. The result is indeed a fractional edge cover, because each variable not in any S _i is still covered as before and the variables in S _i are covered by definition of ψ _t . Furthermore, we claim that the width of the cover is at most k ′. Indeed, for each i ∈ I we had for each v ∈ V _i , $\sum _{e\in E: v\in e} \psi (e) \ge 1$. None of these edges appears in the new decomposition anymore. Thus adding the edge S _i with weight 1 does not increase the total weight of the cover. It is now easy to see that doing this construction for all χ _t leads to a fractional hypertree decomposition of Φ′ of width at most k ′.

Applying Lemma 22 concludes the proof.

7.2 Computing Independents Sets

Also S-star size or equivalently independent sets of bounded fractional hypertree width hypergraphs can be computed efficiently.

Lemma 23

There is an algorithm that given a hypergraph ${\mathcal {H}}=(V,E)$ of fractional hypertree width at most k computes a maximum independent set of 𝓗 in time $|\mathcal {H}|^{k^{O(1)}}$.

In the proof of Lemma 23 we will use the following lemma.

Lemma 24

The independent sets of a hypergraph ${\mathcal {H}}=(V,E)$ can be enumerated in time $|{\mathcal {H}}|^{O(\rho ^{*}_{{\mathcal {H}}}(V))}$.

Proof

Let ${\mathcal {H}}=(V,E)$. We construct a quantifier free CQ-instance $\Phi =({\mathcal {A}}, \phi )$ with the hypergraph 𝓗. Let V be the variables of Φ, {0,1} the domain and add an atom ϕ _e with relation symbol ${\mathcal {R}}_{e}$ and scope e for each e ∈ E. The relation ${\mathcal {R}}_{e}^{{\mathcal {A}}}$ contains all tuples that contain at most one 1 entry. Finally, $\phi := \bigwedge _{e\in E} \phi _{e}$.

Clearly, Φ has indeed the hypergraph 𝓗. Furthermore the solutions of Φ are exactly the characteristic vectors of independent sets of 𝓗. Thus we can enumerate all independent sets of 𝓗 in time $|\mathcal {H}|^{O(\rho ^{*}_{\mathcal {H}}(V))}$ with Theorem 17.

Proof of Lemma 23 (Sketch))

We proceed by dynamic programming along a fractional hypertree decomposition.

In a first step we compute a fractional hypertree decomposition $({\mathcal {T}}, (\chi _{t})_{t\in T}, (\psi _{t})_{t\in T})$ of width k′ = k ^O(1) of 𝓗 with Theorem 18. For each bag χ _t we then compute all all independent sets of $\mathcal {H}[\chi _{t}]$ by Lemma 24; call this set I _t .

By dynamic programming similar to the proof of Lemma 2 we then compute a maximum independent set of 𝓗.

8 Conclusion

The results of this paper give a clear picture of tractability for counting solutions of conjunctive queries for structural classes that are known to have tractable decision problems. Essentially counting is tractable if and only if these classes are combined with quantified star size. So to find more general structural classes that allow tractable counting, progress for the corresponding decision question appears to be necessary.

Note that our characterizations of tractable classes of queries rely only on the underlying hypergraphs of the queries and do not use any other information. For the case of bounded arity, it is known that analyzing classes of queries directly instead of their hypergraphs allows to completely characterize the classes of queries for which the decision problem CQ is tractable [12, 22]. In particular, this includes tractable classes whose tractability is not witnessed by the hypergraph perspective alone. A refinement of our results in this style in the case of bounded arity can be found in [29]. These results will also appear in an upcoming paper by Hubie Chen and the second author.

Another way of generalizing the results of this paper would be extending the logic that the queries can be formulated in. Just recently Chen and Dalmau [9] have characterized the tractable classes of bounded arity QCSP which is essentially a version of CQ in which also universal quantifiers are allowed. They do this by introducing a new width measure for first order {∀, ∃, ∧}-formulas. We conjecture that their width measure also characterizes the tractable cases for #QCSP, i.e., tractable decision and counting coincide here. It would be interesting to see how far this can be pushed for the case of unbounded arity.

Another extension of conjunctive queries appears in a recent paper by Chen [7] where he considers existential formulas that may use conjunction and disjunction. This is particularly interesting, because it corresponds to the classical select-project-join queries with union that play an important role in database theory (see e.g., the textbook [1]). One may wonder if techniques used in this paper may help to understand the complexity of this class of queries better.