Reducing the number of disjuncts in DTPs

The Disjunctive Temporal Problem (DTP) consists of a finite set of time points and a finite set of constraints, each composed of alternative disjuncts modeling delays and deadlines for possibly different pairs of time points. An instance of DTP is consistent if there exists an assignment of real values to the time points such that all constraints are satisfied. Here we focus on DTPs with at most k >= 2 disjuncts per constraint. We define a few polynomial-time encoders to reduce the number of disjuncts to at most k', with 2 <= k' <= k, preserving (in)consistency of the original instance. These results generalize previous work in the literature. Anyway, we provide a methodology not related to any specific technology that sticks to DTP.