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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Adler, I.: Marshals, monotone marshals, and hypertree-width. Journal of Graph Theory 47(4), 275–296 (2004)
Atserias, A., Bulatov, A., Dalmau, V.: On the Power of k -Consistency. In: Arge, L., Cachin, C., Jurdziński, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 279–290. Springer, Heidelberg (2007)
Adler, I., Gottlob, G., Grohe, M.: Hypertree-Width and Related Hypergraph Invariants. European Journal of Combinatorics 28, 2167–2181 (2007)
Bernstein, P.A., Goodman, N.: The power of natural semijoins. SIAM Journal on Computing 10(4), 751–771 (1981)
Bodlaender, H.L., Fomin, F.V.: A Linear-Time Algorithm for Finding Tree Decompositions of Small Treewidth. SIAM Journal on Computing 25(6), 1305–1317 (1996)
Daskalakis, C., Papadimitriou, C.H.: Computing pure nash equilibria in graphical games via markov random fields. In: Proc. of ACM EC 2006, pp. 91–99 (2006)
Fraigniaud, P., Nisse, N.: Connected Treewidth and Connected Graph Searching. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol. 3887, pp. 479–490. Springer, Heidelberg (2006)
Golumbic, M.C., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms 19, 449–473 (1995)
Golumbic, M.C., Wassermann, A.: Complexity and algorithms for graph and hypergraph sandwich problems. Graphs and Combinatorics 14, 223–239 (1998)
Goodman, N., Shmueli, O.: Syntactic characterization of tree database schemas. Journal of the ACM 30(4), 767–786 (1983)
Goodman, N., Shmueli, O.: The tree projection theorem and relational query processing. JCSS 28(1), 60–79 (1984)
Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. of Computer and System Sciences 64(3), 579–627 (2002)
Gottlob, G., Leone, N., Scarcello, F.: Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width. J. of Computer and System Sciences 66(4), 775–808 (2003)
Gottlob, G., Miklós, Z., Schwentick, T.: Generalized hypertree decompositions: NP-hardness and tractable variants. In: Proc. of PODS 2007, pp. 13–22 (2007)
Greco, G., Scarcello, F.: Tree Projections: Hypergraph Games and Minimality. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 736–747. Springer, Heidelberg (2008)
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM 54(1) (2007)
Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proc. of SODA 2006, pp. 289–298 (2006)
Lustig, A., Shmueli, O.: Acyclic hypergraph projections. Journal of Algorithms 30(2), 400–422 (1999)
Pearson, J., Jeavons, P.G.: A Survey of Tractable Constraint Satisfaction Problems, CSD-TR-97-15, Royal Holloway, Univ. of London (1997)
Robertson, N., Seymour, P.D.: Graph minors III: Planar tree-width. Journal of Combinatorial Theory, Series B 36, 49–64 (1984)
Ruzzo, W.L.: Tree-size bounded alternation. Journal of Cumputer and System Sciences 21, 218–235 (1980)
Sagiv, Y., Shmueli, O.: Solving queries by tree projections. ACM Transactions on Database Systems 18(3), 487–511 (1993)
Seymour, P.D., Thomas, R.: Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory, Series B 58, 22–33 (1993)
Subbarayan, S., Reif Andersen, H.: Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs. In: Proc. of IJCAI 2007, pp. 180–185 (2007)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Gottlob, G., Greco, G., Miklós, Z., Scarcello, F., Schwentick, T. (2009). Tree Projections: Game Characterization and Computational Aspects. In: Lipshteyn, M., Levit, V.E., McConnell, R.M. (eds) Graph Theory, Computational Intelligence and Thought. Lecture Notes in Computer Science, vol 5420. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-02029-2_21
Download citation
DOI: https://doi.org/10.1007/978-3-642-02029-2_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-02028-5
Online ISBN: 978-3-642-02029-2
eBook Packages: Computer ScienceComputer Science (R0)