Sparse highly connected spanning subgraphs in dense directed graphs
share
Mader (1985) proved that every strongly k-connected n-vertex digraph contains a strongly k-connected spanning subgraph with at most 2kn - 2k^2 edges, and this is sharp. For dense strongly k-connected digraphs, the bound can be significantly improved for dense strongly k-connected digraphs. Let Δ(D) be the maximum degree of the complement of the underlying undirected graph of a digraph D. 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. The additional term 800k(k+Δ(D)) is sharp up to a multiplicative constant. In particular, it follows that every strongly k-connected n-vertex semicomplete digraph contains a strongly k-connected spanning subgraph with at most kn + 800k^2 edges, improving the recent result of Kang, Kim, Kim, and Suh (2017) for tournaments and establishing the tight bound, as 800k^2 cannot be improved to the number less than k(k-1)/2. We also prove an analogous result for strongly k-arc-connected directed multigraphs, which generalises the earlier result of Bang-Jensen, Huang, and Yeo (2004) for strongly connected digraphs. The proofs yield polynomial-time algorithms.
READ FULL TEXT