The approximability of MAX CSP with fixed-value constraints

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The approximability of MAX CSP with fixed-value constraints

Full text

Pdf (329 KB)

Source

Journal of the ACM (JACM) archive
Volume 55 , Issue 4 (September 2008) table of contents

Article No. 16

Year of Publication: 2008

ISSN:0004-5411

Authors

Vladimir Deineko	University of Warwick, Coventry, UK
Peter Jonsson	Linköpings Universitet, Linköpings, Sweden
Mikael Klasson	Linköpings Universitet, Linköpings, Sweden
Andrei Krokhin	Durham University, Durham, UK

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 7, Downloads (12 Months): 96, Citation Count: 1

Additional Information:

abstract references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1391289.1391290 What is a DOI?

ABSTRACT

In the maximum constraint satisfaction problem (MAX CSP), one is given a finite collection of (possibly weighted) constraints on overlapping sets of variables, and the goal is to assign values from a given finite domain to the variables so as to maximize the number (or the total weight, for the weighted case) of satisfied constraints. This problem is NP-hard in general, and, therefore, it is natural to study how restricting the allowed types of constraints affects the approximability of the problem. In this article, we show that any MAX CSP problem with a finite set of allowed constraint types, which includes all fixed-value constraints (i.e., constraints of the form x = a), is either solvable exactly in polynomial time or else is APX-complete, even if the number of occurrences of variables in instances is bounded. Moreover, we present a simple description of all polynomial-time solvable cases of our problem. This description relies on the well-known algebraic combinatorial property of supermodularity.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Paola Alimonti , Viggo Kann, Some APX-completeness results for cubic graphs, Theoretical Computer Science, v.237 n.1-2, p.123-134, April 28, 2000 [doi>10.1016/S0304-3975(98)00158-3]
	2	Giorgio Ausiello , M. Protasi , A. Marchetti-Spaccamela , G. Gambosi , P. Crescenzi , V. Kann, Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties, Springer-Verlag New York, Inc., Secaucus, NJ, 1999
	3	Bazgan, C., and Karpinski, M. 2005. On the complexity of global constraint satisfaction. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'05). 624--633.
	4	Berman, P., and Karpinski, M. 2003. Improved approximation lower bounds on small occurrence optimization. Tech. Rep. TR03-008, Electronic Colloquium on Computational Complexity (ECCC).
	5	Börner, F., Bulatov, A., Jeavons, P., and Krokhin, A. 2003. Quantified constraints: Algorithms and complexity. In Proceedings of the Workshop on Computer Science Logic (CSL'03). Lecture Notes in Computer Science, vol. 2803. Springer-Verlag, New York, 58--70.
	6	Andrei A. Bulatov, Tractable conservative Constraint Satisfaction Problems, Proceedings of the 18th Annual IEEE Symposium on Logic in Computer Science, p.321, June 22-25, 2003
	7	Andrei A. Bulatov, A dichotomy theorem for constraint satisfaction problems on a 3-element set, Journal of the ACM (JACM), v.53 n.1, p.66-120, January 2006 [doi>10.1145/1120582.1120584]
	8	Andrei A. Bulatov , Víctor Dalmau, Towards a dichotomy theorem for the counting constraint satisfaction problem, Information and Computation, v.205 n.5, p.651-678, May, 2007 [doi>10.1016/j.ic.2006.09.005]
	9	Andrei Bulatov , Peter Jeavons , Andrei Krokhin, Classifying the Complexity of Constraints Using Finite Algebras, SIAM Journal on Computing, v.34 n.3, p.720-742, 2005 [doi>10.1137/S0097539700376676]
	10	Rainer E. Burkard , Bettina Klinz , Rüdiger Rudolf, Perspectives of Monge properties in optimization, Discrete Applied Mathematics, v.70 n.2, p.95-161, Sept. 24, 1996 [doi>10.1016/0166-218X(95)00103-X]
	11	David Cohen , Martin Cooper , Peter Jeavons , Andrei Krokhin, Supermodular functions and the complexity of MAX CSP, Discrete Applied Mathematics, v.149 n.1-3, p.53-72, 1 August 2005 [doi>10.1016/j.dam.2005.03.003]
	12	Nadia Creignou, A dichotomy theorem for maximum generalized satisfiability problems, Journal of Computer and System Sciences, v.51 n.3, p.511-522, Dec. 1995 [doi>10.1006/jcss.1995.1087]
	13	Nadia Creignou , Sanjeev Khanna , Madhu Sudan, Complexity classifications of boolean constraint satisfaction problems, Society for Industrial and Applied Mathematics, Philadelphia, PA, 2001
	14	Mayur Datar , Tomás Feder , Aristides Gionis , Rajeev Motwani , Rina Panigrahy, A combinatorial algorithm for MAX CSP, Information Processing Letters, v.85 n.6, p.307-315, 31 March 2003 [doi>10.1016/S0020-0190(02)00435-0]
	15	Deineko, V., Rudolf, R., and Woeginger, G. 1994. A general approach to avoiding 2 × 2 submatrices. Computing 52, 371--388.
	16	Lars Engebretsen, The Nonapproximability of Non-Boolean Predicates, SIAM Journal on Discrete Mathematics, v.18 n.1, p.114-129, 2005 [doi>10.1137/S0895480100380458]
	17	Tomás Feder , Moshe Y. Vardi, The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory, SIAM Journal on Computing, v.28 n.1, p.57-104, Feb. 1999 [doi>10.1137/S0097539794266766]
	18	Fujishige, S. 2005. Submodular Functions and Optimization, 2nd ed. Annals of Discrete Mathematics, vol. 58. Elsevier.
	19	Gregory Gutin , Arash Rafiey , Anders Yeo , Michael Tso, Level of repair analysis and minimum cost homomorphisms of graphs, Discrete Applied Mathematics, v.154 n.6, p.881-889, 15 April 2006 [doi>10.1016/j.dam.2005.06.012]
	20	Hast, G. 2005. Beating a random assignment: Approximating constraint satisfaction problems. Ph.D. dissertation Royal Institute of Technology, Stockholm, Sweden.
	21	Johan Håstad, On bounded occurrence constraint satisfaction, Information Processing Letters, v.74 n.1-2, p.1-6, April 2000 [doi>10.1016/S0020-0190(00)00032-6]
	22	Johan Håstad, Some optimal inapproximability results, Journal of the ACM (JACM), v.48 n.4, p.798-859, July 2001 [doi>10.1145/502090.502098]
	23	Johan Håstad, Every 2-CSP allows nontrivial approximation, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060700]
	24	Hell, P. 2003. Algorithmic aspects of graph homomorphisms. In Surveys in Combinatorics 2003, C. Wensley, Ed. LMS Lecture Note Series, vol. 307. Cambridge University Press, Cambridge, MA, 239--276.
	25	Hell, P., and Nešetřil, J. 2004. Graphs and Homomorphisms. Oxford University Press.
	26	Satoru Iwata , Lisa Fleischer , Satoru Fujishige, A combinatorial strongly polynomial algorithm for minimizing submodular functions, Journal of the ACM (JACM), v.48 n.4, p.761-777, July 2001 [doi>10.1145/502090.502096]
	27	Peter Jonsson, Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights, Theoretical Computer Science, v.244 n.1-2, p.189-203, Aug. 6, 2000 [doi>10.1016/S0304-3975(98)00343-0]
	28	Peter Jonsson , Mikael Klasson , Andrei Krokhin, The Approximability of Three-valued MAX CSP, SIAM Journal on Computing, v.35 n.6, p.1329-1349, 2006 [doi>10.1137/S009753970444644X]
	29	Peter Jonsson , Andrei Krokhin, Maximum H-colourable subdigraphs and constraint optimization with arbitrary weights, Journal of Computer and System Sciences, v.73 n.5, p.691-702, August, 2007 [doi>10.1016/j.jcss.2007.02.001]
	30	Marek Karpinski, Approximating Bounded Degree Instances of NP-Hard Problems, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory, p.24-34, August 22-24, 2001
	31	Sanjeev Khanna , Madhu Sudan , Luca Trevisan , David P. Williamson, The Approximability of Constraint Satisfaction Problems, SIAM Journal on Computing, v.30 n.6, p.1863-1920, 2001 [doi>10.1137/S0097539799349948]
	32	Subhash Khot , Guy Kindler , Elchanan Mossel , Ryan O’Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM Journal on Computing, v.37 n.1, p.319-357, April 2007 [doi>10.1137/S0097539705447372]
	33	Bettina Klinz , Rüdiger Rudolf , Gerhard J. Woeginger, Permuting matrices to avoid forbidden submatrices, Discrete Applied Mathematics, v.60 n.1-3, p.223-248, June 23, 1995 [doi>10.1016/0166-218X(94)00054-H]
	34	Krokhin, A., Bulatov, A., and Jeavons, P. 2005. The complexity of constraint satisfaction: an algebraic approach. In Structural Theory of Automata, Semigroups, and Universal Algebra. NATO Science Series II: Math., Phys., Chem., vol. 207. Springer Verlag, New York, 181--213.
	35	Andrei Krokhin , Benoit Larose, Maximizing Supermodular Functions on Product Lattices, with Application to Maximum Constraint Satisfaction, SIAM Journal on Discrete Mathematics, v.22 n.1, p.312-328, February 2008 [doi>10.1137/060669565]
	36	Itsik Pe'er , Tal Pupko , Ron Shamir , Roded Sharan, Incomplete Directed Perfect Phylogeny, SIAM Journal on Computing, v.33 n.3, p.590-607, 2004 [doi>10.1137/S0097539702406510]
	37	Rüdiger Rudolf, Recognition of d-dimensional Monge arrays, Discrete Applied Mathematics, v.52 n.1, p.71-82, July 22, 1994 [doi>10.1016/0166-218X(92)00189-S]
	38	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	39	Alexander Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time, Journal of Combinatorial Theory Series B, v.80 n.2, p.346-355, Nov. 2000 [doi>10.1006/jctb.2000.1989]
	40	Topkis, D. 1998. Supermodularity and Complementarity. Princeton University Press, Princeton, NJ.
	41	Ryan Williams, A new algorithm for optimal 2-constraint satisfaction and its implications, Theoretical Computer Science, v.348 n.2, p.357-365, 8 December 2005 [doi>10.1016/j.tcs.2005.09.023]