Sparse highly connected spanning subgraphs in dense directed graphs

Dong Yeap Kang

Published 2018-01-05Version 1

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 $\overline{\Delta}(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+\overline{\Delta}(D))$ edges. The additional term $800k(k+\overline{\Delta}(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.