Hypertree Decompositions and Tractable Queries and Constraints

One way of coping with an NP-hard problem is to identify significantly large classes of instances that are both recognizable and solvable in polynomial time. Such instances are often defined via some structural property of a graph G(I) that is associated in a canonical way with the instance I.
For example, many problems that are NP-complete in general become tractable for instances I whose associated graph has bounded treewidth. Treewidth is a measure of the degree of cyclicity of a graph.
Note that instances of bounded treewidth are also easy to recognize given that deciding whether the treewidth of a graph is at most k is decidable in linear time for each constant k>0.

The structure of a large number of problems is, however, more faithfully described by a hypergraph than by a graph. Again, several NP-complete problems become tractable if restricted to instances with acyclic hypergraphs. In order to obtain larger tractable instance-classes of hypergraph-based problems, we thus investigated measures of hypergraph cyclicity that play a similar role for hypergraphs as the concept of treewidth does for graphs.
In particular, an appropriate notion of hypergraph width (and an associated method of hypergraph decomposition) should fulfill both of the following conditions:
-    Relevant hypergraph-based problems should be solvable in polynomial time for instances of bounded width.
-    For each constant k, one should be able to check in polynomial time whether a hypergraph is of width k, and, in the positive case, it should be possible to produce an associated decomposition of width k of the given hypergraph.

Existing measures for hypergraph cyclicity we were aware of do either not fulfil one of these two conditions (e.g. recognizing hypergraphs of bounded query width is NP-complete, or are not general enough (such methods are mentioned. In particular, various notions of hypergraph width can be obtained by first transforming a hypergraph into a graph and then considering the treewidth of that graph. However, it is not hard to see that such measures of cyclicity are not very significant due to a loss of structural information caused by the transformation of the hypergraph to a graph. 

In summary, it appeared that a satisfactory way of determining the degree of cyclicity of a hypergraph was missing, on the basis of which large tractable instances of relevant NP-hard problems could be defined.
Consequently, after a careful analysis of the shortcomings of various hypergraph decomposition methods, we introduced the new method of hypertree decomposition and the associated notion of hypertree width. To our best knowledge, the method of hypertree decomposition is currently the most general known hypergraph decomposing method leading to large tractable classes of important problems such as constraint satisfaction problems or conjunctive queries.

For definitions and results on hypertree decompositions, formal comparisons with other structural methods defined in the literature, and further closely related issues, see the Section Papers, below.

Next, we describe some tools for computing and drawing hypertree decompositions, available for experimenting at Section Download.