Abstract
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) k-flows, we prove that every digraph with minimum dicut size \(\tau \) contains \(\frac{\tau }{k}\) disjoint dijoins if the underlying undirected graph admits a nowhere-zero (circular) k-flow. The existence of nowhere-zero 6-flows in 2-edge-connected graphs (Seymour 1981) directly leads to the existence of \(\frac{\tau }{6}\) disjoint dijoins in a digraph with minimum dicut size \(\tau \), which can be found in polynomial time as well. The existence of nowhere-zero circular \(\frac{2p+1}{p}\)-flows in 6p-edge-connected graphs (Lovász et al. 2013) directly leads to the existence of \(\frac{\tau p}{2p+1}\) disjoint dijoins in a digraph with minimum dicut size \(\tau \) whose underlying undirected graph is 6p-edge-connected.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
References
Abdi, A., Cornuéjols, G., Zambelli, G.: Arc connectivity and submodular flows in digraphs (2023). https://www.andrew.cmu.edu/user/gc0v/webpub/connectedflip.pdf
Abdi, A., Cornuéjols, G., Zlatin, M.: On packing dijoins in digraphs and weighted digraphs. SIAM J. Discret. Math. 37(4), 2417–2461 (2023)
Bang-Jensen, J., Kriesell, M.: Disjoint sub (di) graphs in digraphs. Electron. Notes Discrete Math. 34, 179–183 (2009)
Bang-Jensen, J., Yeo, A.: Decomposing k-arc-strong tournaments into strong spanning subdigraphs. Combinatorica 24, 331–349 (2004)
Chudnovsky, M., Edwards, K., Kim, R., Scott, A., Seymour, P.: Disjoint dijoins. J. Combin. Theory Ser. B 120, 18–35 (2016)
Devos, M.: Woodall’s conjecture. http://www.openproblemgarden.org/op/woodalls_conjecture
Edmonds, J.: Edge-disjoint branchings. Combin. Algorithms 91–96 (1973)
Edmonds, J., Giles, R.: A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185–204 (1977)
Goddyn, L.A.: Some open problems I like. https://www.sfu.ca/~goddyn/Problems/problems.html
Goddyn, L.A., Tarsi, M., Zhang, C.-Q.: On (k, d)-colorings and fractional nowhere-zero flows. J. Graph Theory 28(3), 155–161 (1998)
Jaeger, F.: On nowhere-zero flows in multigraphs. In: Proceedings, Fifth British Combinatorial Conference, Aberdeen, pp. 373–378 (1975)
Jaeger, F.: Flows and generalized coloring theorems in graphs. J. Combin. Theory Ser. B 26(2), 205–216 (1979)
Jaeger, F.: On circular flows in graphs. In: Finite and Infinite Sets, pp. 391–402. Elsevier (1984)
Jaeger, F.: Nowhere-zero flow problems. Sel. Top. Graph Theory 3, 71–95 (1988)
Király, T.: A result on crossing families of odd sets (2007). https://egres.elte.hu/tr/egres-07-10.pdf
Lovász, L.: Combinatorial Problems and Exercises, vol. 361. American Mathematical Society (2007)
Lovász, L.M., Thomassen, C., Wu, Y., Zhang, C.-Q.: Nowhere-zero 3-flows and modulo k-orientations. J. Combin. Theory Ser. B 103(5), 587–598 (2013)
Mészáros, A.: A note on disjoint dijoins. Combinatorica 38(6), 1485–1488 (2018)
Schrijver, A.: Observations on Woodall’s conjecture. https://homepages.cwi.nl/~lex/files/woodall.pdf
Schrijver, A.: A counterexample to a conjecture of Edmonds and Giles. Discret. Math. 32, 213–214 (1980)
Schrijver, A.: Total dual integrality from directed graphs, crossing families, and sub-and supermodular functions. In: Progress in Combinatorial Optimization, pp. 315–361. Elsevier (1984)
Seymour, P.D.: Nowhere-zero 6-flows. J. Combin. Theory Ser. B 30(2), 130–135 (1981)
Shepherd, B., Vetta, A.: Visualizing, finding and packing dijoins. Graph Theory Combin. Optim. 219–254 (2005)
Thomassen, C.: The weak 3-flow conjecture and the weak circular flow conjecture. J. Combin. Theory Ser. B 102(2), 521–529 (2012)
Tutte, W.T.: A contribution to the theory of chromatic polynomials. Can. J. Math. 6, 80–91 (1954)
Woodall, D.R.: Menger and König systems. In: Theory and Applications of Graphs: Proceedings, Michigan, 11–15 May 1976, pp. 620–635 (1978)
Younger, D.H.: Integer flows. J. Graph Theory 7(3), 349–357 (1983)
Acknowledgements
The first author is supported by the U.S. Office of Naval Research under award number N00014-22-1-2528, the second author is supported by a Balas Ph.D. Fellowship from the Tepper School, Carnegie Mellon University and the third author is supported by the U.S. Office of Naval Research under award number N00014-21-1-2243 and the Air Force Office of Scientific Research under award number FA9550-20-1-0080. We thank Ahmad Abdi, Olha Silina and Michael Zlatin for invaluable discussions, and the referees for their detailed suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cornuéjols, G., Liu, S., Ravi, R. (2024). Approximately Packing Dijoins via Nowhere-Zero Flows. In: Vygen, J., Byrka, J. (eds) Integer Programming and Combinatorial Optimization. IPCO 2024. Lecture Notes in Computer Science, vol 14679. Springer, Cham. https://doi.org/10.1007/978-3-031-59835-7_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-59835-7_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-59834-0
Online ISBN: 978-3-031-59835-7
eBook Packages: Computer ScienceComputer Science (R0)