Skip to main content

Research Repository

Advanced Search

Disjunctive Temporal Problems under Structural Restrictions

Dabrowski, Konrad K.; Jonsson, Peter; Ordyniak, Sebastian; Osipov, George

Disjunctive Temporal Problems under Structural Restrictions Thumbnail


Authors

Konrad K. Dabrowski

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

Conference Name 35th AAAI Conference on Artificial Intelligence (AAAI)
Conference Location Vancouver, Canada
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
Publisher URL https://aaai.org/papers/03724-disjunctive-temporal-problems-under-structural-restrictions/

Files





You might also like



Downloadable Citations