Marshals, Monotone Marshals, and hypertree-width

The tree-width of a hypergraph H equals one less than the number of cops necessary to catch the robber in the Monotone Robber and Cops Game played on H. Analogously, the hypertree-width of a hypergraph is characterised by the Monotone Robber and Marshals Game. While the Robber and Cops Game and its monotone variant coincide, Gottlob, Leone and Scarcello stated the corresponding question for the Robber and Marshals Game as an open problem. We give a negative answer. Concerning the generalised hypertree-width, our counterexamples show that it is neither characterised by the Robber and Marshals Game nor by its monotone variant. We conclude by resuming how these hypergraph invariants are related, (C) 2004 Wiley Periodicals, hic.