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) twovariable lineardifference simple constraint; (t_2) singlevariable disjunction of many interval constraints; (t_3) twovariable disjunction of two interval constraints only. Kumar showed that RDTPs are solvable in deterministic strongly polynomial time by reducing them to the Connected RowConvex (CRC) constraints satisfaction problem, also devising a faster randomized algorithm. Instead, the most general form of DTPs allows for multivariable disjunctions of many interval constraints and it is NPcomplete.
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 SingleSource Shortest Paths (SSSP) and the 2SAT 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_3constraint. 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_2constraints and either only multitail or only multihead hyperarcconstraints lies in NP cap coNP and admits deterministic pseudopolynomial time algorithms; on the other hand, problems having only t_3constraints and either only multitail or only multihead hyperarcconstraints turns out strongly NPcomplete.
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:110:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770897},
ISSN = {18688969},
year = {2018},
volume = {120},
editor = {Natasha Alechina and Kjetil N{\o}rv{\aa}g and Wojciech Penczek},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/9775},
URN = {urn:nbn:de:0030drops97751},
doi = {10.4230/LIPIcs.TIME.2018.10},
annote = {Keywords: Restricted Disjuctive Temporal Problems, Simple Temporal Networks, Hyper Temporal Networks, Consistency Checking, SingleSource ShortestPaths, 2SAT}
}
08.10.2018
Keywords: 

Restricted Disjuctive Temporal Problems, Simple Temporal Networks, Hyper Temporal Networks, Consistency Checking, SingleSource ShortestPaths, 2SAT 
Seminar: 

25th International Symposium on Temporal Representation and Reasoning (TIME 2018)

Issue date: 

2018 
Date of publication: 

08.10.2018 