We consider the problem of packing edge-disjoint cycles in digraphs. It is shown that for
, any digraph with minimum degree
contains at least
edge-disjoint directed cycles of size
. In each of these two cases, examples are given to show that
edge-disjoint directed cycles is the best we can achieve. These results are applied to obtain approximation algorithms for
-node-connectivity problems.
References
[1]
Balister, P. (2003) Packing Digraphs with Directed Closed Trails. Combinatorics,ProbabilityandComputing, 12, 1-15. https://doi.org/10.1017/s0963548302005461
Conlon, D., Fox, J. and Sudakov, B. (2014) Cycle Packing. RandomStructures&Algorithms, 45, 608-626. https://doi.org/10.1002/rsa.20574
[4]
Salavatipour, M.R. and Verstra？te, J. (2005) Disjoint Cycles in Directed Graphs. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Vancouver, 23-25 January 2005, 1152-1151.
[5]
Shang, Y. (2010) On the Degree Sequence of Random Geometric Digraphs. Applied Mathematical Sciences, 4, 2001-2012. https://www.m-hikari.com/ams/ams-2010/ams-41-44-2010/index.html
[6]
Alon, N., McDiarmid, K. and Molloy M. (1996) Edge-Disjoint Cycles in Regular Directed Graphs. Journal of Graph Theory, 22, 231-237. https://onlinelibrary.wiley.com/doi/abs/10.1002/(SICI)1097-0118(199607)22:3%3C231::AID-JGT3%3E3.0.CO;2-N?utm_source=gemini
[7]
Gupta, A. and K？nemann, J. (2011) Approximation Algorithms for Network Design: A Survey. SurveysinOperationsResearchandManagementScience, 16, 3-20. https://doi.org/10.1016/j.sorms.2010.06.001
[8]
Khuller, S. and Raghavachari, B. (1996) Improved Approximation Algorithms for Uniform Connectivity Problems. JournalofAlgorithms, 21, 434-450. https://doi.org/10.1006/jagm.1996.0052
[9]
Kortsarz, G. and Nutov, Z. (2003) Approximating Node Connectivity Problems via Set Covers. Algorithmica, 37, 75-92. https://doi.org/10.1007/s00453-003-1027-4
[10]
Frank, A. and Tardos, é. (1989) An Application of Submodular Flows. LinearAlgebraanditsApplications, 114, 329-348. https://doi.org/10.1016/0024-3795(89)90469-2
[11]
Shang, Y. (2019) Super Connectivity of Erd？s-Rényi Graphs. Mathematics, 7, Article 267. https://doi.org/10.3390/math7030267
[12]
Shang, Y. (2023) On Connectivity and Robustness of Random Graphs with Inhomogeneity. Journal of Applied Probability, 60, 284-294. https://www.cambridge.org/core/journals/journal-of-applied-probability/article/abs/on-connectivity-and-robustness-of-random-graphs-with-inhomogeneity/63E67543B2CC627844B0E62DBD5599BA?utm_source=gemini
