Hostname: page-component-74656f9884-npj9w Total loading time: 0 Render date: 2026-11-07T10:57:21.501Z Has data issue: false hasContentIssue false
  • English
  • Français

Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs

Part of: Graph theory

Published online by Cambridge University Press:  05 November 2018

DONG YEAP KANG
DONG YEAP KANG*
Affiliation:
Department of Mathematical Sciences, KAIST, 291 Daehak-ro Yuseong-gu Daejeon, 34141South Korea (e-mail: dyk90@kaist.ac.kr)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Mader proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k2 edges, where equality holds for the complete bipartite digraph DKk,n-k. For dense strongly k-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly k-connected n-vertex digraph D contains a strongly k-connected spanning subgraph with at most kn + 800k(k + Δ(D)) edges, where Δ(D) denotes the maximum degree of the complement of the underlying undirected graph of a digraph D. Here, the additional term 800k(k + Δ(D)) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k2 edges, which is essentially optimal since 800k2 cannot be reduced to the number less than k(k - 1)/2.

We also prove an analogous result for strongly k-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.

MSC classification

Primary: 05C20: Directed graphs (digraphs), tournaments
Secondary: 05C40: Connectivity

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 3 , May 2019 , pp. 423 - 464
Copyright
Copyright © Cambridge University Press 2018 

Footnotes

†

Supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (no. NRF-2017R1A2B4005020) and also by a TJ Park Science Fellowship of POSCO TJ Park Foundation.

References

[1] Bang-Jensen, J. (2009) Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs. Discrete Math. 309 5655–5667.Google Scholar
[2] Bang-Jensen, J. and Gutin, G. (2009) Digraphs: Theory, Algorithms and Applications, second edition, Springer Monographs in Mathematics, Springer.Google Scholar
[3] Bang-Jensen, J. and Havet, F. (2018) Tournaments and Semicomplete Digraphs, Springer, pp. 35–124.Google Scholar
[4] Bang-Jensen, J., Huang, J. and Yeo, A. (2003) Strongly connected spanning subdigraphs with the minimum number of arcs in quasi-transitive digraphs. SIAM J. Discrete Math. 16 335–343.Google Scholar
[5] Bang-Jensen, J., Huang, J. and Yeo, A. (2004) Spanning k-arc-strong subdigraphs with few arcs in k-arc-strong tournaments. J. Graph Theory 46 265–284.Google Scholar
[6] Bang-Jensen, J. and Yeo, A. (2001) The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs. J. Algorithms 41 1–19.Google Scholar
[7] Berg, A. R. and Jordán, T. (2005) Minimally k-edge-connected directed graphs of maximal size. Graphs Combin. 21 39–50.Google Scholar
[8] Cheriyan, J. and Thurimella, R. (2000) Approximating minimum-size k-connected spanning subgraphs via matching. SIAM J. Comput. 30 528–560.Google Scholar
[9] Dalmazzo, M. (1977) Nombre d'arcs dans les graphes k-arc-fortement connexes minimaux. CR Acad. Sci. Paris Sér. A–B 285 A341–A344.Google Scholar
[10] Edmonds, J. (1973) Edge-disjoint branchings. In Combinatorial Algorithms (Rustin, B., ed.), Academic Press, pp. 91–96.Google Scholar
[11] Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.Google Scholar
[12] Hopcroft, J. E. and Karp, R. M. (1973) An n 5/2 algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2 225–231.Google Scholar
[13] Kang, D. Y., Kim, J., Kim, Y. and Suh, G. (2017) Sparse spanning k-connected subgraphs in tournaments. SIAM J. Discrete Math. 31 2206–2227.Google Scholar
[14] Kim, J., Kühn, D. and Osthus, D. (2016) Bipartitions of highly connected tournaments. SIAM J. Discrete Math. 30 895–911.Google Scholar
[15] Kühn, D., Lapinskas, J., Osthus, D. and Patel, V. (2014) Proof of a conjecture of Thomassen on Hamilton cycles in highly connected tournaments. Proc. Lond. Math. Soc. (3) 109 733–762.Google Scholar
[16] Kühn, D., Osthus, D. and Townsend, T. (2016) Proof of a tournament partition conjecture and an application to 1-factors with prescribed cycle lengths. Combinatorica 36 451–469.Google Scholar
[17] Mader, W. (1985) Minimal n-fach zusammenhängende Digraphen. J. Combin. Theory Ser. B 38 102–117.Google Scholar
[18] Mader, W. (1996) On vertices of degree n in minimally n-connected graphs and digraphs. In Combinatorics: Paul Erdős is Eighty, (Miklós, D. et al., eds), Vol. 2, János Bolyai Mathematical Society, pp. 423–449.Google Scholar
[19] Pokrovskiy, A. (2015) Highly linked tournaments. J. Combin. Theory Ser. B 115 339–347.Google Scholar
[20] Pokrovskiy, A. (2017) Edge disjoint Hamiltonian cycles in highly connected tournaments. Int. Math. Res. Not. 2017 429–467.Google Scholar
[21] Thomassen, C. (1982) Edge-disjoint Hamiltonian paths and cycles in tournaments. Proc. London Math. Soc. (3) 45 151–168.Google Scholar
[22] Vetta, A. (2001) Approximating the minimum strongly connected subgraph via a matching lower bound. In Proceedings of the Twelfth Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, pp. 417–426.Google Scholar