{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T04:06:00Z","timestamp":1750910760910,"version":"3.41.0"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T00:00:00Z","timestamp":1748736000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T00:00:00Z","timestamp":1748822400000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100008047","name":"Carnegie Mellon University","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100008047","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Combinatorica"],"published-print":{"date-parts":[[2025,6]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>In a digraph, a dicut is a cut where all the arcs cross in one direction. A dijoin is a subset of arcs that intersects each dicut. Woodall conjectured in 1976 that in every digraph, the minimum size of a dicut equals to the maximum number of disjoint dijoins. However, prior to our work, it was not even known whether at least 3 disjoint dijoins exist in an arbitrary digraph whose minimum dicut size is sufficiently large. By building connections with nowhere-zero (circular) <jats:italic>k<\/jats:italic>-flows, we prove that every digraph with minimum dicut size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\tau $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c4<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> contains <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\left\\lfloor \\frac{\\tau }{k}\\right\\rfloor $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfenced>\n                    <mml:mfrac>\n                      <mml:mi>\u03c4<\/mml:mi>\n                      <mml:mi>k<\/mml:mi>\n                    <\/mml:mfrac>\n                  <\/mml:mfenced>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) <jats:italic>k<\/jats:italic>-flow. The existence of nowhere-zero 6-flows in 2-edge-connected graphs (Seymour 1981) directly leads to the existence of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\left\\lfloor \\frac{\\tau }{6}\\right\\rfloor $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfenced>\n                    <mml:mfrac>\n                      <mml:mi>\u03c4<\/mml:mi>\n                      <mml:mn>6<\/mml:mn>\n                    <\/mml:mfrac>\n                  <\/mml:mfenced>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> disjoint dijoins in a digraph with minimum dicut size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\tau $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c4<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>, which can be found in polynomial time as well. The existence of nowhere-zero circular <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\frac{2p+1}{p}$$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfrac>\n                    <mml:mrow>\n                      <mml:mn>2<\/mml:mn>\n                      <mml:mi>p<\/mml:mi>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                    <\/mml:mrow>\n                    <mml:mi>p<\/mml:mi>\n                  <\/mml:mfrac>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>-flows in 6<jats:italic>p<\/jats:italic>-edge-connected graphs (Lov\u00e1sz et al. 2013) directly leads to the existence of <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\left\\lfloor \\frac{\\tau p}{2p+1}\\right\\rfloor $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mfenced>\n                    <mml:mfrac>\n                      <mml:mrow>\n                        <mml:mi>\u03c4<\/mml:mi>\n                        <mml:mi>p<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mi>p<\/mml:mi>\n                        <mml:mo>+<\/mml:mo>\n                        <mml:mn>1<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:mfrac>\n                  <\/mml:mfenced>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> disjoint dijoins in a digraph with minimum dicut size <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>$$\\tau $$<\/jats:tex-math>\n                <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03c4<\/mml:mi>\n                <\/mml:math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula> whose underlying undirected graph is 6<jats:italic>p<\/jats:italic>-edge-connected. We also discuss reformulations of Woodall\u2019s conjecture into packing strongly connected orientations.<\/jats:p>","DOI":"10.1007\/s00493-025-00159-x","type":"journal-article","created":{"date-parts":[[2025,6,2]],"date-time":"2025-06-02T13:26:47Z","timestamp":1748870807000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Approximately Packing Dijoins via Nowhere-Zero Flows"],"prefix":"10.1007","volume":"45","author":[{"given":"G\u00e9rard","family":"Cornu\u00e9jols","sequence":"first","affiliation":[]},{"given":"Siyue","family":"Liu","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,6,2]]},"reference":[{"key":"159_CR1","doi-asserted-by":"crossref","unstructured":"Abdi, Ahmad, Cornu\u00e9jols, G\u00e9rard, Zambelli, Giacomo: Arc connectivity and submodular flows in digraphs. Combinatorica, pages 1\u201322, (2024)","DOI":"10.1007\/s00493-024-00108-0"},{"issue":"4","key":"159_CR2","doi-asserted-by":"publisher","first-page":"2417","DOI":"10.1137\/22M1506511","volume":"37","author":"Ahmad Abdi","year":"2023","unstructured":"Abdi, Ahmad, Cornu\u00e9jols, G\u00e9rard., Zlatin, Michael: On packing dijoins in digraphs and weighted digraphs. SIAM Journal on Discrete Mathematics 37(4), 2417\u20132461 (2023)","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"159_CR3","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.endm.2009.07.030","volume":"34","author":"J\u00f8rgen Bang-Jensen","year":"2009","unstructured":"Bang-Jensen, J\u00f8rgen., Kriesell, Matthias: Disjoint sub (di) graphs in digraphs. Electronic Notes in Discrete Mathematics 34, 179\u2013183 (2009)","journal-title":"Electronic Notes in Discrete Mathematics"},{"key":"159_CR4","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1007\/s00493-004-0021-z","volume":"24","author":"J\u00f8rgen Bang-Jensen","year":"2004","unstructured":"Bang-Jensen, J\u00f8rgen., Yeo, Anders: Decomposing k-arc-strong tournaments into strong spanning subdigraphs. Combinatorica 24, 331\u2013349 (2004)","journal-title":"Combinatorica"},{"key":"159_CR5","doi-asserted-by":"crossref","unstructured":"Baum, Stephen, Trotter, Leslie\u00a0E.: Integer rounding and polyhedral decomposition for totally unimodular systems. In Optimization and Operations Research: Proceedings of a Workshop Held at the University of Bonn, October 2\u20138, 1977, pages 15\u201323. Springer, (1978)","DOI":"10.1007\/978-3-642-95322-4_2"},{"key":"159_CR6","doi-asserted-by":"publisher","first-page":"18","DOI":"10.1016\/j.jctb.2016.04.002","volume":"120","author":"Maria Chudnovsky","year":"2016","unstructured":"Chudnovsky, Maria, Edwards, Katherine, Kim, Ringi, Scott, Alex, Seymour, Paul: Disjoint dijoins. Journal of Combinatorial Theory, Series B 120, 18\u201335 (2016)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"159_CR7","doi-asserted-by":"crossref","unstructured":"Cornu\u00e9jols, G\u00e9rard, Liu, Siyue, Ravi, R.: Approximately packing dijoins via nowhere-zero flows. In IPCO 2024, LNCS 14679, pages 71\u201384, (2024)","DOI":"10.1007\/978-3-031-59835-7_6"},{"key":"159_CR8","unstructured":"Devos, Matthew: Woodall\u2019s conjecture. http:\/\/www.openproblemgarden.org\/op\/woodalls_conjecture"},{"key":"159_CR9","unstructured":"Edmonds, Jack: Edge-disjoint branchings. Combinatorial Algorithms, pages 91\u201396, (1973)"},{"key":"159_CR10","doi-asserted-by":"crossref","unstructured":"Edmonds, Jack, Giles, Rick: A min-max relation for submodular functions on graphs. In Annals of Discrete Mathematics, volume\u00a01, pages 185\u2013204. Elsevier, (1977)","DOI":"10.1016\/S0167-5060(08)70734-9"},{"issue":"4","key":"159_CR11","doi-asserted-by":"publisher","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"Kapali P Eswaran","year":"1976","unstructured":"Eswaran, Kapali P., Endre Tarjan, R.: Augmentation problems. SIAM Journal on Computing 5(4), 653\u2013665 (1976)","journal-title":"SIAM Journal on Computing"},{"key":"159_CR12","unstructured":"Goddyn, Luis\u00a0A.: Some open problems I like. https:\/\/www.sfu.ca\/~goddyn\/Problems\/problems.html"},{"issue":"3","key":"159_CR13","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1002\/(SICI)1097-0118(199807)28:3<155::AID-JGT5>3.0.CO;2-J","volume":"28","author":"Luis A Goddyn","year":"1998","unstructured":"Goddyn, Luis A., Tarsi, Michael, Zhang, Cun-Quan.: On (k, d)-colorings and fractional nowhere-zero flows. Journal of Graph Theory 28(3), 155\u2013161 (1998)","journal-title":"Journal of Graph Theory"},{"key":"159_CR14","doi-asserted-by":"crossref","unstructured":"Hoffman, Alan\u00a0J.: Some recent applications of the theory of linear inequalities to extremal combinatorial analysis. In Selected Papers Of Alan J Hoffman: With Commentary, pages 244\u2013258. World Scientific, (2003)","DOI":"10.1142\/9789812796936_0025"},{"key":"159_CR15","unstructured":"Jaeger, Fran\u00e7ois: On nowhere-zero flows in multigraphs. Proceedings, Fifth British Combinatorial Conference, Aberdeen, pages 373\u2013378, (1975)"},{"issue":"1","key":"159_CR16","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1090\/S0002-9939-1976-0427156-5","volume":"55","author":"Fran\u00e7ois Jaeger","year":"1976","unstructured":"Jaeger, Fran\u00e7ois: Balanced valuations and flows in multigraphs. Proceedings of the American Mathematical Society 55(1), 237\u2013242 (1976)","journal-title":"Proceedings of the American Mathematical Society"},{"issue":"2","key":"159_CR17","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/0095-8956(79)90057-1","volume":"26","author":"Fran\u00e7ois Jaeger","year":"1979","unstructured":"Jaeger, Fran\u00e7ois: Flows and generalized coloring theorems in graphs. Journal of Combinatorial Theory, series B 26(2), 205\u2013216 (1979)","journal-title":"Journal of Combinatorial Theory, series B"},{"key":"159_CR18","doi-asserted-by":"crossref","unstructured":"Jaeger, Fran\u00e7ois: On circular flows in graphs. In Finite and Infinite Sets, pages 391\u2013402. Elsevier, (1984)","DOI":"10.1016\/B978-0-444-86893-0.50031-0"},{"key":"159_CR19","first-page":"71","volume":"3","author":"Fran\u00e7ois Jaeger","year":"1988","unstructured":"Jaeger, Fran\u00e7ois: Nowhere-zero flow problems. Selected Topics in Graph Theory 3, 71\u201395 (1988)","journal-title":"Selected Topics in Graph Theory"},{"key":"159_CR20","unstructured":"Kir\u00e1ly, Tam\u00e1s: A result on crossing families of odd sets. (2007). https:\/\/egres.elte.hu\/tr\/egres-07-10.pdf"},{"issue":"5","key":"159_CR21","doi-asserted-by":"publisher","first-page":"587","DOI":"10.1016\/j.jctb.2013.06.003","volume":"103","author":"L\u00e1szl\u00f3 Mikl\u00f3s Lov\u00e1sz","year":"2013","unstructured":"Lov\u00e1sz, L\u00e1szl\u00f3 Mikl\u00f3s., Thomassen, Carsten, Yezhou, Wu., Zhang, Cun-Quan.: Nowhere-zero 3-flows and modulo k-orientations. Journal of Combinatorial Theory, Series B 103(5), 587\u2013598 (2013)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"6","key":"159_CR22","doi-asserted-by":"publisher","first-page":"1485","DOI":"10.1007\/s00493-018-3862-6","volume":"38","author":"Andr\u00e1s M\u00e9sz\u00e1ros","year":"2018","unstructured":"M\u00e9sz\u00e1ros, Andr\u00e1s: A note on disjoint dijoins. Combinatorica 38(6), 1485\u20131488 (2018)","journal-title":"Combinatorica"},{"issue":"1","key":"159_CR23","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1112\/jlms\/s1-39.1.12","volume":"1","author":"C\u00a0St\u00a0JA Nash-Williams","year":"1964","unstructured":"Nash-Williams, C\u00a0St.\u00a0J.A.: Decomposition of finite graphs into forests. Journal of the London Mathematical Society 1(1), 12\u201312 (1964)","journal-title":"Journal of the London Mathematical Society"},{"issue":"5","key":"159_CR24","doi-asserted-by":"publisher","first-page":"281","DOI":"10.2307\/2303897","volume":"46","author":"Herbert Ellis Robbins","year":"1939","unstructured":"Robbins, Herbert Ellis: A theorem on graphs, with an application to a problem of traffic control. The American Mathematical Monthly 46(5), 281\u2013283 (1939)","journal-title":"The American Mathematical Monthly"},{"key":"159_CR25","unstructured":"Schrijver, Alexander: Observations on Woodall\u2019s conjecture. https:\/\/homepages.cwi.nl\/~lex\/files\/woodall.pdf"},{"key":"159_CR26","doi-asserted-by":"publisher","first-page":"213","DOI":"10.1016\/0012-365X(80)90057-6","volume":"32","author":"Alexander Schrijver","year":"1980","unstructured":"Schrijver, Alexander: A counterexample to a conjecture of Edmonds and Giles. Discrete Mathematics 32, 213\u2013214 (1980)","journal-title":"Discrete Mathematics"},{"key":"159_CR27","unstructured":"Schrijver, Alexander: Theory of linear and integer programming. John Wiley & Sons, (1998)"},{"key":"159_CR28","unstructured":"Schrijver, Alexander, et\u00a0al.: Combinatorial optimization: polyhedra and efficiency, volume\u00a024. Springer, (2003)"},{"issue":"2","key":"159_CR29","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1016\/0095-8956(81)90058-7","volume":"30","author":"Paul D Seymour","year":"1981","unstructured":"Seymour, Paul D.: Nowhere-zero 6-flows. Journal of Combinatorial Theory, series B 30(2), 130\u2013135 (1981)","journal-title":"Journal of Combinatorial Theory, series B"},{"key":"159_CR30","doi-asserted-by":"crossref","unstructured":"Shepherd, Bruce, Vetta, Adrian: Visualizing, finding and packing dijoins. Graph Theory and Combinatorial Optimization, pages 219\u2013254, (2005)","DOI":"10.1007\/0-387-25592-3_8"},{"issue":"2","key":"159_CR31","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1016\/j.jctb.2011.09.003","volume":"102","author":"Carsten Thomassen","year":"2012","unstructured":"Thomassen, Carsten: The weak 3-flow conjecture and the weak circular flow conjecture. Journal of Combinatorial Theory, Series B 102(2), 521\u2013529 (2012)","journal-title":"Journal of Combinatorial Theory, Series B"},{"key":"159_CR32","doi-asserted-by":"publisher","first-page":"80","DOI":"10.4153\/CJM-1954-010-9","volume":"6","author":"William Thomas Tutte","year":"1954","unstructured":"William Thomas Tutte: A contribution to the theory of chromatic polynomials. Canadian Journal of Mathematics 6, 80\u201391 (1954)","journal-title":"Canadian Journal of Mathematics"},{"key":"159_CR33","doi-asserted-by":"crossref","unstructured":"Woodall, Douglas\u00a0R.: Menger and K\u00f6nig systems. Theory and Applications of Graphs: Proceedings, Michigan May 11\u201315, 1976, pages 620\u2013635, (1978)","DOI":"10.1007\/BFb0070416"},{"issue":"3","key":"159_CR34","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1002\/jgt.3190070307","volume":"7","author":"DH Younger","year":"1983","unstructured":"Younger, D.H.: Integer flows. Journal of Graph Theory 7(3), 349\u2013357 (1983)","journal-title":"Journal of Graph Theory"}],"container-title":["Combinatorica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00159-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00493-025-00159-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00493-025-00159-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,25]],"date-time":"2025-06-25T13:15:31Z","timestamp":1750857331000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00493-025-00159-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2025,6]]}},"alternative-id":["159"],"URL":"https:\/\/doi.org\/10.1007\/s00493-025-00159-x","relation":{},"ISSN":["0209-9683","1439-6912"],"issn-type":[{"type":"print","value":"0209-9683"},{"type":"electronic","value":"1439-6912"}],"subject":[],"published":{"date-parts":[[2025,6]]},"assertion":[{"value":"3 November 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2025","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2025","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 June 2025","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"32"}}