Abstract
We study interval-valued constraint satisfaction problems (CSPs), in which the aim is to find an assignment of intervals to a given set of variables subject to constraints on the relative positions of intervals. One interesting question concerning such problems is to determine exactly how the complexity of an interval-valued CSP depends on the set of constraints allowed in instances. For the framework known as Allen’s interval algebra this question was completely answered earlier by the authors.
Here we extend the qualitative framework of Allen’s algebra with additional constraints on the lengths of intervals. We allow these length constraints to be expressed as Horn disjunctive linear relations, a wellknown tractable and sufficiently expressive form of constraints. We completely characterize sets of qualitative relations for which the constraint satisfaction problem augmented with arbitrary length constraints of the above form is tractable. We also show that all the remaining cases are NP-complete.
Partially supported by the UK EPSRC grant GR/R29598.
Partially supported by the Swedish Research Council (VR) under grant 221-2000- 361.
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
Montanari, U.: Networks of constraints: Fundamental properties and applications to picture processing. Information Sciences 7 (1974) 95–132
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, New York (1979)
Angelsmark, O., Jonsson, P.: Some observations on durations, scheduling and Allen’s algebra. In: Proceedings of the 6th Conference on Constraint Programming (CP’00). Volume 1894 of Lecture Notes in Computer Science., Springer-Verlag (2000) 484–488
Jeavons, P.: On the algebraic structure of combinatorial problems. Theoretical Computer Science 200 (1998) 185–204
Schaefer, T.: The complexity of satisfiability problems. In: Proceedings of the 10th Symposium on the Theory of Computing (STOC’78), New-York, ACM Press (1978) 216–226
Hell, P., Nešetřil, J.: On the complexity of H-coloring. Journal of Combinatorial Theory, Ser. B 48(1990) 92–110
Allen, J.: Maintaining knowledge about temporal intervals. Communications of the ACM 26(1983) 832–843
Golumbic, M., Shamir, R.: Complexity and algorithms for reasoning about time: A graph-theoretic approach. Journal of the ACM 40(1993) 1108–1133
Krokhin, A., Jeavons, P., Jonsson, P.: Reasoning about temporal relations: Tractable subalgebras of Allen’s interval algebra. Technical Report RR-01-12, Oxford University Computing Laboratory (2001) Submitted for publication.
Nebel, B., Bürckert, H.J.: Reasoning about temporal relations: A maximal tractable subclass of Allen’s interval algebra. Journal of the ACM 42 (1995) 43–66
Goldberg, P., Golumbic, M., Kaplan, H., Shamir, R.: Four strikes against physical mapping of DNA. Journal of Computational Biology 2 (1995) 139–152
Golumbic, M., Kaplan, H., Shamir, R.: On the complexity of DNA physical mapping. Advances in Applied Mathematics 15(1994) 251–261
Karp, R.: Mapping the genome: some combinatorial problems arising in molecular biology. In: Proceedings of the 25th Symposium on the Theory of Computing (STOC’93), New-York, ACM Press (1993) 278–285
Hsu, W.L.: A simple test for interval graphs. In Hsu, W.L., Lee, R., eds.: Proceedings of the 18th InternationalWorkshop on Graph-Theoretic Concepts in Computer Science. Volume 657 of Lecture Notes in Computer Science., Springer (1992) 11–16
Corneil, D., Kim, H., Natarajan, S., Olariu, S., Sprague, A.: Simple linear time recognition of unit interval graphs. Information Processing Letters 55(1995) 99–104
Peér, I., Shamir, R.: Realizing interval graphs with size and distance constraints. SIAM Journal on Discrete Mathematics 10 (1997) 662–687
Gabor, C., Supowit, K., Hsu, W.: Recognizing circle graphs in polynomial time. Journal of the ACM 36 (1989) 435–473
Golumbic, M., Kaplan, H., Shamir, R.: Graph sandwich problems. Journal of Algorithms 19 (1995) 449–473
Peér, I., Shamir, R.: Satisfiability problems on intervals and unit intervals. Theoretical Computer Science 175 (1997) 349–372
Webber, A.: Proof of the interval satisfiability conjecture. Annals of Mathematics and Artificial Intelligence 15 (1995) 231–238
Drakengren, T., Jonsson, P.: Eight maximal tractable subclasses of Allen’s algebra with metric time. Journal of Artificial Intelligence Research7 (1997) 25–45
Drakengren, T., Jonsson, P.: A complete classification of tractability in Allen’s algebra relative to subsets of basic relations. Artificial Intelligence 106 (1998) 205–219
Jonsson, P., Bäckström, C.: A unifying approach to temporal constraint reasoning. Artificial Intelligence 102 (1998) 143–155
Koubarakis, M.: Tractable disjunctions of linear constraints: basic results and applications to temporal reasoning. Theoretical Computer Science 266 (2001) 311–339
Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoretical Computer Science 10 (1980) 111–121
Creignou, N., Khanna, S., Sudan, M.: Complexity Classification of Boolean Constraint Satisfaction Problems. Volume 7 of SIAM Monographs on Discrete Mathematics and Applications. (2001)
Kirousis, L., Kolaitis, P.: The complexity of minimal satisfiability problems. In: Proceedings of the 18th Symposium on Theoretical Aspects of Computer Science (STACS 2001). Volume 2010 of Lecture Notes in Computer Science., Springer (2001) 407–418
Krokhin, A., Jeavons, P., Jonsson, P.: The complexity of constraints on intervals and lengths. Technical Report TR01-077, Electronic Colloquim on Computational Complexity (2001) (http://www.eccc.uni-trier.de/eccc).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Krokhin, A., Jeavons, P., Jonsson, P. (2002). The Complexity of Constraints on Intervals and Lengths. In: Alt, H., Ferreira, A. (eds) STACS 2002. STACS 2002. Lecture Notes in Computer Science, vol 2285. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45841-7_36
Download citation
DOI: https://doi.org/10.1007/3-540-45841-7_36
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43283-8
Online ISBN: 978-3-540-45841-8
eBook Packages: Springer Book Archive