Tree Projections: Hypergraph Games and Minimality

A hypergraph-game characterization is provided for hypergraph tree projections (TPs) and, hence, for the special cases of generalized and fractional hypertree decompositions, where such a characterization was missing and asked for. In this game, as for the Robber and Cops game characterizing tree decompositions, the existence of winning strategies implies the existence of monotone ones, which are yet somehow preferable, because they correspond to minimal tree projections. In fact, it is shown that minimal TPs enjoy a number of nice properties, such as the same kind of connection property as (minimal) tree decompositions of graphs. Finally, it is shown that this property is somehow tight, by giving a negative answer to an open question about a slightly stronger notion of connection property, defined to speed-up the computation of hypertree decompositions.