We now show how the instance of IP that was presented in figures 5.2, 5.4 and 5.6 is reduced to an instance of SGP.
We have already noted that not every point of the time range is a start- or an endpoint for some interval. The graph comprises only 15 timepoints / vertices. By carefully looking at figure 5.2 we can see that there are three intervals starting at timepoint 0, two at point 2, etc. which gives the respective vertex weights . By definition, there are only edges with relevant lengths between adjacent vertices. We therefore have to look at adjacent timepoints and count the number of intervals that include these points: there are three intervals including points 0 and 2, five intervals including points 2 and 3, etc. which gives the respective edge lengths . Figure 5.9 shows the resulting graph.