{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:05:13Z","timestamp":1758823513224},"reference-count":22,"publisher":"Cambridge University Press (CUP)","issue":"3","license":[{"start":{"date-parts":[[2018,11,5]],"date-time":"2018-11-05T00:00:00Z","timestamp":1541376000000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,5]]},"abstract":"<jats:p>Mader proved that every strongly <jats:italic>k<\/jats:italic>-connected <jats:italic>n<\/jats:italic>-vertex digraph contains a strongly <jats:italic>k<\/jats:italic>-connected spanning subgraph with at most 2<jats:italic>kn<\/jats:italic> - 2<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup> edges, where equality holds for the complete bipartite digraph <jats:italic>DK<\/jats:italic><jats:sub><jats:italic>k,n-k<\/jats:italic><\/jats:sub>. For dense strongly <jats:italic>k<\/jats:italic>-connected digraphs, this upper bound can be significantly improved. More precisely, we prove that every strongly <jats:italic>k<\/jats:italic>-connected <jats:italic>n<\/jats:italic>-vertex digraph <jats:italic>D<\/jats:italic> contains a strongly <jats:italic>k<\/jats:italic>-connected spanning subgraph with at most <jats:italic>kn<\/jats:italic> + 800<jats:italic>k<\/jats:italic>(<jats:italic>k<\/jats:italic> + <jats:overline>\u0394<\/jats:overline>(<jats:italic>D<\/jats:italic>)) edges, where <jats:overline>\u0394<\/jats:overline>(<jats:italic>D<\/jats:italic>) denotes the maximum degree of the complement of the underlying undirected graph of a digraph <jats:italic>D<\/jats:italic>. Here, the additional term 800<jats:italic>k<\/jats:italic>(<jats:italic>k<\/jats:italic> + <jats:overline>\u0394<\/jats:overline>(<jats:italic>D<\/jats:italic>)) is tight up to multiplicative and additive constants. As a corollary, this implies that every strongly <jats:italic>k<\/jats:italic>-connected <jats:italic>n<\/jats:italic>-vertex semicomplete digraph contains a strongly <jats:italic>k<\/jats:italic>-connected spanning subgraph with at most <jats:italic>kn<\/jats:italic> + 800<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup> edges, which is essentially optimal since 800<jats:italic>k<\/jats:italic><jats:sup>2<\/jats:sup> cannot be reduced to the number less than <jats:italic>k<\/jats:italic>(<jats:italic>k<\/jats:italic> - 1)\/2.<\/jats:p><jats:p>We also prove an analogous result for strongly <jats:italic>k<\/jats:italic>-arc-connected directed multigraphs. Both proofs yield polynomial-time algorithms.<\/jats:p>","DOI":"10.1017\/s0963548318000469","type":"journal-article","created":{"date-parts":[[2018,11,5]],"date-time":"2018-11-05T12:19:14Z","timestamp":1541420354000},"page":"423-464","source":"Crossref","is-referenced-by-count":1,"title":["Sparse Highly Connected Spanning Subgraphs in Dense Directed Graphs"],"prefix":"10.1017","volume":"28","author":[{"given":"DONG YEAP","family":"KANG","sequence":"first","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,11,5]]},"reference":[{"key":"S0963548318000469_ref9","first-page":"A341","article-title":"Nombre d'arcs dans les graphes k-arc-fortement connexes minimaux","volume":"285","author":"Dalmazzo","year":"1977","journal-title":"CR Acad. Sci. Paris S\u00e9r. A\u2013B"},{"key":"S0963548318000469_ref22","unstructured":"Vetta A. (2001) Approximating the minimum strongly connected subgraph via a matching lower bound. In Proceedings of the Twelfth Annual ACM\u2013SIAM Symposium on Discrete Algorithms, SIAM, pp. 417\u2013426."},{"key":"S0963548318000469_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-84800-998-1"},{"key":"S0963548318000469_ref3","first-page":"35","volume-title":"Tournaments and Semicomplete Digraphs","author":"Bang-Jensen","year":"2018"},{"key":"S0963548318000469_ref4","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480199354220"},{"key":"S0963548318000469_ref18","first-page":"423","volume-title":"Combinatorics: Paul Erd\u0151s is Eighty","author":"Mader","year":"1996"},{"key":"S0963548318000469_ref21","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s3-45.1.151"},{"key":"S0963548318000469_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-015-3186-8"},{"key":"S0963548318000469_ref19","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2015.05.005"},{"key":"S0963548318000469_ref13","doi-asserted-by":"publisher","DOI":"10.1137\/16M1064805"},{"key":"S0963548318000469_ref10","first-page":"91","volume-title":"Combinatorial Algorithms","author":"Edmonds","year":"1973"},{"key":"S0963548318000469_ref20","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnw009"},{"key":"S0963548318000469_ref6","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1174"},{"key":"S0963548318000469_ref1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disc.2008.04.016"},{"key":"S0963548318000469_ref15","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/pdu019"},{"key":"S0963548318000469_ref5","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.20004"},{"key":"S0963548318000469_ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00373-004-0588-6"},{"key":"S0963548318000469_ref8","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979833920X"},{"key":"S0963548318000469_ref11","unstructured":"Garey M. R. and Johnson D. S. (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman."},{"key":"S0963548318000469_ref12","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"S0963548318000469_ref14","doi-asserted-by":"publisher","DOI":"10.1137\/15M1006611"},{"key":"S0963548318000469_ref17","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(85)90076-0"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000469","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,11]],"date-time":"2019-04-11T23:38:11Z","timestamp":1555025891000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000469\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,5]]},"references-count":22,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,5]]}},"alternative-id":["S0963548318000469"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000469","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,5]]}}}