Abstract
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}\).
This work was supported by a Grant-in-Aid for JSPS Research Fellow (18F18117 to R. D. Barish), and by JSPS Kakenhi grants \(\{\)20K21827, 20H05967, 21H04871, 21H05052 23H03345, 23K18501\(\}\) to T. Shibuya.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Ananth, P., Nasre, M., Sarpatwar, K.K.: Rainbow connectivity: hardness and tractability. In: Proceedings of the 31st FSTTCS, pp. 241–251 (2011)
Andrews, E., Lumduanhom, C., Laforge, E., Zhang, P.: On proper-path colorings in graphs. J. Comb. Math. Comb. Comput. 97, 189–207 (2016)
Arnborg, S., Lagergren, J., Seese, D.: Easy problems for tree-decomposable graphs. J. Algorithms 12(2), 308–340 (1991)
Barrett, C., et al.: Predecessor existence problems for finite discrete dynamical systems. Theoret. Comput. Sci. 386(1–2), 3–37 (2007)
Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications, 1st edn. Macmillan Press, New York (1976)
Borozan, V., et al.: Proper connection of graphs. Discrete Math. 312(17), 2550–2560 (2012)
Chakraborty, S., Fischer, E., Matsliah, A., Yuster, R.: Hardness and algorithms for rainbow connection. J. Comb. Optim. 21(3), 330–347 (2011)
Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: Rainbow connection in graphs. Math. Bohem. 133(1), 85–98 (2008)
Chartrand, G., Johns, G.L., McKeon, K.A., Zhang, P.: The rainbow connectivity of a graph. Networks 54(2), 75–81 (2009)
Courcelle, B.: The monadic second-order logic of graphs. I. Recognizable sets of finite graphs. Inform. Comput. 85(1), 12–75 (1990)
Courcelle, B.: The monadic second-order logic of graphs XII: planar graphs and planar maps. Theoret. Comput. Sci. 237(1–2), 1–32 (2000)
Courcelle, B.: Graph structure and monadic second-order logic: language theoretical aspects. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5125, pp. 1–13. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-70575-8_1
Courcelle, B., Makowsky, J.A., Rotics, U.: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic. Discrete Appl. Math. 108(1–2), 23–52 (2001)
Diestel, R.: Graph Theory, 5th edn. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53622-3
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity, 1st edn. Springer, New York (2013). https://doi.org/10.1007/978-1-4471-5559-1
Ducoffe, G., Marinescu-Ghemeci, R., Popa, A.: On the (di)graphs with (directed) proper connection number two. Discrete Appl. Math. 281, 203–215 (2020)
Dyer, M., Goldberg, L.A., Greenhill, C., Jerrum, M.: The relative complexity of approximate counting problems. Algorithmica 38(3), 471–500 (2004)
Eiben, E., Ganian, R., Lauri, J.: On the complexity of rainbow coloring problems. Discrete Appl. Math. 246, 38–48 (2018)
Karp, R.M., Luby, M.: Monte-Carlo algorithms for enumeration and reliability problems. In: Proceedings of the 24th FOCS, pp. 56–64 (1983)
Li, X., Magnant, C.: Properly colored notions of connectivity – a dynamic survey. Theory Appl. Graphs (1), 1–16 (2015)
Reed, M.G., Syverson, P.F., Goldschlag, D.M.: Anonymous connections and onion routing. IEEE J. Sel. Area. Commun. 16(4), 482–494 (1998)
Zuckerman, D.: On unapproximable versions of NP-complete problems. SIAM J. Comput. 25(6), 1293–1304 (1996)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd.
About this paper
Cite this paper
Barish, R.D., Shibuya, T. (2024). Counting on Rainbow k-Connections. In: Chen, X., Li, B. (eds) Theory and Applications of Models of Computation. TAMC 2024. Lecture Notes in Computer Science, vol 14637. Springer, Singapore. https://doi.org/10.1007/978-981-97-2340-9_23
Download citation
DOI: https://doi.org/10.1007/978-981-97-2340-9_23
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-97-2339-3
Online ISBN: 978-981-97-2340-9
eBook Packages: Computer ScienceComputer Science (R0)