Tree Projections: Game Characterization and Computational Aspects

The notion of tree projection provides a natural generalization for various structural decomposition methods, which have been proposed in the literature in order to single out classes of nearly-acyclic (hyper)graphs. In this paper, the mathematical properties of the notion of tree projection are overviewed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is depicted. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15]) for tree projections is described, which also serves to provide simple arguments for the membership in NP of the tree projection problem. Eventually, the main ideas proposed in [14] and underlying the proof of NP-hardness of the tree projection problem are discussed.