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 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\, :=\,∑ ᵢ₌₁ⁿ ( 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 ζ _Aᵏ(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 ζ _Aᵏ(G) ζ A k ( G ) is treewidth fixed parameter tractable. However, we also show that determining ζ _Aᵏ(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 ζ _Aᵏ(G) ζ A ′ k ( G ) under any of the aforementioned constraints unless $$NP=RP$$ N P = R P .