Sparse Spanning $k$-Connected Subgraphs in Tournaments
Dong Yeap Kang, Jaehoon Kim, Younjin Kim, Geewon Suh · SIAM Journal on Discrete Mathematics · 2017
In 2009, Bang-Jensen asked whether there exists a function $g(k)$ such that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + g(k)$ arcs. In this paper, we answer the question by showing that every strongly $k$-connected $n$-vertex tournament contains a strongly $k$-connected spanning subgraph with at most $kn + 750k^2\log_2(k+1)$ arcs, and there is a polynomial-time algorithm to find the spanning subgraph.