Hypertree Decompositions: Detecting Tractable Instances of NP-hard Problems

Georg Gottlob

(Oxford University)

One of the best-known methods for decomposing graphs is the method of
tree-decompositions introduced by Robertson and Seymour. Many NP-hard
problems become polynomially soblvable if restricted to instances
whose underlying graph structure has bounded treewidth. The notion of
treewidth can be straightforwardly extended to hypergraphs by simply
considering the treewidth of their primal graphs or, alteratively, of
their incidence graphs. However, doing so comes along with a loss of
information on the structure of a hypergraph with the effect that many
polynomially solvable problems cannot be recognized as such because
the treewidth of the underlying hypergraphs is unbounded. In
particular, the treewidth of the class of acyclic hypergraphs is
unbounded. In this talk, I will describe more appropriate measures for
hypergraph acyclicity, and, in particular, the method of hypertree
decompositions and the associated concept of hypertree width. After
giving general results on hypertree decompositions, I will report on
game-theoretic characterizations of hypergraph decomposition methods,
and give a survey on recent results.
Tuesday 16th October 2007, 14:00
Robert Recorde Room
Department of Computer Science