Professor Andrei Krokhin andrei.krokhin@durham.ac.uk
Professor
Constraint satisfaction problems on intervals and lengths
Krokhin, A.; Jeavons, P.; Jonsson, P.
Authors
P. Jeavons
P. Jonsson
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. Many well-known problems such as INTERVAL GRAPH RECOGNITION and INTERVAL SATISFIABILITY can be considered as examples of such CSPs. 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, by giving a complete description of the tractable cases and showing that all remaining cases are NP-complete. 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 well-known tractable and sufficiently expressive form of constraints. The class of problems we consider contains, in particular, problems that are very closely related to the previously studied UNIT INTERVAL GRAPH SANDWICH problem. We completely characterize sets of qualitative relations for which the CSP augmented with arbitrary length constraints of the above form is tractable. We also show that, again, all the remaining cases are NP-complete.
Citation
Krokhin, A., Jeavons, P., & Jonsson, P. (2004). Constraint satisfaction problems on intervals and lengths. SIAM Journal on Discrete Mathematics, 17(3), 453-477. https://doi.org/10.1137/s0895480102410201
Journal Article Type | Article |
---|---|
Publication Date | Jan 1, 2004 |
Deposit Date | Mar 29, 2010 |
Publicly Available Date | Mar 28, 2024 |
Journal | SIAM Journal on Discrete Mathematics |
Print ISSN | 0895-4801 |
Electronic ISSN | 1095-7146 |
Publisher | Society for Industrial and Applied Mathematics |
Peer Reviewed | Peer Reviewed |
Volume | 17 |
Issue | 3 |
Pages | 453-477 |
DOI | https://doi.org/10.1137/s0895480102410201 |
Keywords | Allen's interval algebra, Interval satisfiability, Computational complexity, Tractable cases, Dichotomy theorem, |
Files
Published Journal Article
(292 Kb)
PDF
Copyright Statement
© 2004 Society for Industrial and Applied Mathematics
You might also like
Topology and adjunction in promise constraint satisfaction
(2023)
Journal Article
Algebraic Approach to Promise Constraint Satisfaction
(2021)
Journal Article
Robust algorithms with polynomial loss for near-unanimity CSPs
(2019)
Journal Article
Algebraic approach to promise constraint satisfaction
(2019)
Conference Proceeding
Towards a characterization of constant-factor approximable Finite-Valued CSPs
(2018)
Journal Article
Downloadable Citations
About Durham Research Online (DRO)
Administrator e-mail: dro.admin@durham.ac.uk
This application uses the following open-source libraries:
SheetJS Community Edition
Apache License Version 2.0 (http://www.apache.org/licenses/)
PDF.js
Apache License Version 2.0 (http://www.apache.org/licenses/)
Font Awesome
SIL OFL 1.1 (http://scripts.sil.org/OFL)
MIT License (http://opensource.org/licenses/mit-license.html)
CC BY 3.0 ( http://creativecommons.org/licenses/by/3.0/)
Powered by Worktribe © 2024
Advanced Search