Affine optimal k-proper connected edge colorings

We introduce affine optimal k-proper connected edge colorings as a variation on Fujita’s notion of optimal k-proper connected colorings (Fujita in Optim Lett 14(6):1371–1380, 2020. https://doi.org/10.1007/s11590-019-01442-9) with applications to the frequency assignment problem. Here, for a simple undirected graph G with edge set \(E_G\) $E_G$ , such a coloring corresponds to a decomposition of \(E_G\) $E_G$ into color classes \(C_1, C_2, \ldots , C_n\) $C_1,C_2,\dots ,C_n$ , with associated weights \(w_1, w_2, \ldots , w_n\) $w_1,w_2,\dots ,w_n$ , minimizing a specified affine function \({\mathcal {A}}\, {:=}\,\sum _{i=1}^{n} \left( w_i \cdot |C_i|\right)\) $\mathcal{A}:={\sum }_{i=1}^n\left(w_i,·,|C_i|\right)$ , while also ensuring the existence of k vertex disjoint proper paths (i.e., simple paths with no two adjacent edges in the same color class) between all pairs of vertices. In this context, we define \(\zeta _{{\mathcal {A}}}^k(G)\) ${\zeta }_{\mathcal{A}}^k(G)$ as the minimum possible value of \({\mathcal {A}}\) $\mathcal{A}$ under a k-proper connectivity requirement. For any fixed number of color classes, we show that computing \(\zeta _{{\mathcal {A}}}^k(G)\) ${\zeta }_{\mathcal{A}}^k(G)$ is treewidth fixed parameter tractable. However, we also show that determining \(\zeta _{{\mathcal {A}}^{\prime }}^k(G)\) ${\zeta }_{{\mathcal{A}}^{\prime }}^k(G)$ with the affine function \({\mathcal {A}}^{\prime } \, {:=}\,0 \cdot |C_1| + |C_2|\) ${\mathcal{A}}^{\prime }:=0·|C_1|+|C_2|$ is NP-hard for 2-connected planar graphs in the case where \(k = 1\) $k=1$ , cubic 3-connected planar graphs for \(k = 2\) $k=2$ , and k-connected graphs \(\forall k \ge 3\) $\forall k\ge 3$ . We also show that no fully polynomial-time randomized approximation scheme can exist for approximating \(\zeta _{{\mathcal {A}}^{\prime }}^k(G)\) ${\zeta }_{{\mathcal{A}}^{\prime }}^k(G)$ under any of the aforementioned constraints unless \(NP=RP\) $NP=RP$ .