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 ) 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  and underlying the proof of NP-hardness of the tree projection problem are discussed.
Record created on 2009-09-21, modified on 2016-08-08