Counting on Rainbow k-Connections

For an undirected graph imbued with an edge coloring, a rainbow path (resp. proper path) between a pair of vertices corresponds to a simple path in which no two edges (resp. no two adjacent edges) are of the same color. In this context, we refer to such an edge coloring as a rainbow k-connected w-coloring (resp. k-proper connected w-coloring) if at most w colors are used to ensure the existence of at least k internally vertex disjoint rainbow paths (resp. k internally vertex disjoint proper paths) between all pairs of vertices. At present, while there have been extensive efforts to characterize the complexity of finding rainbow 1-connected colorings, we remark that very little appears to known for cases where $$k \in \mathbb {N}_{>1}$$ . In this work, in part answering a question of (Ducoffe et al.; Discrete Appl. Math. 281; 2020), we first show that the problems of counting rainbow k-connected w-colorings and counting k-proper connected w-colorings are both linear time treewidth Fixed Parameter Tractable (FPT) for every $$\left( k,w\right) \in \mathbb {N}_{>0}^2$$ . Subsequently, and in the other direction, we extend prior NP-completeness results for deciding the existence of a rainbow 1-connected w-coloring for every $$w \in \mathbb {N}_{>1}$$ , in particular, showing that the problem remains NP-complete for every $$\left( k,w\right) \in \mathbb {N}_{>0} \times \mathbb {N}_{>1}$$ . This yields as a corollary that no Fully Polynomial-time Randomized Approximation Scheme (FPRAS) can exist for approximately counting such colorings in any of these cases (unless $$NP = RP$$ ). Next, concerning counting hardness, we give the first $$\#P$$ -completeness result we are aware of for rainbow connected colorings, proving that counting rainbow k-connected 2-colorings is $$\#P$$ -complete for every $$k \in \mathbb {N}_{>0}$$ .