Access Restriction

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

   Open content in new tab
Source: ACM Digital Library