## 3 NP-Completeness  
We note that Theorem 1 of [25] implies that the problem is APX-hard for \(\alpha=1\). Furthermore, in this section, we prove that the decision version of CombinedTraffic-Grooming is NP-complete even on a chain network with \(g=2\) and for every \(\alpha>0\). Moreover, for \(\alpha=0\), i.e., for the case of ADM minimization, the problem is already known to be NP-complete (see [31]). In the following theorem, we consider the case of \(\alpha>0\). Theorem 1.1: _Given an instance \((G,P,2,\alpha)\) of CombinedTrafficGrooming for chain topology and a real number \(x\), the problem of deciding whether there exists a solution with a cost of at most \(x\) is NP-complete for every \(\alpha>0\)._  
TriPart  
**Input:** An undirected graph \(G^{\prime}=(V^{\prime},E^{\prime})\) with \(V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{\sigma}\}\) and \(E^{\prime}\)  
\(=\{e^{\prime}_{1},e^{\prime}_{2},\ldots,e^{\prime}_{3\beta}\}\)  
**Output:** \"YES\" if there exists a partition of \(E(G)\) into triangles, \"NO\" otherwise. The TriPart problem is the problem of deciding whether for a given simple graph \(G\), there exists a partition of its edge set into triangles. Let \(V^{\prime}=\{v^{\prime}_{1},v^{\prime}_{2},\ldots,v^{\prime}_{\sigma}\}\) and \(E^{\prime}=\{e^{\prime}_{1},e^{\prime}_{2},\ldots,e^{\prime}_{3\beta}\}\) be the vertex and edge sets of \(G^{\prime}\). Note that we can assume that the number of edges of \(G^{\prime}\) is a multiple of \(3\), because otherwise a partition does not exist and the answer is trivially \"NO\". From the above instance \(G^{\prime}=(V^{\prime},E^{\prime})\) of TriPart, we build the following instance \(I=(G=(V,E),P,2,\alpha)\) of CombinedTrafficGrooming. For each \(v^{\prime}_{i}\in V^{\prime}\), we add \(6\beta+2\Delta\) nodes to chain \(G\), with \(\Delta=36\beta^{2}\sigma+1\). More precisely, we consider a subchain of nodes \(C_{i}=\{l^{1}_{i},\ldots,l^{3\beta}_{i},a^{1}_{i},\ldots,a^{\Delta}_{i},r^{1}_ {i},\ldots,r^{3\beta}_{i},b^{1}_{i},\ldots,b^{\Delta}_{i}\}\) (see Figure 2); it is worth emphasizing that \(\Delta\) is chosen to be sufficiently big to force optimal solutions to prefer triangular sets over others, as it will be proven in the sequel. The chain \(G\) of our instance is obtained by concatenating all the subchains \(C_{i}\), \(1\leq i\leq\sigma\) (see Figure 3). Finally, we have to define the path set \(P\). Let \((u,v)\in V\times V\) denote the path between \(u\) and \(v\) in \(G\). For each \(e^{\prime}_{i}=\{v^{\prime}_{h_{i}},v^{\prime}_{k_{i}}\}\in E^{\prime}\) with \(h_{i}<k_{i}\), we add the path \(p_{i}=(r^{i}_{h_{i}},r^{i}_{k_{i}})\) to \(P\). Since each node of \(G\) is an endpoint of at most one request in \(P\), it holds that each solution uses exactly \(6\beta\) ADMs. Therefore, in the following, we focus only on the minimization of OADMs. In fact, let \(x=\alpha\times K+(1-\alpha)\times 6\beta\) (the value of \(K\) will be chosen later). It can be noticed that there exists a solution of cost at most \(x\) if and only if there is a solution which uses a number of OADMs at most \(K\). Define a \(t\)-solution (where \(t\) is an integer value) as a solution using \(\Delta\times t\) OADMs located at blocks of \(\Delta\) nodes, (i.e., the \(a\) and \(b\) nodes), in the following called \(\Delta\)_-blocks_. Recall that \(\Delta=36\beta^{2}\sigma+1\): notice that (i) it is polynomial in the size of the instance and (ii) it is sufficiently high so that the cost of a solution is mainly determined by the number of OADMs located at \(\Delta\)-blocks, that is, every \(t\)-solution uses a total number of OADMs lower  
Figure 3: The chain \(G\) with three paths corresponding to the edges of the triangle \(v^{\prime}_{1},v^{\prime}_{2},v^{\prime}_{4}\) in the graph \(G^{\prime}\) being the instance of TriPart in Theorem 1.  
than the one used by any \((t+1)\)-solution. We can conclude that a \(t\)-solution uses a total number of OADMs between \(\Delta\times t\) and \(\Delta\times t+\Delta-1\).