Finding small k-arc-strong Spanning Subdigraphs in k-arc-strong Tournaments
Jørgen Bang‐Jensen, Jing Huang, Anders Yeo · 2000
Given a k-arc-strong tournament T , we estimate the minimum number of arcs possible in a k-arc-strong spanning subdigraph of T . We give a construction which shows that for each k 2 there are tournaments T on n vertices such that every k-arc-strong spanning subdigraph of T contains at least nk + 1 8 (k + 1) 2 arcs. As our main result we prove that every k-arc-strong tournament contains a spanning k-arc-strong subdigraph with no more than nk+280k 2 arcs. Our proof implies the existence of a polynomial algorithm which finds such a spanning k- strong subdigraph with at most nk+280k 2 arcs. We also discuss the implications of our results on related problems and conjectures. Keywords: tournament, arc-connectivity, minimum strong spanning subdigraph, certificates for connectivity, polynomial algorithm. 1 Introduction A tournament is an orientation of a complete graph. It is well-known and easy to show that every strong tournament has a hamiltonian cycle. Furthermore, it i...