On Restricted Disjunctive Temporal Problems: Faster Algorithms and Tractability Frontier.

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 \mathcal{T}=\{X,Y,\ldots\} of time-point variables, and a finite set \mathcal{C} of temporal constraints where each of them can be either one of the following three types: (\texttt{t}_1) (Y-X\leq w), for w real (a simple temporal difference-constraint);
(\texttt{t}_2) (l_1\leq X\leq u_1)\vee \cdots \vee (l_k\leq X\leq u_k), for l_i,u_i reals (a single-variable disjunction of many interval-constraints);
(\texttt{t}_3) (l_1\leq X\leq u_1) \vee (l_2\leq Y\leq u_2), for l_i,u_i reals (a 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 problem; plus, he devised a randomized algorithm whose expected running time is less than that of the deterministic one. 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 solving them,
significantly improving the asymptotic running times of all the previous deterministic and randomized algorithms. 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 \texttt{t}_1 and \texttt{t}_2-constraints (and no \texttt{t}_3-constraint).
As a second main contribution, we study the tractability frontier of solving RDTPs blended with Hyper Temporal Networks (HyTNs), a strict generalization of Simple Temporal Networks (STNs) grounded on hypergraphs: we prove that solving temporal problems having only \texttt{t}_2-constraints and either only multi-tail or only multi-head hyperarc-constraints lies in \text{NP}\cap \text{co-NP} and it admits deterministic pseudo-polynomial time algorithms; on the other hand, problems having only \texttt{t}_3-constraints and either only multi-tail or only multi-head hyperarc-constraints are strongly NP-complete.

Download: manuscript.



Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s