You have just completed your registration at OpenAire.
Before you can login to the site, you will need to activate your account.
An e-mail will be sent to you with the proper instructions.
Important!
Please note that this site is currently undergoing Beta testing.
Any new content you create is not guaranteed to be present to the final version
of the site upon release.
In this paper we study the complexity of the (weighted) maximum constr aint satisfaction problem (Max CSP) over an arbitrary finite domain. In this pro blem, one is given a collection of weighted constraints on overlapping sets of v ariables, and the goal is to find an assignment of values to the variables so as to maximize the total weight of satisfied constraints. Max Cut is a typical exa mple of a Max CSP problem. Max CSP is NP-hard in general; however, some restrict ions on the form of constraints may ensure tractability. Recent results indicate that there is a connection between tractability of such restricted problems and supermodularity of the allowed constraint types with respect to some lattice or dering of the domain. We prove several results confirming this. Diamonds are the smallest lattices in terms of the number of comparabilities, and so are as unor dered as a lattice can possibly be. In the present paper, we study Max CSP on di amond-ordered domains. We show that if all allowed constraints are supermodular with respect to such an ordering then the problem can be solved in polynomial (i n fact, in cubic) time. We also prove a partial converse: if the set of allowed constraints includes a certain small family of binary supermodular constraints on such a lattice, then the problem is tractable if and only if all of the allowed constraints are supermodular; otherwise, it is NP-hard.
1. F. B¨orner, A. Bulatov, P. Jeavons, and A. Krokhin. Quantified constraints: Algorithms and complexity. In CSL'03, volume 2803 of LNCS, pages 58-70, 2003.
2. A. Bulatov. A dichotomy theorem for constraints on a 3-element set. In FOCS'02, pages 649-658, 2002.
3. A. Bulatov. Tractable conservative constraint satisfaction problems. In LICS'03, pages 321-330, 2003.
4. A. Bulatov and V. Dalmau. Towards a dichotomy theorem for the counting constraint satisfaction problem. In FOCS'03, pages 562-571, 2003.
5. R.E. Burkard, B. Klinz, and R. Rudolf. Perspectives of Monge properties in optimization. Discrete Applied Mathematics, 70:95-161, 1996.
6. D. Cohen, M. Cooper, and P. Jeavons. A complete characterization of complexity for Boolean constraint optimization problems. In CP'04, volume 3258 of LNCS, 2004.
7. D. Cohen, M. Cooper, P. Jeavons, and A. Krokhin. Soft constraints: complexity and multimorphisms. In CP'03, volume 2833 of LNCS, pages 244-258, 2003.
8. D. Cohen, M. Cooper, P. Jeavons, and A. Krokhin. Identifying efficiently solvable cases of Max CSP. In STACS'04, volume 2996 of LNCS, pages 152-163, 2004.
9. N. Creignou. A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences, 51:511-522, 1995.
10. N. Creignou, S. Khanna, and M. Sudan. Complexity Classifications of Boolean Constraint Satisfaction Problems, volume 7 of SIAM Monographs on Discrete Mathematics and Applications. 2001.
11. M. Datar, T. Feder, A. Gionis, R. Motwani, and R. Panigrahy. A combinatorial algorithm for MAX CSP. Information Processing Letters, 85(6):307-315, 2003.
12. B.A. Davey and H.A. Priestley. Introduction to Lattices and Order. Cambridge University Press, 2nd edition, 2002.
13. B.L. Dietrich and A.J. Hoffman. On greedy algorithms, partially ordered sets, and submodular functions. IBM Journal of Research and Development, 47(1):25-30, 2003.
14. L. Engebretsen and V. Guruswami. Is constraint satisfaction over two variables always easy? Random Structures and Algorithms, 25(2):150-178, 2004.
15. S. Fujishige. Submodular Functions and Optimization, volume 47 of Annals of Discrete Mathematics. North-Holland, 1991.
16. A. Goldberg and R.E. Tarjan. A new approach to the maximum flow problem. J. ACM, 35:921-940, 1988.
17. M. Grohe. The complexity of homomorphism and constraint satisfaction problems seen from the other side. In FOCS'03, pages 552-561, 2003.
18. J. H˚astad. Some optimal inapproximability results. J. ACM, 48:798-859, 2001.
19. S. Iwata, L. Fleischer, and S. Fujishige. A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM, 48(4):761-777, 2001.
20. P. Jonsson. Boolean constraint satisfaction: Complexity results for optimization problems with arbitrary weights. Theoret. Comput. Sci., 244(1-2):189-203, 2000.