Abstract
We study the computational complexity of Boolean constraint satisfaction problems with cardinality constraint. A Galois connection between clones and co-clones has received a lot of attention in the context of complexity considerations for constraint satisfaction problems. This connection fails when considering constraint satisfaction problems that support in addition a cardinality constraint. We prove that a similar Galois connection, involving a weaker closure operator and partial polymorphisms, can be applied to such problems. Thus, we establish dichotomies for the decision as well as for the counting problems in Schaefer’s framework.
Supported by the DAAD postdoc program. Work done in part while the second and third authors worked at the University of Hannover.
This is a preview of subscription content, log in via an institution to check access.
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
Allender, E., Bauland, M., Immerman, N., Schnoor, H., Vollmer, H.: The complexity of satisfiability problems: Refining Schaefer’s theorem. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 71–82. Springer, Heidelberg (2005)
Böhler, E., Creignou, N., Reith, S., Vollmer, H.: Playing with Boolean blocks, part I: Post’s lattice with applications to complexity theory. ACM-SIGACT Newsletter 34(4), 38–52 (2003)
Bauland, M., Hemaspaandra, E.: Isomorphic implication. In: Jedrzejowicz, J., Szepietowski, A. (eds.) MFCS 2005. LNCS, vol. 3618, pp. 119–130. Springer, Heidelberg (2005); Theory of Computing Systems (to appear)
Bläser, M., Heynen, T., Manthey, B.: Adding cardinality constraints to integer programs with applications to maximum satisfiability. Information Processing Letters 105, 194–198 (2008)
Böhler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: Equivalence and isomorphism for Boolean constraint satisfaction. In: Bradfield, J.C. (ed.) CSL 2002 and EACSL 2002. LNCS, vol. 2471, pp. 412–426. Springer, Heidelberg (2002)
Böhler, E., Hemaspaandra, E., Reith, S., Vollmer, H.: The complexity of Boolean constraint isomorphism. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 164–175. Springer, Heidelberg (2004)
Bazgan, C., Karpinski, M.: On the complexity of global constraint satisfaction. In: Deng, X., Du, D. (eds.) ISAAC 2005. LNCS, vol. 3827, pp. 624–633. Springer, Heidelberg (2005)
Bodnarchuk, V.G., Kalužnin, L.A., Kotov, V.N., Romov, B.A.: Galois theory for Post algebras I, II. Cybernetics 5, 243–252, 531–539 (1969)
Böhler, E., Reith, S., Schnoor, H., Vollmer, H.: Bases for Boolean co-clones. Information Processing Letters 96, 59–66 (2005)
Creignou, N., Hermann, M.: Complexity of generalized satisfiability counting problems. Information and Computation 125, 1–12 (1996)
Creignou, N., Kolaitis, P., Zanuttini, B.: Structure identification for Boolean relations and plain bases for co-clones. Journal of Computer and System Sciences (in press, 2008)
Creignou, N.: A dichotomy theorem for maximum generalized satisfiability problems. Journal of Computer and System Sciences 51, 511–522 (1995)
Creignou, N., Vollmer, H.: Boolean constraint satisfaction problems: when does Post’s lattice help? In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. Springer, Heidelberg (to appear, 2008)
Creignou, N., Zanuttini, B.: A complete classification of the complexity of propositional abduction. SIAM Journal on Computing 36(1), 207–229 (2006)
Geiger, D.: Closed systems of functions and predicates. Pac. J. Math. 27(2), 228–250 (1968)
Garey, M.R., Johnson, D.S.: Computers and Intractability, A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Jeavons, P.G.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200, 185–204 (1998)
Kirousis, L.M., Kolaitis, P.G.: The complexity of minimal satisfiability problems. Information and Computation 187(1), 20–39 (2003)
Khanna, S., Sudan, M., Trevisan, L., Williamson, D.P.: The approximability of constraint satisfaction problems. SIAM Journal on Computing 30, 1863–1920 (2001)
Marx, D.: Parameterized complexity of constraint satisfaction problems. Computational Complexity 14(2), 153–183 (2005)
Post, E.L.: The two-valued iterative systems of mathematical logic. Annals of Mathematical Studies 5, 1–122 (1941)
Romov, B.A.: The algebras of partial functions and their invariants. Cybernetics and Systems Analysis 17(2), 157–167 (1981)
Reith, S., Vollmer, H.: Optimal satisfiability for propositional calculi and constraint satisfaction problems. Information and Computation 186(1), 1–19 (2003)
Schaefer, T.J.: The complexity of satisfiability problems. In: Proccedings 10th Symposium on Theory of Computing, pp. 216–226. ACM Press, New York (1978)
Schnoor, H., Schnoor, I.: Partial polymorphisms and constraint satisfaction problems. In: Creignou, N., Kolaitis, P.G., Vollmer, H. (eds.) Complexity of Constraints. Springer, Heidelberg (to appear, 2008)
Sviridenko, M.I.: Best possible approximation algorithm for MAX-SAT with cardinality constraint. Algorithmica 30(3), 398–405 (2001)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Creignou, N., Schnoor, H., Schnoor, I. (2008). Non-uniform Boolean Constraint Satisfaction Problems with Cardinality Constraint. In: Kaminski, M., Martini, S. (eds) Computer Science Logic. CSL 2008. Lecture Notes in Computer Science, vol 5213. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-87531-4_10
Download citation
DOI: https://doi.org/10.1007/978-3-540-87531-4_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-87530-7
Online ISBN: 978-3-540-87531-4
eBook Packages: Computer ScienceComputer Science (R0)