article

An efficient algorithm for a class of constraint satisfaction problems

Author:

Gerhard J. WoegingerAuthors Info & Claims

Operations Research Letters, Volume 30, Issue 1

Pages 9 - 16

https://doi.org/10.1016/S0167-6377(01)00114-6

Published: 01 February 2002 Publication History

Abstract

We define the class of the so-called monotone constraint satisfaction problems (MON-CSP). MON-CSP forms a subclass of the class of min-closed (respectively, max-closed) constraint satisfaction problems of Jeavons and Cooper (Artificial Intelligence 79 (1995) 327). We prove that for all problems in the class MON-CSP there exists a very fast and very simple algorithm for testing feasibility. We then show that a number of well-known results from the literature are special cases of MON-CSP: (1) Satisfiability of Horn formulae; (2) graph homomorphisms to directed graphs with an X@?-numbering; (3) monotone integer programming with two variables per inequality; (4) project scheduling under AND/OR precedence constraints. Our results provide a unified algorithmic approach to all these problems.

References

[1]

Dowling, W.F. and Gallier, J.H., Linear time algorithms for testing satisfiability of propositional Horn formulae. J. Logic Programming. v1. 267-284.

Google Scholar

[2]

Garey, M.R. and Johnson, D.S., . 1979. Freeman, San Francisco.

Google Scholar

[3]

Gutjahr, W., Welzl, E. and Woeginger, G.J., Polynomial graph-colorings. Discrete Appl. Math. v35. 29-45.

Crossref

Google Scholar

[4]

Hell, P. and Nešetřil, J., On the complexity of H-coloring. J. Combin. Theory (B). v48. 92-110.

Crossref

Google Scholar

[5]

Hochbaum, D.S. and Naor, J., Simple and fast algorithms for linear and integer programs with two variables per inequality. SIAM J. Comput. v23. 1179-1192.

Crossref

Google Scholar

[6]

Jeavons, P.G., Cohen, D. and Cooper, M.C., Constraints, consistency, and closure. Artificial Intelligence. v101. 251-265.

Crossref

Google Scholar

[7]

Jeavons, P.G., Cohen, D. and Gyssens, M., Closure properties of constraints. J. ACM. v44. 527-548.

Crossref

Google Scholar

[8]

Jeavons, P.G. and Cooper, M.C., Tractable constraints on ordered domains. Artificial Intelligence. v79. 327-339.

Crossref

Google Scholar

[9]

Lagarias, J.C., The computational complexity of simultaneous diophantine approximation problems. SIAM J. Comput. v14. 196-209.

Crossref

Google Scholar

[10]

R.H. Moehring, M. Skutella, F. Stork, Scheduling with AND/OR precedence constraints, Report No. 689/2000, TU Berlin, Germany, 2000.

Google Scholar

[11]

Papadimitriou, C.H., . 1994. Addison-Wesley, Reading, MA.

Google Scholar

[12]

Schwiegelshohn, U. and Thiele, L., Dynamic min-max problems. Discrete Event Dynamic Systems. v9. 111-134.

Crossref

Google Scholar

[13]

van Hentenryck, P., Deville, Y. and Teng, C.-M., A generic arc-consistency algorithm and its specializations. Artificial Intelligence. v57. 291-321.

Crossref

Google Scholar

[14]

Zwick, U. and Paterson, M., The complexity of mean payoff games on graphs. Theoret. Comput. Sci. v158. 343-359.

Digital Library

Google Scholar

Cited By

View all

Mitra SDutta PBhattacharya AChakraborty PGupta MDey LRoy S(2017)Optimal Algorithms for Min-Closed, Max-Closed and Arc Consistency over Connected Row Convex ConstraintsProceedings of the 10th Annual ACM India Compute Conference10.1145/3140107.3140110(61-72)Online publication date: 16-Nov-2017
https://dl.acm.org/doi/10.1145/3140107.3140110
Bessiere CPetit TZanuttini B(2009)Making bound consistency as effective as arc consistencyProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661513(425-430)Online publication date: 11-Jul-2009
https://dl.acm.org/doi/10.5555/1661445.1661513
Jonsson PNordh G(2008)Introduction to the Maximum Solution ProblemComplexity of Constraints10.1007/978-3-540-92800-3_10(255-282)Online publication date: 23-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-92800-3_10

An efficient algorithm for a class of constraint satisfaction problems
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Machine learning theory
      1. Reinforcement learning

Recommendations

Bounded-degree forbidden patterns problems are constraint satisfaction problems
CSR'06: Proceedings of the First international computer science conference on Theory and Applications

Forbidden Patterns problem (FPP) is a proper generalisation of Constraint Satisfaction Problem (CSP). FPP was introduced in [1] as a combinatorial counterpart of MMSNP, a logic which was in turn introduced in relation to CSP by Feder and Vardi [2]. We ...
A pre-processing algorithm for solving constraint satisfaction optimisation problems
SAICSIT '03: Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology

A constraint satisfaction problem (CSP) involves finding values, selected from a finite domain, for all variables such that all constraints on the variables are satisfied. A constraint satisfaction optimisation problem (CSOP) is a CSP that has some ...
Solving conditional and composite constraint satisfaction problems
SAC '07: Proceedings of the 2007 ACM symposium on Applied computing

Constraint Satisfaction Problems (CSPs) have been widely used to solve combinatorial problems. In order to deal with dynamic CSPs where the information regarding any possible change is known a priori and can thus be enumerated beforehand, conditional ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Operations Research Letters Volume 30, Issue 1

February, 2002

71 pages

ISSN:0167-6377

Issue’s Table of Contents

Publisher

Elsevier Science Publishers B. V.

Netherlands

Publication History

Published: 01 February 2002

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 27 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Mitra SDutta PBhattacharya AChakraborty PGupta MDey LRoy S(2017)Optimal Algorithms for Min-Closed, Max-Closed and Arc Consistency over Connected Row Convex ConstraintsProceedings of the 10th Annual ACM India Compute Conference10.1145/3140107.3140110(61-72)Online publication date: 16-Nov-2017
https://dl.acm.org/doi/10.1145/3140107.3140110
Bessiere CPetit TZanuttini B(2009)Making bound consistency as effective as arc consistencyProceedings of the 21st International Joint Conference on Artificial Intelligence10.5555/1661445.1661513(425-430)Online publication date: 11-Jul-2009
https://dl.acm.org/doi/10.5555/1661445.1661513
Jonsson PNordh G(2008)Introduction to the Maximum Solution ProblemComplexity of Constraints10.1007/978-3-540-92800-3_10(255-282)Online publication date: 23-Dec-2008
https://dl.acm.org/doi/10.1007/978-3-540-92800-3_10

Abstract

References

Cited By

Recommendations

Bounded-degree forbidden patterns problems are constraint satisfaction problems

A pre-processing algorithm for solving constraint satisfaction optimisation problems

Solving conditional and composite constraint satisfaction problems

Comments

Information

Published In

Publisher

Publication History

Author Tags

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

Share

Share this Publication link

Share on social media

Affiliations