On the Tractability of Restricted Disjunctive Temporal Problems

In this paper, we provide a polynomial-time deterministic algorithm, and an even simpler randomized algorithm, for solving a restricted (but very expressive) class of disjunctive temporal problems (DTPs). The general form of a DTP is as follows. We are given a set of events X = (X0 is the "beginning of the world" node and is set to 0 by convention), and a set of constraints C. A constraint ci in C is a disjunction of the form s(i, 1) or s(i, 2) ... s(i, Ti). Here, s(i, j) (1 ⇐ j ⇐ Ti) is a simple temporal constraint of the form L(i, j) ⇐ X{b(i, j)} – X{a(i, j)} ⇐ U(i, j) for 0 ⇐ a(i, j), b(i, j) ⇐ N. We will first provide a pseudo-polynomial-time randomized algorithm for solving the following restricted class of DTPs (which we will refer to as RDTPs (restricted DTPs)): Any ci in C is of one of the following types: (Type 1) (L ⇐ Xb – Xa ⇐ U), (Type 2) (L1 ⇐ Xa ⇐ U1) or (L2 ⇐ Xa ⇐ U2) ... (L{Ti} ⇐ Xa ⇐ U{Ti}), (Type 3) (L1 ⇐ Xa ⇐ U1) or (L2 ⇐ Xb ⇐ U2). We will then provide a strongly polynomial-time deterministic algorithm for solving the same problem, and extend the ideas further to provide an even simpler randomized algorithm---the expected running time of which is much less than that of the deterministic algorithm. Our polynomial-time algorithms for solving RDTPs bear important implications on not only being able to handle limited (but very useful) forms of disjunctions in metric temporal reasoning (that would otherwise require an exponential search space), but also in pruning large parts of the search spaces associated with general DTPs.