The characterization of IRS with at most 1 interval per arc (linear or cyclic) is polynomial if there is no constraint about the path lengths induced by the routing, see Paragraph 2.4. The problem becomes much harder when, for example, the shortest paths are required. Because the labeling can be optimized over all the possible node- and arc-labeling (including all the possible choice of routing paths), it appears that determining whether or not a graph has a shortest path 1-IRS is difficult in practice. The best-known NP-completeness results are the following:
Thus it is NP-complete for the case of weighted graphs (NP-completeness results are stated for the unweighted case), and shortest path IRS (s = 1). The result concerning the stretch factor was not mentioned in the original paper of [Fla97b]. However, since their construction is a graph of diameter 2, is quite easy to see that G has a shortest path 1-SLIRS (or its variant) if and only if G has a 1-SLIRS of stretch factor s < 3/2.
In [FGS95] it is also mentioned that the problem of determining the minimum K such that a given weighted graph supports a shortest path IRS with a total number of K intervals, for the entire graph, is NP-hard.
In Paragraph 4.1 we will see that the problem becomes polynomial under some assumptions of non uniform link costs (dynamic link-costs).
The general problem of shortest path k-IRS is difficult to solve, however shortest path k-IRS have been found for many large classes of graphs.