Generalized hypertree decompositions: NP-hardness and tractable variants
- 8 September 2009
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 56 (6), 1-32
- https://doi.org/10.1145/1568318.1568320
Abstract
The generalized hypertree width GHW( H ) of a hypergraph 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 k and input hypergraph H it can be determined in polynomial time whether GHW( H ) ≤ k . Here, this problem is settled by proving that even for 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 H admits a tree projection with respect to a hypergraph 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.Keywords
Funding Information
- Engineering and Physical Sciences Research Council (EP/E010865/1)
- Austrian Science Fund (P17222-N04)
This publication has 24 references indexed in Scilit:
- Hypertree Decompositions and Tractable QueriesJournal of Computer and System Sciences, 2002
- The complexity of acyclic conjunctive queriesJournal of the ACM, 2001
- Conjunctive-Query Containment and Constraint SatisfactionJournal of Computer and System Sciences, 2000
- Acyclic Hypergraph ProjectionsJournal of Algorithms, 1999
- Graph Sandwich ProblemsJournal of Algorithms, 1995
- Solving queries by tree projectionsACM Transactions on Database Systems, 1993
- Easy problems for tree-decomposable graphsJournal of Algorithms, 1991
- Graph minors. II. Algorithmic aspects of tree-widthJournal of Algorithms, 1986
- Closures of database hypergraphsJournal of the ACM, 1985
- The tree projection theorem and relational query processingJournal of Computer and System Sciences, 1984