Abstract
Several variants of the Constraint Satisfaction Problem have been proposed and investigated in the literature for modeling those scenarios where solutions are associated with costs. Within these frameworks, computing an optimal solution (short: Min problem), enumerating the best K solutions (Top- K), and computing the next solution following one that is given at hand (Next) are all \(\mbox{\rm NP}\)-hard problems. In fact, only some restricted islands of tractability for them have been singled out in the literature. The paper fills the gap, by studying the complexity of Min, Top- K, and Next over classes of acyclic and nearly acyclic instances, as they can be identified via structural decomposition methods. The analysis is provided for both monotone cost-functions and non-monotone ones (which have been largely ignored so far). Also, multi-criteria optimization is considered, as instances may have a number of cost functions to be minimized together, according to a given precedence relationship. Large islands of tractability are identified and, for classes of bounded-arity instances, the tractability frontier of constraint optimization is precisely charted.
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
Bernstein, P.A., Goodman, N.: The power of natural semijoins. SIAM Journal on Computing 10(4), 751–771 (1981)
Bistarelli, S., Montanari, U., Rossi, F., Schiex, T., Verfaillie, G., Fargier, H.: Semiring-Based CSPs and Valued CSPs: Frameworks, Properties, and Comparison. Constraints 4(3), 199–240 (1999)
Brafman, R.I., Rossi, F., Salvagnin, D., Venable, K.B., Walsh, T.: Finding the Next Solution in Constraint- and Preference-Based Knowledge Representation Formalisms. In: Proc. of KR 2010, pp. 425–433 (2010)
Bulatov, A., Dalmau, V., Grohe, M., Marx, D.: Enumerating Homomorphism. In: Proc. of STACS 2009, pp. 231–242 (2009)
Chen, H., Dalmau, V.: Beyond Hypertree Width: Decomposition Methods Without Decompositions. In: van Beek, P. (ed.) CP 2005. LNCS, vol. 3709, pp. 167–181. Springer, Heidelberg (2005)
Cohen, D.A., Jeavons, P., Gyssens, M.: A unified theory of structural tractability for constraint satisfaction problems. J. of Computer and System Sciences 74(5), 721–743 (2008)
Dechter, R.: Constraint Processing. Morgan Kaufmann, San Francisco (2003)
Flerova, N., Dechter, R.: M best solutions over Graphical Models. In: Proc. of Constraint Reasoning and Graphical Structures, CP 2010 Workshop (2010)
Flum, J., Frick, M., Grohe, M.: Query evaluation via tree-decompositions. Journal of the ACM 49(6), 716–752 (2002)
de Givry, S., Schiex, T., Verfaillie, G.: Exploiting Tree Decomposition and Soft Local Consistency In Weighted CSP. In: Proc. of AAAI 2006 (2006)
Gottlob, G., Greco, G., Scarcello, F.: Tractable Optimization Problems through Hypergraph-Based Structural Restrictions. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol. 5556, pp. 16–30. Springer, Heidelberg (2009)
Gottlob, G., Leone, N., Scarcello, F.: A comparison of structural CSP decomposition methods. Artificial Intelligence 124(2), 243–282 (2000)
Gottlob, G., Leone, N., Scarcello, F.: Computing LOGCFL Certificates. Theoretical Computer Science 270(1-2), 761–777 (2002)
Gottlob, G., Leone, N., Scarcello, F.: Hypertree decompositions and tractable queries. J. of Computer and System Sciences 64(3), 579–627 (2002)
Gottlob, G., Miklós, Z., Schwentick, T.: Generalized hypertree decompositions: \(\mbox{\rm NP}\)-hardness and tractable variants. Journal of the ACM 56(6) (2009)
Greco, G., Scarcello, F.: The power of tree projections: local consistency, greedy algorithms, and larger islands of tractability. In: Proc. of PODS 2010, pp. 327–338 (2010)
Greco, G., Scarcello, F.: Structural Tractability of Enumerating CSP Solutions. In: Cohen, D. (ed.) CP 2010. LNCS, vol. 6308, pp. 236–251. Springer, Heidelberg (2010)
Greco, G., Scarcello, F.: The tractability frontier of computing K best solutions. Techinical Report, University of Calabria (2011)
Grohe, M., Marx, D.: Constraint solving via fractional edge covers. In: Proc. of SODA 2006, pp. 289–298 (2006)
Grohe, M.: The complexity of homomorphism and constraint satisfaction problems seen from the other side. Journal of the ACM 54(1) (2007)
Kimelfeld, B., Sagiv, Y.: Incrementally computing ordered answers of acyclic conjunctive queries. In: Etzion, O., Kuflik, T., Motro, A. (eds.) NGITS 2006. LNCS, vol. 4032, pp. 33–38. Springer, Heidelberg (2006)
Kolaitis, P.G., Vardi, M.Y.: Conjunctive-query containment and constraint satisfaction. Journal of Computer and System Sciences 61(2), 302–332 (1998)
Lawler, E.L.: A procedure for computing the k best solutions to discrete optimization problems and its application to the shortest path problem. Management Science 18, 401–405 (1972)
Marx, D.: Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries. In: Proc. of STOC 2010, pp. 735–744 (2010)
Meseguer, P., Rossi, F., Schiex, T.: Soft Constraints. In: Handbook of Constraint Programming. Elsevier, Amsterdam (2006)
Ndiaye, S., Jégou, P., Terrioux, C.: Extending to Soft and Preference Constraints a Framework for Solving Efficiently Structured Problems. In: Proc. of ICTAI 2008, pp. 299–306 (2008)
Robertson, N., Seymour, P.D.: Graph minors III: Planar tree-width. Journal of Combinatorial Theory, Series B 36, 49–64 (1984)
Robertson, N., Seymour, P.D.: Graph minors V: Excluding a planar graph. Journal of Combinatorial Theory, Series B 41, 92–114 (1986)
Ruzzo, W.L.: Tree-size bounded alternation. Journal of Cumputer and System Sciences 21, 218–235 (1980)
Yannakakis, M.: Algorithms for acyclic database schemes. In: Proc. of VLDB 1981, pp. 82–94 (1981)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Greco, G., Scarcello, F. (2011). Structural Tractability of Constraint Optimization. In: Lee, J. (eds) Principles and Practice of Constraint Programming – CP 2011. CP 2011. Lecture Notes in Computer Science, vol 6876. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-23786-7_27
Download citation
DOI: https://doi.org/10.1007/978-3-642-23786-7_27
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-23785-0
Online ISBN: 978-3-642-23786-7
eBook Packages: Computer ScienceComputer Science (R0)