zbMATH — the first resource for mathematics

Sparse highly connected spanning subgraphs in dense directed graphs. (English) Zbl 07186350
Summary: Mader proved that every strongly \(k\)-connected \(n\)-vertex digraph contains a strongly \(k\)-connected spanning subgraph with at most \(2 kn - 2k^2\) edges, where equality holds for the complete bipartite digraph \(DK_{ k,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 + \overline{\Delta}(D))\) edges, where \(\overline{\Delta}(D)\) denotes the maximum degree of the complement of the underlying undirected graph of a digraph \(D\). Here, the additional term \(800k(k + \overline{\Delta}(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 + 800k^2\) edges, which is essentially optimal since \(800k^2\) 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.
05C20 Directed graphs (digraphs), tournaments
05C40 Connectivity
Full Text: DOI
[1] Bang-Jensen, J. (2009) Problems and conjectures concerning connectivity, paths, trees and cycles in tournament-like digraphs.Discrete Math.3095655-5667. · Zbl 1207.05067
[2] Bang-Jensen, J. and Gutin, G. (2009) Digraphs: Theory, Algorithms and Applications, second edition, Springer Monographs in Mathematics, Springer. · Zbl 1170.05002
[3] Bang-Jensen, J. and Havet, F. (2018) Tournaments and Semicomplete Digraphs, Springer, pp. 35-124. · Zbl 1407.05102
[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.16335-343. · Zbl 1029.05063
[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 Theory46265-284. · Zbl 1057.05039
[6] Bang-Jensen, J. and Yeo, A. (2001) The minimum spanning strong subdigraph problem for extended semicomplete digraphs and semicomplete bipartite digraphs.J. Algorithms411-19. · Zbl 1002.68110
[7] Berg, A. R. and Jordán, T. (2005) Minimally k-edge-connected directed graphs of maximal size.Graphs Combin.2139-50. · Zbl 1062.05079
[8] Cheriyan, J. and Thurimella, R. (2000) Approximating minimum-size k-connected spanning subgraphs via matching.SIAM J. Comput.30528-560. · Zbl 1049.90104
[9] Dalmazzo, M. (1977) Nombre d’arcs dans les graphes k-arc-fortement connexes minimaux. CR Acad. Sci. Paris Sér. A-B285A341-A344. · Zbl 0367.05037
[10] Edmonds, J. (1973) Edge-disjoint branchings. In Combinatorial Algorithms (Rustin, B., ed.), Academic Press, pp. 91-96.
[11] Garey, M. R. and Johnson, D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. · Zbl 0411.68039
[12] Hopcroft, J. E. and Karp, R. M. (1973) An n^5/2 algorithm for maximum matchings in bipartite graphs.SIAM J. Comput.2225-231. · Zbl 0266.05114
[13] Kang, D. Y., Kim, J., Kim, Y. and Suh, G. (2017) Sparse spanning k-connected subgraphs in tournaments.SIAM J. Discrete Math.312206-2227. · Zbl 1371.05104
[14] Kim, J., Kühn, D. and Osthus, D. (2016) Bipartitions of highly connected tournaments.SIAM J. Discrete Math.30895-911. · Zbl 1336.05050
[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)109733-762. · Zbl 1302.05069
[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.Combinatorica36451-469. · Zbl 1389.05058
[17] Mader, W. (1985) Minimal n-fach zusammenhängende Digraphen.J. Combin. Theory Ser. B38102-117. · Zbl 0578.05045
[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. · Zbl 0849.05048
[19] Pokrovskiy, A. (2015) Highly linked tournaments.J. Combin. Theory Ser. B115339-347. · Zbl 1319.05063
[20] Pokrovskiy, A. (2017) Edge disjoint Hamiltonian cycles in highly connected tournaments.Int. Math. Res. Not.2017429-467. · Zbl 1405.05097
[21] Thomassen, C. (1982) Edge-disjoint Hamiltonian paths and cycles in tournaments. Proc. London Math. Soc.(3)45151-168. · Zbl 0486.05049
[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. · Zbl 0987.05090
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.