## 3 NP-Completeness
For each \(p_{i}=(r_{h_{i}}^{i},l_{k_{i}}^{i})\in P\), \(h_{i}<k_{i}\), the number of crossed \(\Delta\)-_blocks_ (i.e., those blocks that are completely contained in \(p_{i}\)) is \(blocks(i)=2(k_{i}-h_{i})-1\). Let \(B=\sum_{i=1}^{3\beta}\frac{blocks(i)}{2}+\frac{\beta}{2}\) and \(K=\Delta B+\Delta-1\). We complete the proof by showing that a solution using at most \(K\) OADMs exists for \(I\) if and only if it is possible to partition the edge set of \(G^{\prime}\) into triangles. We first show that, if it is possible to partition the edge set of \(G^{\prime}\) into triangles, then a solution using at most \(K\) OADMs exists for \(I\). For every triangle in \(G^{\prime}\) composed of edges \(e_{i^{\prime}}^{\prime}\), \(e_{j^{\prime}}^{\prime}\), \(e_{k^{\prime}}^{\prime}\), we consider the set of paths \(\{p_{i},p_{j},p_{k}\}\). Assign these paths the same color and without loss of generality, assume that \(p_{k}\) is the longest path among the three. Since \(g=2\), it can be easily checked that such a set is 1-colorable. Moreover, the number of OADMs used at \(\Delta\)-_blocks_ is \(\Delta\cdot blocks(k)=\frac{\beta}{2}(blocks(i)+blocks(j)+blocks(k)+1)\). By summing over the sets induced by all the triangles, we obtain that the total number of OADMs used at \(\Delta\)-_blocks_ is \(\frac{\Delta}{2}\sum_{i=1}^{3\beta}blocks(i)+\beta=\Delta\cdot B\); thus, we have a \(B\)-solution that can use at most \(K\) OADMs. Conversely, we now show that, if there exists a solution for \(I\) using at most \(K\) OADMs, then it is possible to partition the edge set of \(G^{\prime}\) into triangles. Define a _component_ as a set of paths colored with the same color. We now show that \(S\) is a \(B\)-solution and that in a \(B\)-solution, every component is of the form \(\{(r_{i}^{\gamma_{1}},l_{j}^{\gamma_{1}}),(r_{i}^{\gamma_{2}},l_{k}^{\gamma_{2 }}),(r_{i}^{\gamma_{3}},l_{k}^{\gamma_{3}})\}\) with \(i<j<k\). Let us assume without loss of generality that \(S\) is using the maximum possible number of colors, that is, no set of paths colored with the same color exists, such that it can be split in two sets using two different colors without increasing the number of used OADMs. Since \(g=2\), each component is composed of at most two levels of requests, i.e., two sets of paths where in each set the paths are pairwise disjoint, and every OADM can be used by at most two requests. For each component \(C\) using \(s\)\(\Delta\)-blocks of OADMs, we want to distribute \(s\) among the requests belonging to \(C\) such that each request \(\gamma\in C\) is charged with \(\frac{blocks(\gamma)}{2}+f(C)\), with \(f(C)=\frac{s-\sum_{j^{\prime}\in C}\frac{blocks(\gamma^{\prime})}{2}}{|C|}\) being the _surplus_ of component \(C\). First of all, notice that a component \(C\) of the desired form \(\{(r_{i}^{\gamma_{1}},l_{j}^{\gamma_{1}}),(r_{i}^{\gamma_{2}},l_{k}^{\gamma_{ 2}}),(r_{i}^{\gamma_{3}},l_{k}^{\gamma_{3}})\}\) with \(i<j<k\), uses \(\frac{blocks(\gamma_{1})+blocks(\gamma_{2})+blocks(\gamma_{3})+1}{2}\)\(\Delta\)-_blocks_, and thus \(f(C)=\frac{1}{6}\). The proof now proceeds by cases, considering all the possible components \(C\) not being of the desired form, and for any of them, we show that \(f(C)>\frac{1}{6}\). * Let us assume that three requests belong to a component, \(\gamma_{1}\) on the first level and \(\gamma_{2}\) and \(\gamma_{3}\) on the second one. If the ones on the second level do not correspond to consecutive edges in \(G\), or \(\gamma_{1}\) corresponds to an edge of \(G\) that is not consecutive to both edges corresponding to the requests on the second level, \(C\) uses at least \(\frac{blocks(\gamma_{1})}{2}+\frac{blocks(\gamma_{2})}{2}+\frac{blocks(\gamma_ {2})}{2}+\frac{3}{2}\)\(\Delta\)-_blocks_. Therefore, \(f(C)\geq\frac{1}{2}\). * If a component uses only one level of requests (for our assumption about the maximality of colors, in this case it can contain only a request \(\gamma\)), it is using \(blocks(\gamma)\geq 1\)\(\Delta\)-_blocks_. Therefore, \(f(C)\geq\frac{1}{2}\).