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.

Robert Recorde Room

Department of Computer Science