Shiftable Intervals

Let a set of fixed length intervals and a set of n (larger) windows, in one-to-one correspondence with the intervals, be given, and assume that each interval can be assigned any position with in its corresponding window. Once the position of each interval has been fixed the intersection graph of such set of intervals is an interval graph. By varying the position of each interval in all possible ways, we get a family of interval graphs. We shall define some optimization problems related to the clique, stability, chromatic, and clique cover numbers of the interval graphs in the family, mainly focussing on complexity aspects, bounds and solution algorithms. Some problems are proved to be NP-hard, others are solved in polynomial time on some particular classes of instances, which are characterized. Many practical applications can be reduced to these kind of problems, which seems to be an interesting modeling framework.