×

zbMATH — the first resource for mathematics

A comparison of structural CSP decomposition methods. (English) Zbl 0952.68044
We compare tractable classes of Constraint Satisfaction Problems (CSPs). We first give a uniform presentation of the major structural CSP decomposition methods. We then introduce a new class of tractable CSPs based on the concept of hypertree decomposition recently developed in database theory, and analyze the cost of solving CSPs having bounded hypertree-width. We provide a framework for comparing parametric decomposition-based methods according to tractability criteria and compare the most relevant methods. We show that the method of hypertree decomposition dominates the others in the case of general CSPs (i.e., CSPs of unbounded arity). We also make comparisons for the restricted case of binary CSPs. Finally, we consider the application of decomposition methods to the dual graph of a hypergraph. In fact, this technique is often used to exploit binary decomposition methods for nonbinary CSPs. However, even in this case, the hypertree-decomposition method turns out to be the most general method.

MSC:
68P15 Database theory
PDF BibTeX Cite
Full Text: DOI
References:
[1] Arnborg, S.; Lagergren, J.; Seese, D., Problems easy for tree-decomposable graphs, J. algorithms, 12, 308-340, (1991) · Zbl 0734.68073
[2] Beeri, C.; Fagin, R.; Maier, D.; Yannakakis, M., On the desirability of acyclic database schemes, J. ACM, 30, 3, 479-513, (1983) · Zbl 0624.68087
[3] Bernstein, P.A.; Goodman, N., The power of natural semijoins, SIAM J. comput., 10, 4, 751-771, (1981) · Zbl 0469.68090
[4] Bibel, W., Constraint satisfaction from a deductive viewpoint, Artificial intelligence, 35, 401-413, (1988) · Zbl 0645.68112
[5] Bodlaender, H.L., Treewidth: algorithmic techniques and results, (), 19-36 · Zbl 0941.05057
[6] Chekuri, Ch.; Rajaraman, A., Conjunctive query containment revisited, Theoret. comput. sci., 239, 2, 211-229, (2000) · Zbl 0944.68046
[7] Dechter, R., Constraint networks, (), 276-285
[8] Dechter, R.; Pearl, J., Network based heuristics for constraint satisfaction problems, Artificial intelligence, 34, 1, 1-38, (1988) · Zbl 0643.68156
[9] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artificial intelligence, 38, 353-366, (1989) · Zbl 0665.68084
[10] Freuder, E.C., A sufficient condition for backtrack-free search, J. ACM, 29, 1, 24-32, (1982) · Zbl 0477.68063
[11] Freuder, E.C., A sufficient condition for backtrack-bounded search, J. ACM, 32, 4, 755-761, (1985) · Zbl 0633.68096
[12] Freuder, E.C., Complexity of k-tree structured constraint satisfaction problems, Proc. AAAI-90, Boston, MA, (1990)
[13] Garey, M.R.; Johnson, D.S., Computers and intractability. A guide to the theory of NP-completeness, (1979), Freeman New York, NY · Zbl 0411.68039
[14] N. Goodman, O. Shmueli, Syntactic characterization of tree database schemas, J. ACM 30 (4) 767-786 · Zbl 0625.68077
[15] Gottlob, G.; Leone, N.; Scarcello, F., The complexity of acyclic conjunctive queries, (), 706-715, Full version: Technical Report DBAI-TR-98/17, available on the web as: http://www.dbai.tuwien.ac.at/staff/gottlob/acyclic.ps, or by email from the authors
[16] Gottlob, G.; Leone, N.; Scarcello, F., Hypertree decompositions and tractable queries, (), Full version to appear in Journal of Computer and System Sciences. A preprint of the full version is currently stored in The Computer Research Repository, http://xxx.lanl.gov/archive/cs · Zbl 1052.68025
[17] Gottlob, G.; Leone, N.; Scarcello, F., On tractable queries and constraints, (), 1-15
[18] Gyssens, M.; Jeavons, P.G.; Cohen, D.A., Decomposing constraint satisfaction problems using database techniques, Artificial intelligence, 66, 57-89, (1994) · Zbl 0803.68090
[19] Gyssens, M.; Paredaens, J., A decomposition methodology for cyclic databases, (), 85-122
[20] Jeavons, P.; Cohen, D.; Gyssens, M., Closure properties of constraints, J. ACM, 44, 4, (1997) · Zbl 0890.68064
[21] Kolaitis, Ph.G.; Vardi, M.Y., Conjunctive-query containment and constraint satisfaction, (), 205-213, Full version to appear in Journal of Computer and System Sciences · Zbl 0963.68059
[22] Maier, D., (1986), Computer Science Press Rockville, MD
[23] Pearson, J.; Jeavons, P.G., (1997), CSD-TR-97-15, Royal Holloway, University of London London
[24] Robertson, N.; Seymour, P.D., Graph minors II. algorithmic aspects of tree width, J. algorithms, 7, 309-322, (1986) · Zbl 0611.05017
[25] Seidel, R., A new method for solving constraint satisfaction problems, ()
[26] Yannakakis, M., Algorithms for acyclic database schemes, (), 82-94
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.