All-Shotest-Path 2-Interval Routing is NP-Complete

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. All of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problems have been proved to be NP-complete for every k � 3, and remain open for k = 1,2. In this paper, we close the open case of k = 2 by showing that it is NP-complete to decide whether a graph admits an all-shortestpath 2-IRS. The same proof is also valid for all-shortest-path Strict 2-IRS. All-shortest-path Strict k-IRS is previously known to be polynomial for k = 1, open for k = 2, 3, and NP-complete for every constant k � 4. Key words: Interval routing schemes; compact routing; NP-completeness.