Affine optimal k-proper connected edge colorings

Abstract 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 EG E G, such a coloring corresponds to a decomposition of EG E G into color classes C₁, C₂, , Cₙ C 1, C 2, …, C n, with associated weights w₁, w₂, , wₙ w 1, w 2, …, w n, minimizing a specified affine function {A}\,: =\, ₈=₁^n (wᵢ |Cᵢ|) A: = ∑ i = 1 n w i · | C i |, 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 {₀}ᵏ (G) ζ A k (G) as the minimum possible value of {A} A under a k -proper connectivity requirement. For any fixed number of color classes, we show that computing {₀}ᵏ (G) ζ A k (G) is treewidth fixed parameter tractable. However, we also show that determining {₀^ }ᵏ (G) ζ A ′ k (G) with the affine function {A}^ \,: =\, 0 |C₁| + |C₂| A ′: = 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 k 3 ∀ k ≥ 3. We also show that no fully polynomial-time randomized approximation scheme can exist for approximating {₀^ }ᵏ (G) ζ A ′ k (G) under any of the aforementioned constraints unless NP=RP N P = R P.