The complexity of homomorphism and constraint satisfaction problems seen from the other side

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of homomorphism and constraint satisfaction problems seen from the other side

Full text

Pdf (214 KB)

Source

Journal of the ACM (JACM) archive
Volume 54 , Issue 1 (March 2007) table of contents

Article No. 1

Year of Publication: 2007

ISSN:0004-5411

Author

Martin Grohe

Humboldt-Universität zu Berlin, Berlin, Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 115, Citation Count: 4

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1206035.1206036 What is a DOI?

ABSTRACT

We give a complexity theoretic classification of homomorphism problems for graphs and, more generally, relational structures obtained by restricting the left hand side structure in a homomorphism. For every class C of structures, let HOM(C,−) be the problem of deciding whether a given structure A ∈C has a homomorphism to a given (arbitrary) structure ß. We prove that, under some complexity theoretic assumption from parameterized complexity theory, HOM(C,−) is in polynomial time if and only if C has bounded tree width modulo homomorphic equivalence.

Translated into the language of constraint satisfaction problems, our result yields a characterization of the tractable structural restrictions of constraint satisfaction problems. Translated into the language of database theory, it implies a characterization of the tractable instances of the evaluation problem for conjunctive queries over relational databases.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Abrahamson, K., Downey, R., and Fellows, M. 1995. Fixed-parameter tractability and completeness IV: On completeness for W{P} and PSPACE analogs. Ann. Pure Appl. Logic 73, 235--276.
	3	Adler, I., Gottlob, G., and Grohe, M. 2005. Hypertree-width and related hypergraph invariants. In Proceedings of the 3rd European Conference on Combinatorics, Graph Theory, and Applications, S. Felsner, Ed. DMTCS Proceedings Series, vol. AE. 5--10.
	4	Andrei A. Bulatov, A Dichotomy Theorem for Constraints on a Three-Element Set, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.649-658, November 16-19, 2002
	5	Andrei A. Bulatov, Tractable conservative Constraint Satisfaction Problems, Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.321, June 22-25, 2003
	6	Andrei Bulatov , Andrei Krokhin , Peter Jeavons, The complexity of maximal constraint languages, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.667-674, July 2001, Hersonissos, Greece [doi>10.1145/380752.380868]
	7	Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
	8	Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
	9	Chen, H., and Dalmau, V. 2005. Beyond hypertree width: Decomposition methods without decompositions. In Proceedings of the 11th International Conference on Principles and Practice of Constraint Programming, P. van Beek, Ed. Lecture Notes in Computer Science, vol. 3709. Springer-Verlag, New York, 167--181.
	10	Cohen, D., Jeavons, P., and Gyssens, M. 2005. A unified theory of structural tractability for constraint satisfaction and spread cut decomposition. In Proceedings of the 19th International Joint Conference on Artificial Intelligence, L. P. Kaelbling and A. Saffiotti, Eds. 72--77.
	11	Ho Weng Kin, Generalized Majority-Minority Operations are Tractable, Proceedings of the 20th Annual IEEE Symposium on Logic in Computer Science (LICS' 05), p.438-447, June 26-29, 2005 [doi>10.1109/LICS.2005.19]
	12	Víctor Dalmau , Peter Jonsson, The complexity of counting homomorphisms seen from the other side, Theoretical Computer Science, v.329 n.1-3, p.315-323, 13 December 2004 [doi>10.1016/j.tcs.2004.08.008]
	13	Víctor Dalmau , Phokion G. Kolaitis , Moshe Y. Vardi, Constraint Satisfaction, Bounded Treewidth, and Finite-Variable Logics, Proceedings of the 8th International Conference on Principles and Practice of Constraint Programming, p.310-326, September 09-13, 2002
	14	Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
	15	Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3]
	16	Downey, R., and Fellows, M. 1999. Parameterized Complexity. Springer-Verlag, New York.
	17	Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
	18	Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002 [doi>10.1145/602220.602222]
	19	J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
	20	Freuder, E. 1990. Complexity of k-tree structured constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence. 4--9.
	21	Gottlob, G., Leone, N., and Scarcello, F. 2002. Hypertree decompositions and tractable queries. J. Comput. Syst. Sci. 64, 579--627.
	22	Georg Gottlob , Nicola Leone , Francesco Scarcello, Robbers, marshals, and guards: game theoretic and logical characterizations of hypertree width, Journal of Computer and System Sciences, v.66 n.4, p.775-808, 1 June 2003 [doi>10.1016/S0022-0000(03)00030-8]
	23	Martin Grohe, The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side, Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, p.552, October 11-14, 2003
	24	Martin Grohe , Dániel Marx, Constraint solving via fractional edge covers, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.289-298, January 22-26, 2006, Miami, Florida [doi>10.1145/1109557.1109590]
	25	Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece [doi>10.1145/380752.380867]
	26	Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
	27	Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
	28	Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, v.51 n.1, p.110-134, Aug. 1995
	29	Phokion G. Kolaitis , Moshe Y. Vardi, Conjunctive-query containment and constraint satisfaction, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.205-213, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275511]
	30	Christos H. Papadimitriou , Mihalis Yannakakis, Linear programming without the matrix, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.121-129, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167127]
	31	Jürgen Plehn , Bernd Voigt, Finding minimally weighted subgraphs, Proceedings of the 16th international workshop on Graph-theoretic concepts in computer science, p.18-29, May 1991, Berlin, Germany
	32	Reed, B. 1997. Tree width and tangles: A new connectivity measure and some applications. In Surveys in Combinatorics, R. Bailey, Ed. LMS Lecture Note Series, vol. 241. Cambridge University Press, Cambridge, MA. 87--162.
	33	Neil Robertson , P D Seymour, Graph minors. V. Excluding a planar graph, Journal of Combinatorial Theory Series B, v.41 n.1, p.92-114, Aug. 1986 [doi>10.1016/0095-8956(86)90030-4]
	34	Neil Robertson , P. D. Seymour, Graph minors. XII: distance on a surface, Journal of Combinatorial Theory Series B, v.64 n.2, p.240-272, July 1995 [doi>10.1006/jctb.1995.1034]
	35	Neil Robertson , Paul Seymour , Robin Thomas, Quickly excluding a planar graph, Journal of Combinatorial Theory Series B, v.62 n.2, p.323-348, Nov. 1994 [doi>10.1006/jctb.1994.1073]
	36	Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335209]

CITED BY 4

	Víctor Dalmau , Andrei Krokhin, Majority constraints have bounded pathwidth duality, European Journal of Combinatorics, v.29 n.4, p.821-837, May, 2008
	Dániel Marx, Approximating fractional hypertree width, Proceedings of the Nineteenth Annual ACM -SIAM Symposium on Discrete Algorithms, p.902-911, January 04-06, 2009, New York, New York
	Bruno Zanuttini , Stanislav Živný, A note on some collapse results of valued constraints, Information Processing Letters, v.109 n.11, p.534-538, May, 2009
	Peter Golbus , Robert W. McGrail , Tomasz Przytycki , Mary Sharac , Aleksandar Chakarov, Tricolorable torus knots are NP-complete, Proceedings of the 47th Annual Southeast Regional Conference, March 19-21, 2009, Clemson, South Carolina