### Generalized hypertree decompositions: NP-hardness and tractable variantsGeneralized hypertree decompositions: NP-hardness and tractable variants

Access Restriction
Subscribed

 Author Gottlob, Georg ♦ Mikls, Zoltn ♦ Schwentick, Thomas Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2009 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Conjunctive query ♦ NP-complete ♦ TreeProjection Problem ♦ Acyclic ♦ Hypergraph ♦ Hypertree decomposition ♦ Tractable Abstract The generalized hypertree width $GHW(\textit{H})$ of a hypergraph $\textit{H}$ is a measure of its cyclicity. Classes of conjunctive queries or constraint satisfaction problems whose associated hypergraphs have bounded GHW are known to be solvable in polynomial time. However, it has been an open problem for several years if for a fixed constant $\textit{k}$ and input hypergraph $\textit{H}$ it can be determined in polynomial time whether $GHW(\textit{H})$ ≤ $\textit{k}.$ Here, this problem is settled by proving that even for $\textit{k}$ = 3 the problem is already NP-hard. On the way to this result, another long standing open problem, originally raised by Goodman and Shmueli [1984] in the context of join optimization is solved. It is proven that determining whether a hypergraph $\textit{H}$ admits a tree projection with respect to a hypergraph $\textit{G}$ is NP-complete. Our intractability results on generalized hypertree width motivate further research on more restrictive tractable hypergraph decomposition methods that approximate generalized hypertree decomposition (GHD). We show that each such method is dominated by a tractable decomposition method definable through a function that associates a set of partial edges to a hypergraph. By using one particular such function, we define the new Component Hypertree Decomposition method, which is tractable and strictly more general than other approximations to GHD published so far. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2009-09-08 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 56 Issue Number 6 Page Count 32 Starting Page 1 Ending Page 32

#### Open content in new tab

Source: ACM Digital Library