Hypertree decompositions, generalized hypertree decompositions, and fractional hypertree decompositions are hypergraph decomposition methods successfully used for answering conjunctive queries and for the solution of constraint satisfaction problems. In this work, we present new intractability and tractability results for the problem of recognizing if a given hypergraph has a generalized or fractional hypertree decomposition of low width.
Clearly, bounded fhw defines the largest tractable class while bounded hw defines
the smallest one. On the other hand, only the problem CHECK(HD, k) is known to be
feasible in polynomial time [
Formally both, CQs and CSPs, are first-order formulae using only f9; ^g as connectives. but not f8; _; :g. Now consider an arbitrary CQ or CSP, i.e., an FO-formula with connectives f9; ^g. The hypergraph corresponding to is defined as hypergraph H = (V (H); E(H)), where the set of vertices V (H) is defined as the set of variables in and the set of edges E(H) is defined as E(H) = fe j contains an atom A, s.t. e equals the set of variables occurring in Ag.
We consider here three notions of hypergraph decompositions with associated notions of width. To this end, we first introduce the notion of (fractional) edge covers. Let H = (V (H); E(H)) be a hypergraph and consider a function : E(H) ! [0; 1]. Then, we define the set B( ) of all vertices covered by and the weight of as 8 < : B( ) = v 2 V (H) j
X e2E(H);v2e (e) 9 = 1 ; weight ( ) = ;
X
e2E(H)
(e):
The special case of a function with values restricted to f0; 1g, will usually be denoted
by , i.e., : E(H) ! f0; 1g. Note that, following [
E(H) (i.e., the set of edges e with (e) = 1) and the weight as the cardinality of such a set of edges.
We are now ready to introduce our three notions of hypergraph decompositions and their width measures.
Definition 1. A generalized hypertree decomposition (GHD) of a hypergraph H = (V (H); E(H)) is a tuple T; (Bu)u2N(T ); ( )u2N(T ) , such that T = hN (T ); E(T )i is a rooted tree and the following conditions hold: (1) for each e 2 E(H), there is a node u 2 N (T ) with e Bu; (2) for each v 2 V (H), the set fu 2 N (T ) j v 2 Bug is connected in T ; (3) for each u 2 N (T ), u is a function u : E(H) ! f0; 1g with Bu
We use the following notational conventions. To avoid confusion, we will
consequently refer to the elements in V (H) as vertices of the hypergraph and to the elements
in N (T ) as the nodes of the decomposition. For a node u in T , we write Tu to denote
the subtree of T rooted at u. By slight abuse of notation, we will write u0 2 Tu to denote
that u0 is a node in the subtree Tu of T . Finally, we define V (Tu) := Su02Tu Bu0 .
Definition 2. A hypertree decomposition (HD) of a hypergraph H = (V (H); E(H))
is a GHD, which in addition also satisfies the following condition:
(4) for each u 2 N (T ), V (Tu) \ B( u)
Definition 3. A fractional hypertree decomposition (FHD) [
The width of a GHD, HD, or FHD is the maximum weight of the functions u or u, respectively, over all nodes u in T . The generalized hypertree width, hypertree width, and fractional hypertree width of H (denoted ghw (H), hw (H), fhw (H)) is the minimum width over all GHDs, HDs, and FHDs of H, respectively. 3
On the negative side, the main result of our work is the following NP-completeness (in particular, the NP-hardness) result: Theorem 1. The CHECK(FHD, k) problem is NP-complete for k = 2.
The NP-hardness proof is by reduction from the 3-SAT problem. It can be easily
extended to arbitrary (possibly fractional) k 3 (see [
The construction in the proof of Theorem 1 also gives us the following result: Theorem 2. The CHECK(GHD, k) problem is NP-complete for k = 2.
On the positive side, we identify general, realistic, and non-trivial restrictions that make the CHECK(GHD, k) and CHECK(FHD, k) problems tractable. More precisely, we concentrate on the following three properties: Definition 4. We say that a class C of hypergraphs has the bounded intersection property (BIP) if there exists some constant i such that for every hypergraph H in C , the cardinality of any intersection e1 \ e2 of two distinct edges e1 and e2 of H is i.
We say that a class C of hypergraphs has the bounded multi-intersection property (BMIP) if there exist constants c and i such that for every hypergraph H in C , the cardinality of any intersection e1 \ \ ec of c distinct edges e1; : : : ; ec of H is i.
We say that a class C of hypergraphs has bounded degree, if there exists d 1, such that for every hypergraph H 2 C , jfe 2 E(H) j v 2 E(H)gj d holds, i.e., every vertex occurs in at most d edges.
In an empirical analysis of several CQ and CSP instances we have verified that an
overwhelming number of the instances enjoy these properties for low constants i, c, or
d, respectively [
Unfortunately, the tractability proof for the BMIP in Theorem 3 does not directly carry over to FHDs. However, by combining two restrictions, we also manage to identify an interesting tractable fragment for the CHECK(FHD, k) problem. Theorem 4. Let C be a class of hypergraphs. If C has the BIP and bounded degree, then the CHECK(FHD, k) problem is in P for arbitrary k > 0. Moreover, in case of a positive instance, an FHD of width k can be computed in polynomial time. 4
Our main results shown in this work are, on the one hand, the NP-completeness proof
of the CHECK(decomp, k) problem for decomp 2 fGHD, FHDg and k = 2 and, on the
other hand, the identification of tractable fragments of these problems. The tractability
results for CHECK(FHD, k) are significantly weaker than for CHECK(GHD, k).
Further results in [
Acknowledgements. This work was supported by the Engineering and Physical Sciences Research Council (EPSRC), Programme Grant EP/M025268/ VADA: Value Added Data Systems — Principles and Architecture as well as by the Austrian Science Fund (FWF):P25518-N23 and P30930-N35.