Complexity of clausal constraints over chains

Creignou, N.; Hermann, M.; Krokhin, A.; Salzer, G.

Abstract

We investigate the complexity of the satisfiability problem of constraints over finite totally ordered domains. In our context, a clausal constraint is a disjunction of inequalities of the form x≥d and x≤d. We classify the complexity of constraints based on clausal patterns. A pattern abstracts away from variables and contains only information about the domain elements and the type of inequalities occurring in a constraint. Every finite set of patterns gives rise to a (clausal) constraint satisfaction problem in which all constraints in instances must have an allowed pattern. We prove that every such problem is either polynomially decidable or NP-complete, and give a polynomial-time algorithm for recognizing the tractable cases. Some of these tractable cases are new and have not been previously identified in the literature.

Citation

Creignou, N., Hermann, M., Krokhin, A., & Salzer, G. (2008). Complexity of clausal constraints over chains. Theory of Computing Systems, 42(2), 239-255. https://doi.org/10.1007/s00224-007-9003-z

• Journal Article Type: Article
• Publication Date: Feb 1, 2008
• Deposit Date: Dec 15, 2009
• Journal: Theory of Computing Systems
• Print ISSN: 1432-4350
• Electronic ISSN: 1433-0490
• Publisher: Springer
• Peer Reviewed: Peer Reviewed
• Volume: 42
• Issue: 2
• Pages: 239-255
• DOI: https://doi.org/10.1007/s00224-007-9003-z
• Keywords: Constraint satisfaction problems, Complexity, Finite totally ordered domains, Inequalities, Clausal patterns, Dichotomy theorem.
• Public URL: https://durham-repository.worktribe.com/output/1555005
• Publisher URL: http://www.springerlink.com/content/95406v1j434gv835/