Abstract
In this paper, we bound the integrality gap and the approximation ratio for maximum plane multiflow problems and deduce bounds on the flow-cut-gap. Planarity means here that the union of the supply and demand graph is planar. We first prove that there exists a multiflow of value at least half of the capacity of a minimum multicut. We then show how to convert any multiflow into a half-integer one of value at least half of the original multiflow. Finally, we round any half-integer multiflow into an integer multiflow, losing again at most half of the value, in polynomial time, achieving a 1/4-approximation algorithm for maximum integer multiflows in the plane, and an integer-flow-cut gap of 8.
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
Similar content being viewed by others
Notes
- 1.
Given a partition of V so that all edges in F join different classes, those of E joining different classes form a multicut, and inclusionwise minimal multicuts are like this.
- 2.
Seymour’s correspondence through dualisation reduces this problem to checking whether \(F^*\) is a minimum weight “\(T_{F^*}\)-join” (see e.g. [20]) in \((G+H)^*\) with weights defined by c and d, where \(T_{F^*}\) is the set of odd degree vertices of \(F^*\). This also provides a polynomial separation algorithm for maximising the sum of (not necessarily integer) demands satisfying the cut condition.
- 3.
i.e. a cut with both shores containing more than one vertex, and meeting every perfect matching in exactly one edge. Lovász characterised graphs without nontrivial tight cuts as “bicritical 3-connected graphs” [15]. Such graphs may have arbitrarily many vertices, even under the planarity constraint.
- 4.
This is not an allowed step for a polynomial algorithm, but it will not really be necessary to do it. The choice of the cuts to be rounded down or up will be clear from the proof without actually executing this subdivision. The choices for rounding concern a family of size O(|V|).
- 5.
\(\{\delta _{E^*\cup F^*}(L)^*:L\in \mathcal {L}\}=\{P\cup e_P: P\in \mathcal {P}, f(P)>0\}\), as before.
References
Appel, K., Haken, W.: A proof of the four color theorem. Discrete Math. 16, 179–180 (1976)
Baker, B.S.: Approximation algorithms for np-complete problems on planar graphs. J. ACM 41(1), 153–180 (1994)
Cheriyan, J., Karloff, H., Khandekar, R., Könemann, J.: On the integrality ratio for tree augmentation. Oper. Res. Lett. 36(4), 399–401 (2008)
Edmonds, J., Rick, G.: A min-max relation for submodular functions in graphs. Ann. Discrete Math. I, 185–204 (1977)
Fiorini, S., Hardy, N., Reed, B., Vetta, A.: Approximate min-max relations for odd cycles in planar graphs. Math. Program. 110(1), 71–91 (1995)
Frank, A., Szigeti, Z.: A note on packing paths in planar graphs. Math. Program. 70, 201–209 (1995)
Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. SIAM J. Comput. 25(2), 235–251 (1996)
Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3–20 (1997)
Hoffman, A.J., Kruskal, J.B.: Integral boundary points of convex polyhedra. In: Linear Inequalities and Related Systems, pp. 223–246 (1956)
Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 682–690. ACM (1993)
Klein, P.N., Mathieu, C., Zhou, H.: Correlation clustering and two-edge-connected augmentation for planar graphs. In: 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2015)
Korach, E., Penn, M.: Tight integral duality gap in the chinese postman problem. Mateh. Program. 55, 183–191 (1992)
Korte, B., Vygen, J.: Combinatorial Optimization: Theory and Algorithms, Collection Algorithms and Combinatorics, vol. 21, 5th edn. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-24488-9
Král, D., Voss, H.: Edge-disjoint odd cycles in planar graphs. J. Comb. Theor. Ser. B 90, 107–120 (2004)
Lovász, L., Plummer, M.: Matching Theory. Akadémiai Kiadó and Springer (1986)
Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica 13(1), 97–107 (1993)
Okamura, H., Seymour, P.D.: Multicommodity flows in planar graphs. J. Comb. Theor. Ser. B 31(1), 75–81 (1981)
Robertson, N., Sanders, D.P., Seymour, P., Thomas, R.: Efficiently four-coloring planar graphs. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp. 571–575 (1996)
Schrijver, A.: Theory of Linear and Integer Programming. Wiley and Chichester (1986)
Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency, vol. 24. Springer, Heidelberg (2003)
Seguin-Charbonneau, L., Bruce Shepherd, F.: Maximum edge-disjoint paths in planar graphs with congestion 2. In: 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 200–209. IEEE (2011)
Seymour, P.D.: On odd cuts and plane multicommodity flows. Proc. London Math. Soc. 3(1), 178–192 (1981)
Tardos, É., Vazirani, V.V.: Improved bounds for the max-flow min-multicut ratio for planar and k\(\_\)r, r-free graphs. Inf. Process. Lett. 47(2), 77–80 (1993)
Tutte, W.T.: Lectures on matroids. J. Res. Nat. Bur. Stan. B 69, 1–47 (1965)
Williamson, D.P., Goemans, M.X., Mihail, M., Vazirani, V.V.: A primal-dual approximation algorithm for generalized steiner network problems. Combinatorica 15(3), 435–454 (1995)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2020 Springer Nature Switzerland AG
About this paper
Cite this paper
Garg, N., Kumar, N., Sebő, A. (2020). Integer Plane Multiflow Maximisation: Flow-Cut Gap and One-Quarter-Approximation. In: Bienstock, D., Zambelli, G. (eds) Integer Programming and Combinatorial Optimization. IPCO 2020. Lecture Notes in Computer Science(), vol 12125. Springer, Cham. https://doi.org/10.1007/978-3-030-45771-6_12
Download citation
DOI: https://doi.org/10.1007/978-3-030-45771-6_12
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-45770-9
Online ISBN: 978-3-030-45771-6
eBook Packages: Computer ScienceComputer Science (R0)