{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,31]],"date-time":"2025-12-31T00:13:03Z","timestamp":1767139983141,"version":"build-2238731810"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T00:00:00Z","timestamp":1716854400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T00:00:00Z","timestamp":1716854400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2024,10]]},"abstract":"Abstract<\/jats:title>\n \n Let\n \n \n $$D=(V,A)$$<\/jats:tex-math>\n \n \n D<\/mml:mi>\n =<\/mml:mo>\n (<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n A<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be a digraph. For an integer\n \n \n $$k\\ge 1$$<\/jats:tex-math>\n \n \n k<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , a\n k<\/jats:italic>\n -\n arc-connected flip<\/jats:italic>\n is an arc subset of\n D<\/jats:italic>\n such that after reversing the arcs in it the digraph becomes (strongly)\n k<\/jats:italic>\n -arc-connected. The first main result of this paper introduces a sufficient condition for the existence of a\n k<\/jats:italic>\n -arc-connected flip that is also a submodular flow for a crossing submodular function. More specifically, given some integer\n \n \n $$\\tau \\ge 1$$<\/jats:tex-math>\n \n \n \u03c4<\/mml:mi>\n \u2265<\/mml:mo>\n 1<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , suppose\n \n \n $$d_A^+(U)+(\\frac{\\tau }{k}-1)d_A^-(U)\\ge \\tau $$<\/jats:tex-math>\n \n \n \n d<\/mml:mi>\n A<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n +<\/mml:mo>\n \n (<\/mml:mo>\n \n \u03c4<\/mml:mi>\n k<\/mml:mi>\n <\/mml:mfrac>\n -<\/mml:mo>\n 1<\/mml:mn>\n )<\/mml:mo>\n <\/mml:mrow>\n \n d<\/mml:mi>\n A<\/mml:mi>\n -<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \u03c4<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for all\n \n \n $$U\\subsetneq V, U\\ne \\emptyset $$<\/jats:tex-math>\n \n \n U<\/mml:mi>\n \u228a<\/mml:mo>\n V<\/mml:mi>\n ,<\/mml:mo>\n U<\/mml:mi>\n \u2260<\/mml:mo>\n \u2205<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , where\n \n \n $$d_A^+(U)$$<\/jats:tex-math>\n \n \n \n d<\/mml:mi>\n A<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n $$d_A^-(U)$$<\/jats:tex-math>\n \n \n \n d<\/mml:mi>\n A<\/mml:mi>\n -<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n denote the number of arcs in\n A<\/jats:italic>\n leaving and entering\n U<\/jats:italic>\n , respectively. Let\n \n \n $${\\mathcal {C}}$$<\/jats:tex-math>\n \n C<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be a crossing family over ground set\n V<\/jats:italic>\n , and let\n \n \n $$f:{\\mathcal {C}}\\rightarrow {\\mathbb {Z}}$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n :<\/mml:mo>\n C<\/mml:mi>\n \u2192<\/mml:mo>\n Z<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n be a crossing submodular function such that\n \n \n $$f(U)\\ge \\frac{k}{\\tau }(d_A^+(U)-d_A^-(U))$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n k<\/mml:mi>\n \u03c4<\/mml:mi>\n <\/mml:mfrac>\n \n (<\/mml:mo>\n \n d<\/mml:mi>\n A<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n -<\/mml:mo>\n \n d<\/mml:mi>\n A<\/mml:mi>\n -<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for all\n \n \n $$U\\in {\\mathcal {C}}$$<\/jats:tex-math>\n \n \n U<\/mml:mi>\n \u2208<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . Then\n D<\/jats:italic>\n has a\n k<\/jats:italic>\n -arc-connected flip\n J<\/jats:italic>\n such that\n \n \n $$f(U)\\ge d_J^+(U)-d_J^-(U)$$<\/jats:tex-math>\n \n \n f<\/mml:mi>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \n d<\/mml:mi>\n J<\/mml:mi>\n +<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n -<\/mml:mo>\n \n d<\/mml:mi>\n J<\/mml:mi>\n -<\/mml:mo>\n <\/mml:msubsup>\n \n (<\/mml:mo>\n U<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n for all\n \n \n $$U\\in {\\mathcal {C}}$$<\/jats:tex-math>\n \n \n U<\/mml:mi>\n \u2208<\/mml:mo>\n C<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . The result has several applications to Graph Orientations and Combinatorial Optimization. In particular, it strengthens Nash-Williams\u2019 so-called\n weak orientation theorem<\/jats:italic>\n , and proves a weaker variant of Woodall\u2019s conjecture on digraphs whose underlying undirected graph is\n \n \n $$\\tau $$<\/jats:tex-math>\n \n \u03c4<\/mml:mi>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -edge-connected. The second main result of this paper is even more general. It introduces a sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This sufficient condition implies the classic result of Edmonds and Giles on the box-total dual integrality of a submodular flow system. It also has the consequence that in a weakly connected digraph, the intersection of two submodular flow systems is totally dual integral.\n <\/jats:p>","DOI":"10.1007\/s00493-024-00108-0","type":"journal-article","created":{"date-parts":[[2024,5,28]],"date-time":"2024-05-28T03:01:58Z","timestamp":1716865318000},"page":"1069-1090","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Arc Connectivity and Submodular Flows in Digraphs"],"prefix":"10.1007","volume":"44","author":[{"given":"Ahmad","family":"Abdi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00e9rard","family":"Cornu\u00e9jols","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Giacomo","family":"Zambelli","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,5,28]]},"reference":[{"issue":"3","key":"108_CR1","doi-asserted-by":"publisher","first-page":"251","DOI":"10.1016\/0095-8956(80)90071-4","volume":"28","author":"A Frank","year":"1980","unstructured":"Frank, A.: On the orientation of graphs. J. Combinat. Theo. Ser. B 28(3), 251\u2013261 (1980)","journal-title":"J. Combinat. Theo. Ser. B"},{"key":"108_CR2","unstructured":"Frank, A.: Connections in Combinatorial Optimization. Oxford Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2011)"},{"key":"108_CR3","volume-title":"Combinatorial Optimization, Polyhedra and Efficiency","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization, Polyhedra and Efficiency. Springer, Berlin, Heidelberg (2003)"},{"key":"108_CR4","unstructured":"Nash-Williams, C.S.J.: Well-balanced orientations of finite graphs and unobtrusive odd-vertex-pairings. In: Recent progress in Combinatorics (Proc. Third Waterloo Conf. on Combinatorics, 1968), pages 133\u2013149. Academic Press (1969)"},{"key":"108_CR5","doi-asserted-by":"crossref","unstructured":"Ito, T., Iwamasa, Y.,\u00a0Kakimura, N., Kamiyama, N., Kobayashi, Y., Maezawa, S.-I., Nozaki, Y., Okamoto, Y., Ozeki, K.: Monotone edge flips to an orientation of maximum edge-connectivity \u00e0 la Nash-Williams. ACM Trans. Algorithms, 19(1), (2023)","DOI":"10.1145\/3561302"},{"issue":"4","key":"108_CR6","doi-asserted-by":"publisher","first-page":"2417","DOI":"10.1137\/22M1506511","volume":"37","author":"A Abdi","year":"2023","unstructured":"Abdi, A., Cornu\u00e9jols, G., Zlatin, M.: On packing dijoins in digraphs and weighted digraphs. SIAM J. Discrete Math. 37(4), 2417\u20132461 (2023)","journal-title":"SIAM J. Discrete Math."},{"key":"108_CR7","doi-asserted-by":"crossref","unstructured":"Woodall., D.: Menger and K\u00f6nig systems. In: Alavi, Y., Lick, D. (eds.), Theory and Applications of Graphs, volume 642 of Lecture Notes in Mathematics. Springer, Berlin, Heidelberg (1978)","DOI":"10.1007\/BFb0070416"},{"key":"108_CR8","doi-asserted-by":"crossref","unstructured":"Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. In: Studies in integer programming (Proc. Workshop, Bonn, 1975), pages 185\u2013204. Ann. of Discrete Math. Vol. 1. (1977)","DOI":"10.1016\/S0167-5060(08)70734-9"},{"issue":"1","key":"108_CR9","doi-asserted-by":"publisher","first-page":"352","DOI":"10.1007\/BF01580250","volume":"6","author":"AJ Hoffman","year":"1974","unstructured":"Hoffman, A.J.: A generalization of max flow-min cut. Math. Progr. 6(1), 352\u2013359 (1974)","journal-title":"Math. Progr."},{"key":"108_CR10","doi-asserted-by":"crossref","unstructured":"Schrijver, A.: Total dual integrality from directed graphs, crossing families, and sub- and supermodular functions. In: Pulleyblank, W.R. (ed.), Progress in Combinatorial Optimization, pages 315\u2013361, Academic Press (1984)","DOI":"10.1016\/B978-0-12-566780-7.50025-8"},{"issue":"1","key":"108_CR11","doi-asserted-by":"publisher","first-page":"489","DOI":"10.1007\/BF01589418","volume":"42","author":"A Frank","year":"1988","unstructured":"Frank, A., Tardos, \u00c9.: Generalized polymatroids and submodular flows. Math. Progr. 42(1), 489\u2013563 (1988)","journal-title":"Math. Progr."},{"issue":"1","key":"108_CR12","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1007\/s10107-020-01514-0","volume":"188","author":"P Chervet","year":"2021","unstructured":"Chervet, P., Grappe, R., Robert, L.-H.: Box-total dual integrality, box-integrality, and equimodular matrices. Math. Progr. 188(1), 319\u2013349 (2021)","journal-title":"Math. Progr."},{"issue":"2","key":"108_CR13","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0012-365X(80)90057-6","volume":"32","author":"A Schrijver","year":"1980","unstructured":"Schrijver, A.: A counterexample to a conjecture of Edmonds and Giles. Discrete Math. 32(2), 213\u2013215 (1980)","journal-title":"Discrete Math."},{"issue":"3","key":"108_CR14","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1112\/jlms\/s2-17.3.369","volume":"17","author":"CL Lucchesi","year":"1978","unstructured":"Lucchesi, C.L., Younger, D.H.: A minimax theorem for directed graphs. J. London Math. Soc. (2) 17(3), 369\u2013374 (1978)","journal-title":"J. London Math. Soc. (2)"},{"key":"108_CR15","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1112\/jlms\/s1-36.1.445","volume":"36","author":"CSJA Nash-Williams","year":"1961","unstructured":"Nash-Williams, C.S.J.A.: Edge-disjoint spanning trees of finite graphs. J. Lond. Math. Soc. 36, 445\u2013450 (1961)","journal-title":"J. Lond. Math. Soc."},{"key":"108_CR16","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1112\/jlms\/s1-36.1.221","volume":"36","author":"WT Tutte","year":"1961","unstructured":"Tutte, W.T.: On the problem of decomposing a graph into $$n$$ connected factors. J. Lond. Math. Soc. 36, 221\u2013230 (1961)","journal-title":"J. Lond. Math. Soc."},{"issue":"6","key":"108_CR17","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1007\/s00493-018-3862-6","volume":"38","author":"A M\u00e9sz\u00e1ros","year":"2018","unstructured":"M\u00e9sz\u00e1ros, A.: A note on disjoint dijoins. Combinatorica 38(6), 1485\u20131488 (2018)","journal-title":"Combinatorica"},{"issue":"3","key":"108_CR18","doi-asserted-by":"publisher","first-page":"334","DOI":"10.1287\/moor.7.3.334","volume":"7","author":"EL Lawler","year":"1982","unstructured":"Lawler, E.L., Martel, C.U.: Computing maximal \u201cpolymatroidal\u2019\u2019 network flows. Math. Oper. Res. 7(3), 334\u2013347 (1982)","journal-title":"Math. Oper. Res."},{"issue":"3","key":"108_CR19","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1016\/0095-8956(84)90029-7","volume":"36","author":"A Frank","year":"1984","unstructured":"Frank, A.: Finding feasible vectors of Edmonds-Giles polyhedra. J. Combinat. Theo. Ser. B 36(3), 221\u2013239 (1984)","journal-title":"J. Combinat. Theo. Ser. B"},{"key":"108_CR20","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jctb.2016.04.002","volume":"120","author":"M Chudnovsky","year":"2016","unstructured":"Chudnovsky, M., Edwards, K., Kim, R., Scott, A., Seymour, P.: Disjoint dijoins. J. Combinat. Theo. Ser. B 120, 18\u201335 (2016)","journal-title":"J. Combinat. Theo. Ser. B"},{"key":"108_CR21","unstructured":"Goemans, M.X., Pan, Y.: A counterexample to box-half-integrality of the intersection of crossing submodular flow systems. Manuscript (2023)"},{"issue":"2","key":"108_CR22","first-page":"73","volume":"3","author":"T Akiyama","year":"1980","unstructured":"Akiyama, T., Nishizeki, T., Saito, N.: NP-Completeness of the Hamiltonian cycle problem for bipartite graphs. J. Inf. Process. 3(2), 73\u201376 (1980)","journal-title":"J. Inf. Process."},{"key":"108_CR23","unstructured":"Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-completeness. Mathematical Sciences Series, Freemans (1979)"}],"updated-by":[{"DOI":"10.1007\/s00493-024-00121-3","type":"erratum","label":"Erratum","source":"publisher","updated":{"date-parts":[[2024,8,5]],"date-time":"2024-08-05T00:00:00Z","timestamp":1722816000000}}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00108-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-024-00108-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-024-00108-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,7]],"date-time":"2024-10-07T08:09:17Z","timestamp":1728288557000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-024-00108-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,28]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["108"],"URL":"https:\/\/doi.org\/10.1007\/s00493-024-00108-0","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"value":"0209-9683","type":"print"},{"value":"1439-6912","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5,28]]},"assertion":[{"value":"7 April 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2024","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 April 2024","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 May 2024","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 August 2024","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Erratum","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"An Erratum to this paper has been published:","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00493-024-00121-3","URL":"https:\/\/doi.org\/10.1007\/s00493-024-00121-3","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}