License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.TIME.2018.10
URN: urn:nbn:de:0030-drops-97751
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9775/
Comin, Carlo ;
Rizzi, Romeo
On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier
Abstract
In 2005 T.K.S. Kumar studied the Restricted Disjunctive Temporal Problem (RDTP), a restricted but very expressive class of Disjunctive Temporal Problems (DTPs). An RDTP comes with a finite set of temporal variables, and a finite set of temporal constraints each of which can be either one of the following three types: (t_1) two-variable linear-difference simple constraint; (t_2) single-variable disjunction of many interval constraints; (t_3) two-variable disjunction of two interval constraints only. Kumar showed that RDTPs are solvable in deterministic strongly polynomial time by reducing them to the Connected Row-Convex (CRC) constraints satisfaction problem, also devising a faster randomized algorithm. Instead, the most general form of DTPs allows for multi-variable disjunctions of many interval constraints and it is NP-complete.
This work offers a deeper comprehension on the tractability of RDTPs, leading to an elementary deterministic strongly polynomial time algorithm for them, significantly improving the asymptotic running times of all the previous deterministic and randomized solutions. The result is obtained by reducing RDTPs to the Single-Source Shortest Paths (SSSP) and the 2-SAT problem (jointly), instead of reducing to CRCs. In passing, we obtain a faster (quadratic time) algorithm for RDTPs having only {t_1, t_2}-constraints and no t_3-constraint. As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a disjunctive strict generalization of Simple Temporal Networks (STNs) based on hypergraphs: we prove that solving temporal problems having only t_2-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in NP cap co-NP and admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only t_3-constraints and either only multi-tail or only multi-head hyperarc-constraints turns out strongly NP-complete.
BibTeX - Entry
@InProceedings{comin_et_al:LIPIcs:2018:9775,
author = {Carlo Comin and Romeo Rizzi},
title = {{On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier}},
booktitle = {25th International Symposium on Temporal Representation and Reasoning (TIME 2018)},
pages = {10:1--10:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-089-7},
ISSN = {1868-8969},
year = {2018},
volume = {120},
editor = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9775},
URN = {urn:nbn:de:0030-drops-97751},
doi = {10.4230/LIPIcs.TIME.2018.10},
annote = {Keywords: Restricted Disjuctive Temporal Problems, Simple Temporal Networks, Hyper Temporal Networks, Consistency Checking, Single-Source Shortest-Paths, 2-SAT}
}
|
Keywords: |
|
Restricted Disjuctive Temporal Problems, Simple Temporal Networks, Hyper Temporal Networks, Consistency Checking, Single-Source Shortest-Paths, 2-SAT |
|
Collection: |
|
25th International Symposium on Temporal Representation and Reasoning (TIME 2018) |
|
Issue Date: |
|
2018 |
|
Date of publication: |
|
08.10.2018 |
