×

zbMATH — the first resource for mathematics

Tree projections and constraint optimization problems: fixed-parameter tractability and parallel algorithms. (English) Zbl 1390.68345
Summary: The problem of computing optimal solutions to Constraint Satisfaction Problem (CSP) instances parameterized by the size of the objective function is considered, and fixed-parameter polynomial-time algorithms are proposed within the structure-based framework of tree projections. The algorithms compute the desired optimal (or best \(k\)) solutions whenever there exists a tree projection for the given instance; otherwise, the algorithms report that there is no tree-projection. For the case where a tree projection is available, parallel algorithms are also proposed and analyzed. Structural decomposition methods based on acyclic, bounded treewidth, and bounded generalized hypertree-width hypergraphs, extensively considered in the CSP setting, as well as in conjunctive database query evaluation and optimization, are all covered as special cases of the tree projection framework.
MSC:
68Q25 Analysis of algorithms and problem complexity
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10 Graph theory (including graph drawing) in computer science
68W10 Parallel algorithms in computer science
90C27 Combinatorial optimization
Software:
ToulBar2
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Dechter, R., Constraint processing, (2003), Morgan Kaufmann Publishers Inc. San Francisco, CA, USA
[2] Bistarelli, S.; Fargier, H.; Montanari, U.; Rossi, F.; Schiex, T.; Verfaillie, G., Semiring-based CSPs and valued CSPs: basic properties and comparison, (Over-Constrained Systems, (1996)), 111-150 · Zbl 0946.68143
[3] Flerova, N.; Marinescu, R.; Dechter, R., Searching for the M best solutions in graphical models, J. Artif. Intell. Res., 55, 889-952, (2016) · Zbl 1352.68221
[4] Bulatov, A.; Dalmau, V.; Grohe, M.; Marx, D., Enumerating homomorphisms, J. Comput. Syst. Sci., 78, 2, 638-650, (2012) · Zbl 1253.68165
[5] Brafman, R.; Rossi, F.; Salvagnin, D.; Venable, K.; Walsh, T., Finding the next solution in constraint- and preference-based knowledge representation formalisms, (Proc. of KR’10, (2010)), 425-433
[6] Montanari, U., Networks of constraints: fundamental properties and applications to picture processing, Inf. Sci., 7, 95-132, (1974) · Zbl 0284.68074
[7] Yannakakis, M., Algorithms for acyclic database schemes, (Proc. of VLDB’81, (1981)), 82-94
[8] Fagin, R., Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30, 3, 514-550, (1983) · Zbl 0624.68088
[9] Gottlob, G.; Greco, G.; Leone, N.; Scarcello, F., Hypertree decompositions: questions and answers, (Proc of PODS’16, (2016), Association for Computing Machinery (ACM)), 57-74
[10] Kimelfeld, B.; Sagiv, Y., Incrementally computing ordered answers of acyclic conjunctive queries, (Proc. of NGITS’06, (2006)), 33-38
[11] Gottlob, G.; Greco, G.; Scarcello, F., Tractable optimization problems through hypergraph-based structural restrictions, (Proc. of ICALP’09, (2009)), 16-30 · Zbl 1248.68246
[12] Greco, G.; Scarcello, F., Structural tractability of constraint optimization, (Proc. of CP’11, (2011)), 340-355
[13] Marx, D., Tractable hypergraph properties for constraint satisfaction and conjunctive queries, J. ACM, 60, 6, 42:1-42:51, (2013) · Zbl 1281.68135
[14] Goodman, N.; Shmueli, O., The tree projection theorem and relational query processing, J. Comput. Syst. Sci., 28, 1, 60-79, (1984) · Zbl 0571.68086
[15] Sagiv, Y.; Shmueli, O., Solving queries by tree projections, ACM Trans. Database Syst., 18, 3, 487-511, (1993)
[16] Gottlob, G.; Miklós, Z.; Schwentick, T., Generalized hypertree decompositions: NP-hardness and tractable variants, J. ACM, 56, 6, 1-32, (2009) · Zbl 1325.68097
[17] Greco, G.; Scarcello, F., Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Inf. Comput., 252, 201-220, (2017) · Zbl 1355.68121
[18] Robertson, N.; Seymour, P., Graph minors. II. algorithmic aspects of tree-width, J. Algorithms, 7, 3, 309-322, (1986) · Zbl 0611.05017
[19] Gottlob, G.; Leone, N.; Scarcello, F., Hypertree decompositions and tractable queries, J. Comput. Syst. Sci., 64, 3, 579-627, (2002) · Zbl 1052.68025
[20] Chen, H.; Dalmau, V., Beyond hypertree width: decomposition methods without decompositions, (Proc. of CP’05, (2005)), 167-181 · Zbl 1153.68452
[21] Greco, G.; Scarcello, F., The power of local consistency in conjunctive queries and constraint satisfaction problems, SIAM J. Comput., 1111-1145, (2017) · Zbl 1371.68061
[22] 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
[23] Gyssens, M., On the complexity of join dependencies, ACM Trans. Database Syst., 11, 1, 81-108, (1986) · Zbl 0602.68097
[24] Karakashian, S.; Woodward, R. J.; Reeson, C. G.; Choueiry, B. Y.; Bessiere, C., A first practical algorithm for high levels of relational consistency, (Proc. of AAAI’10, (2010)), 101-107
[25] Kask, K.; Dechter, R.; Larrosa, J.; Dechter, A., Unifying tree decompositions for reasoning in graphical models, Artif. Intell., 166, 1-2, 165-193, (2005) · Zbl 1132.68680
[26] Bistarelli, S.; Montanari, U.; Rossi, F., Semiring-based constraint satisfaction and optimization, J. ACM, 44, 2, 201-236, (1997) · Zbl 0890.68032
[27] Terrioux, C.; Jégou, P., Bounded backtracking for the valued constraint satisfaction problems, (Proc. of CP’03, (2003)), 709-723 · Zbl 1273.68363
[28] Gottlob, G.; Greco, G., Decomposing combinatorial auctions and set packing problems, J. ACM, 60, 4, 1-39, (2013) · Zbl 1281.91088
[29] Joglekar, M.; Puttagunta, R.; Ré, C., Aggregations over generalized hypertree decompositions, CoRR
[30] Abo Khamis, M.; Ngo, H. Q.; Rudra, A., Faq: questions asked frequently, (Proc of PODS’16, (2016)), 13-28
[31] Lauritzen, S.; Spiegelhalter, D., Local computations with probabilities on graphical structures and their application to expert systems, (Readings in Uncertain Reasoning, (1990), Morgan Kaufmann Publishers Inc.), 415-448
[32] Downey, R. G.; Fellows, M. R., Parameterized complexity, (2012), Springer Publishing Company, Incorporated · Zbl 0914.68076
[33] Kolaitis, P.; Vardi, M., Conjunctive-query containment and constraint satisfaction, J. Comput. Syst. Sci., 61, 2, 302-332, (2000) · Zbl 0963.68059
[34] Bernstein, P.; Goodman, N., Power of natural semijoins, SIAM J. Comput., 10, 4, 751-771, (1981) · Zbl 0469.68090
[35] Greco, G.; Scarcello, F., Structural tractability of enumerating CSP solutions, Constraints, 18, 1, 38-74, (2013) · Zbl 1310.05151
[36] Lawler, E., A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem, Manag. Sci., 18, 7, 401-405, (1972) · Zbl 0234.90050
[37] Kasif, S., On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artif. Intell., 45, 3, 275-286, (1990) · Zbl 0717.68043
[38] Gottlob, G.; Leone, N.; Scarcello, F., The complexity of acyclic conjunctive queries, J. ACM, 48, 3, 431-498, (2001) · Zbl 1323.68250
[39] Gottlob, G.; Leone, N.; Scarcello, F., Computing LOGCFL certificates, Theor. Comput. Sci., 270, 1-2, 761-777, (2002) · Zbl 0992.68062
[40] Gottlob, G.; Leone, N.; Scarcello, F., Advanced parallel algorithms for acyclic conjunctive queries, (1998), Technical University of Vienna, Tech. Rep. DBAI-TR-98/18
[41] Greco, G.; Scarcello, F., Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Theor. Comput. Sci., 522, 95-114, (2014) · Zbl 1279.68277
[42] Karp, R. M.; Ramachandran, V., Parallel algorithms for shared-memory machines, (van Leeuwen, J., Handbook of Theoretical Computer Science (Vol. A), (1990), MIT Press Cambridge, MA, USA), 869-941 · Zbl 0900.68267
[43] Gent, I. P.; Jefferson, C.; Miguel, I.; Moore, N. C.; Nightingale, P.; Prosser, P.; Unsworth, C., A preliminary review of literature on parallel constraint solving, (Proc. of PMCS’11, (2011))
[44] Valiant, L. G., A bridging model for multi-core computing, J. Comput. Syst. Sci., 77, 1, 154-166, (2011) · Zbl 1210.68134
[45] Vishkin, U., Using simple abstraction to reinvent computing for parallelism, Commun. ACM, 54, 1, 75, (2011)
[46] Afrati, F. N.; Joglekar, M. R.; Ré, C.; Salihoglu, S.; Ullman, J. D., GYM: a multiround distributed join algorithm, (Proc. of ICDT’17, (2017)), 4:1-4:18 · Zbl 1402.68036
[47] Dubois, D.; Fargier, H.; Prade, H., The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, (Proc. of FUZZ-IEEE’93, (1993)), 1131-1136
[48] Fargier, H.; Lang, J., Uncertainty in constraint satisfaction problems: a probabilistic approach, (Proc. of ECSQARU’93, (1993)), 97-104
[49] Schiex, T., Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, (Proc. of UAI’92, (1992)), 268-275
[50] Freuder, E.; Wallace, R., Partial constraint satisfaction, Artif. Intell., 58, 21-70, (1992)
[51] Fargier, H.; Lang, J.; Schiex, T., Selecting preferred solutions in fuzzy constraint satisfaction problems, (Proc. of EUFIT’93, (1993))
[52] Schiex, T.; Fargier, H.; Verfaillie, G., Valued constraint satisfaction problems: hard and easy problems, (Proc. of IJCAI’95, (1995)), 631-637
[53] Cooper, M., High-order consistency in valued constraint satisfaction, Constraints, 10, 3, 283-305, (2005) · Zbl 1112.68118
[54] Bacchus, F.; Chen, X.; van Beek, P.; Walsh, T., Binary vs. non-binary constraints, Artif. Intell., 140, 1-2, 1-37, (2002) · Zbl 0999.68201
[55] Larkin, D.; Dechter, R., Bayesian inference in the presence of determinism, (Proc. of AISTATS’03, (2003))
[56] Fagin, R.; Mendelzon, A.; Ullman, J., A simplified universal relation assumption and its properties, ACM Trans. Database Syst., 7, 3, 343-360, (1982) · Zbl 0488.68069
[57] Gottlob, G.; Leone, N.; Scarcello, F., A comparison of structural CSP decomposition methods, Artif. Intell., 124, 2, 243-282, (2000) · Zbl 0952.68044
[58] Cohen, D.; Jeavons, P.; Gyssens, M., A unified theory of structural tractability for constraint satisfaction problems, J. Comput. Syst. Sci., 74, 5, 721-743, (2008) · Zbl 1151.68640
[59] Greco, G.; Scarcello, F., On the power of structural decompositions of graph-based representations of constraint problems, Artif. Intell., 174, 5-6, 382-409, (2010) · Zbl 1207.68355
[60] Dechter, R.; Pearl, J., Tree clustering for constraint networks, Artif. Intell., 38, 3, 353-366, (1989) · Zbl 0665.68084
[61] Flum, J.; Frick, M.; Grohe, M., Query evaluation via tree-decompositions, J. ACM, 49, 6, 716-752, (2002) · Zbl 1326.68123
[62] Grohe, M., The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1, 1-24, (2007) · Zbl 1312.68101
[63] Grohe, M.; Marx, D., Constraint solving via fractional edge covers, ACM Trans. Algorithms, 11, 1, 1-20, (2014)
[64] Marx, D., Approximating fractional hypertree width, ACM Trans. Algorithms, 6, 2, 1-17, (2010) · Zbl 1300.05201
[65] Fischl, W.; Gottlob, G.; Pichler, R., General and fractional hypertree decompositions: hard and easy cases, short version to appear in Proc. of PODS 2018
[66] Jégou, P.; Terrioux, C., Hybrid backtracking bounded by tree-decomposition of constraint networks, Artif. Intell., 146, 1, 43-75, (2003) · Zbl 1082.68803
[67] Bistarelli, S.; Frühwirth, T.; Marte, M.; Rossi, F., Soft constraint propagation and solving in constraint handling rules, Comput. Intell., 20, 2, 287-307, (2004)
[68] Cooper, M.; Schiex, T., Arc consistency for soft constraints, Artif. Intell., 154, 1-2, 199-227, (2004) · Zbl 1085.68672
[69] Larrosa, J.; Schiex, T., In the quest of the best form of local consistency for weighted CSP, (Proc. of IJCAI’03, (2003)), 239-244
[70] Cooper, M.; de Givry, S.; Sanchez, M.; Schiex, T.; Zytnicki, M.; Werner, T., Soft arc consistency revisited, Artif. Intell., 174, 7-8, 449-478, (2010) · Zbl 1213.68580
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.