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 surveyed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is pinpointed. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15] ) for tree projections is described, which yields a simple argument 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.
Tree Projections: Game Characterization and Computational Aspects
GRECO, Gianluigi;SCARCELLO F;
2009-01-01
Abstract
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 surveyed, and the complexity of the basic tree projection problem (of deciding the existence of a tree projection) is pinpointed. In more details, a game-theoretic characterization (in terms of the Robber and Captain game [15] ) for tree projections is described, which yields a simple argument 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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
