Konrad K. Dabrowski
Disjunctive Temporal Problems under Structural Restrictions
Dabrowski, Konrad K.; Jonsson, Peter; Ordyniak, Sebastian; Osipov, George
Authors
Peter Jonsson
Sebastian Ordyniak
George Osipov
Abstract
The disjunctive temporal problem (DTP) is an expressive temporal formalism that extends Dechter et al.’s simple temporal problem. The DTP is well studied in the literature and has many important applications. It is known that deciding satisfiability of DTPs is NP-hard and that, in many cases, single-exponential algorithms (running in O(c n ) time) do not exist under the Exponential-Time Hypothesis. The computational hardness makes it worthwhile to identify restricted problems that are efficiently solvable. One way of doing this is to restrict the interactions of variables and constraints. We show that instances of DTP of any arity with integers bounded by poly(n) can be solved in n f(w) time, where n denotes the problem size, w is the treewidth of the incidence graph and f is a computable function; in other words, this problem is in the complexity class XP and it can be solved in polynomial time whenever w is fixed. We complement this result by showing that binary DTPs that only involve the integers 0 and 1 are not fixed-parameter tractable with respect to treewidth, i.e. they do not admit a f(w) · poly(n) time algorithm for any computable function f, under standard complexity assumptions. For instances with unbounded integers, we show that even binary DTPs parameterized by treewidth cannot be in XP, unless P = NP.
Citation
Dabrowski, K. K., Jonsson, P., Ordyniak, S., & Osipov, G. (2021). Disjunctive Temporal Problems under Structural Restrictions. . https://doi.org/10.1609/aaai.v35i5.16489
Presentation Conference Type | Conference Paper (Published) |
---|---|
Conference Name | 35th AAAI Conference on Artificial Intelligence (AAAI) |
Start Date | Feb 2, 2021 |
End Date | Feb 9, 2021 |
Acceptance Date | Mar 2, 2021 |
Publication Date | 2021 |
Deposit Date | Mar 4, 2021 |
Publicly Available Date | Mar 8, 2021 |
Pages | 3724-3732 |
Series ISSN | 2374-3468 |
DOI | https://doi.org/10.1609/aaai.v35i5.16489 |
Public URL | https://durham-repository.worktribe.com/output/1139774 |
Publisher URL | https://aaai.org/papers/03724-disjunctive-temporal-problems-under-structural-restrictions/ |
Files
Accepted Conference Proceeding
(297 Kb)
PDF
You might also like
Clique‐width: Harnessing the power of atoms
(2023)
Journal Article
Solving Infinite-Domain CSPs Using the Patchwork Property
(2023)
Presentation / Conference Contribution
Fine-Grained Complexity of Temporal Problems
(2020)
Presentation / Conference Contribution
Graph isomorphism for (H1,H2)-free graphs: an almost complete dichotomy
(2020)
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