Robbers, marshals, and guards
Georg Gottlob, Nicola Leone, Francesco Scarcello · 2001
In a previous paper [10], the authors introduced the notion of hypertree decomposition and the corresponding concept of hypertree width and showed that the conjunctive queries whose hypergraphs have bounded hypertree-width can be evaluated in polynomial time. Bounded hypertree-width generalizes the notions of acyclicity and bounded treewidth and corresponds to larger classes of tractable queries. In the present paper, we provide natural characterizations of hypergraphs and queries having bounded hypertree-width in terms of game-theory and logic.