Tree projections and constraint optimization problems: Fixed-parameter tractability and parallel algorithms

Dechter, 2003 Bistarelli, 1996, Semiring-based CSPs and valued CSPs: basic properties and comparison, 111 Flerova, 2016, Searching for the M best solutions in graphical models, J. Artif. Intell. Res., 55, 889, 10.1613/jair.4985 Bulatov, 2012, Enumerating homomorphisms, J. Comput. Syst. Sci., 78, 638, 10.1016/j.jcss.2011.09.006 Brafman, 2010, Finding the next solution in constraint- and preference-based knowledge representation formalisms, 425 Montanari, 1974, Networks of constraints: fundamental properties and applications to picture processing, Inf. Sci., 7, 95, 10.1016/0020-0255(74)90008-5 Yannakakis, 1981, Algorithms for acyclic database schemes, 82 Fagin, 1983, Degrees of acyclicity for hypergraphs and relational database schemes, J. ACM, 30, 514, 10.1145/2402.322390 Gottlob, 2016, Hypertree decompositions: questions and answers, 57 Kimelfeld, 2006, Incrementally computing ordered answers of acyclic conjunctive queries, 33 Gottlob, 2009, Tractable optimization problems through hypergraph-based structural restrictions, 16 Greco, 2011, Structural tractability of constraint optimization, 340 Marx, 2013, Tractable hypergraph properties for constraint satisfaction and conjunctive queries, J. ACM, 60, 42:1, 10.1145/2535926 Goodman, 1984, The tree projection theorem and relational query processing, J. Comput. Syst. Sci., 28, 60, 10.1016/0022-0000(84)90076-X Sagiv, 1993, Solving queries by tree projections, ACM Trans. Database Syst., 18, 487, 10.1145/155271.155277 Gottlob, 2009, Generalized hypertree decompositions: NP-hardness and tractable variants, J. ACM, 56, 1, 10.1145/1568318.1568320 Greco, 2017, Greedy strategies and larger islands of tractability for conjunctive queries and constraint satisfaction problems, Inf. Comput., 252, 201, 10.1016/j.ic.2016.11.004 Robertson, 1986, Graph minors. II. Algorithmic aspects of tree-width, J. Algorithms, 7, 309, 10.1016/0196-6774(86)90023-4 Gottlob, 2002, Hypertree decompositions and tractable queries, J. Comput. Syst. Sci., 64, 579, 10.1006/jcss.2001.1809 Chen, 2005, Beyond hypertree width: decomposition methods without decompositions, 167 Greco, 2017, The power of local consistency in conjunctive queries and constraint satisfaction problems, SIAM J. Comput., 1111, 10.1137/16M1090272 Beeri, 1983, On the desirability of acyclic database schemes, J. ACM, 30, 479, 10.1145/2402.322389 Gyssens, 1986, On the complexity of join dependencies, ACM Trans. Database Syst., 11, 81, 10.1145/5236.5237 Karakashian, 2010, A first practical algorithm for high levels of relational consistency, 101 Kask, 2005, Unifying tree decompositions for reasoning in graphical models, Artif. Intell., 166, 165, 10.1016/j.artint.2005.04.004 Bistarelli, 1997, Semiring-based constraint satisfaction and optimization, J. ACM, 44, 201, 10.1145/256303.256306 Terrioux, 2003, Bounded backtracking for the valued constraint satisfaction problems, 709 Gottlob, 2013, Decomposing combinatorial auctions and set packing problems, J. ACM, 60, 1, 10.1145/2508028.2505987 Joglekar Abo Khamis, 2016, Faq: questions asked frequently, 13 Lauritzen, 1990, Local computations with probabilities on graphical structures and their application to expert systems, 415 Downey, 2012 Kolaitis, 2000, Conjunctive-query containment and constraint satisfaction, J. Comput. Syst. Sci., 61, 302, 10.1006/jcss.2000.1713 Bernstein, 1981, Power of natural semijoins, SIAM J. Comput., 10, 751, 10.1137/0210059 Greco, 2013, Structural tractability of enumerating CSP solutions, Constraints, 18, 38, 10.1007/s10601-012-9129-8 Lawler, 1972, A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem, Manag. Sci., 18, 401, 10.1287/mnsc.18.7.401 Kasif, 1990, On the parallel complexity of discrete relaxation in constraint satisfaction networks, Artif. Intell., 45, 275, 10.1016/0004-3702(90)90009-O Gottlob, 2001, The complexity of acyclic conjunctive queries, J. ACM, 48, 431, 10.1145/382780.382783 Gottlob, 2002, Computing LOGCFL certificates, Theor. Comput. Sci., 270, 761, 10.1016/S0304-3975(01)00108-6 Gottlob, 1998 Greco, 2014, Tree projections and structural decomposition methods: minimality and game-theoretic characterization, Theor. Comput. Sci., 522, 95, 10.1016/j.tcs.2013.12.012 Karp, 1990, Parallel algorithms for shared-memory machines, 869 Gent, 2011, A preliminary review of literature on parallel constraint solving Valiant, 2011, A bridging model for multi-core computing, J. Comput. Syst. Sci., 77, 154, 10.1016/j.jcss.2010.06.012 Vishkin, 2011, Using simple abstraction to reinvent computing for parallelism, Commun. ACM, 54, 75, 10.1145/1866739.1866757 Afrati, 2017, GYM: a multiround distributed join algorithm, 4:1 Dubois, 1993, The calculus of fuzzy restrictions as a basis for flexible constraint satisfaction, 1131 Fargier, 1993, Uncertainty in constraint satisfaction problems: a probabilistic approach, 97 Schiex, 1992, Possibilistic constraint satisfaction problems or “how to handle soft constraints?”, 268 Freuder, 1992, Partial constraint satisfaction, Artif. Intell., 58, 21, 10.1016/0004-3702(92)90004-H Fargier, 1993, Selecting preferred solutions in fuzzy constraint satisfaction problems Schiex, 1995, Valued constraint satisfaction problems: hard and easy problems, 631 Cooper, 2005, High-order consistency in valued constraint satisfaction, Constraints, 10, 283, 10.1007/s10601-005-2240-3 Bacchus, 2002, Binary vs. non-binary constraints, Artif. Intell., 140, 1, 10.1016/S0004-3702(02)00210-2 Larkin, 2003, Bayesian inference in the presence of determinism Fagin, 1982, A simplified universal relation assumption and its properties, ACM Trans. Database Syst., 7, 343, 10.1145/319732.319735 Gottlob, 2000, A comparison of structural CSP decomposition methods, Artif. Intell., 124, 243, 10.1016/S0004-3702(00)00078-3 Cohen, 2008, A unified theory of structural tractability for constraint satisfaction problems, J. Comput. Syst. Sci., 74, 721, 10.1016/j.jcss.2007.08.001 Greco, 2010, On the power of structural decompositions of graph-based representations of constraint problems, Artif. Intell., 174, 382, 10.1016/j.artint.2009.12.004 Dechter, 1989, Tree clustering for constraint networks, Artif. Intell., 38, 353, 10.1016/0004-3702(89)90037-4 Flum, 2002, Query evaluation via tree-decompositions, J. ACM, 49, 716, 10.1145/602220.602222 Grohe, 2007, The complexity of homomorphism and constraint satisfaction problems seen from the other side, J. ACM, 54, 1, 10.1145/1206035.1206036 Grohe, 2014, Constraint solving via fractional edge covers, ACM Trans. Algorithms, 11, 1, 10.1145/2636918 Marx, 2010, Approximating fractional hypertree width, ACM Trans. Algorithms, 6, 1, 10.1145/1721837.1721845 Fischl Jégou, 2003, Hybrid backtracking bounded by tree-decomposition of constraint networks, Artif. Intell., 146, 43, 10.1016/S0004-3702(02)00400-9 Bistarelli, 2004, Soft constraint propagation and solving in constraint handling rules, Comput. Intell., 20, 287, 10.1111/j.0824-7935.2004.00239.x Cooper, 2004, Arc consistency for soft constraints, Artif. Intell., 154, 199, 10.1016/j.artint.2003.09.002 Larrosa, 2003, In the quest of the best form of local consistency for weighted CSP, 239 Cooper, 2010, Soft arc consistency revisited, Artif. Intell., 174, 449, 10.1016/j.artint.2010.02.001