The instances of the interval partitioning problem can be reduced to instances of a similar graph-theoretic problem, namely the problem of sequential graph partitioning (SGP) . SGP was tackled at the beginning of the 1970s when people where looking for optimal code segmentations and paginations. A polynomial-time algorithm that computes optimal solutions for SGP was presented in [Kernighan, 1971]. For the purpose of interval partitioning we have to use a minor variation of SGP which does not change its complexity.
Being able to map instances of IP to instances of graph partitioning (GP) has another advantage: GP and its variations are well investigated and there is a variety of algorithmic and complexity results available. GP has proven to be very sensitive, even to minor changes in the problem constraints. Arbitrary GP, for example, is NP-complete [Hyafil and Rivest, 1973] whereas SGP is polynomial. Variations of IP probably behave similarly. Reducing them to a GP problem will enable us to benefit from a huge collection of algorithms and complexity results that have already been obtained.
The remainder of this section is structured like this: Section 5.6.1 introduces SGP in the form in which it is required for solving IP. Then, in section 5.6.2, we show how instances of IP can be reduced to instances of SGP. This step is essential as it opens the way towards finding optimal solutions for IP. Section 5.6.3 gives an example by reducing the example of figures 5.2, 5.4 and 5.6 to an instance of SGP. Section 5.6.4 formally proves that the reduction that we derived is correct. In section 5.6.5 the algorithm SGP-opt is presented which computes optimal partitions for instances of SGP. Section 5.6.6 gives an example that shows how SGP-opt works. Finally, we derive the runtime complexity of SGP-opt in section 5.6.7.