{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,22]],"date-time":"2025-04-22T15:10:34Z","timestamp":1745334634086,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T00:00:00Z","timestamp":1696809600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T00:00:00Z","timestamp":1696809600000},"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":["Discrete Comput Geom"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We devise the first constant-factor approximation algorithm for finding an integral multi-commodity flow of maximum total value for instances where the supply graph together with the demand edges can be embedded on an orientable surface of bounded genus. This extends recent results for planar instances. Our techniques include an uncrossing algorithm, which is significantly more difficult than in the planar case, a partition of the cycles in the support of an LP solution into free homotopy classes, and a new rounding procedure for freely homotopic non-separating cycles.<\/jats:p>","DOI":"10.1007\/s00454-023-00552-7","type":"journal-article","created":{"date-parts":[[2023,10,9]],"date-time":"2023-10-09T14:03:59Z","timestamp":1696860239000},"page":"1266-1291","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Approximating Maximum Integral Multiflows on Bounded Genus Graphs"],"prefix":"10.1007","volume":"70","author":[{"given":"Chien-Chung","family":"Huang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8074-0241","authenticated-orcid":false,"given":"Mathieu","family":"Mari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Claire","family":"Mathieu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jens","family":"Vygen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,9]]},"reference":[{"key":"552_CR1","volume-title":"Network Flows","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows. Prentice Hall, Englewood Cliffs (1993)"},{"issue":"5","key":"552_CR2","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/s00493-010-2455-9","volume":"30","author":"M Andrews","year":"2010","unstructured":"Andrews, M., Chuzhoy, J., Guruswami, V., Khanna, S., Talwar, K., Zhang, L.: Inapproximability of edge-disjoint paths and low congestion routing on undirected graphs. Combinatorica 30(5), 485\u2013520 (2010)","journal-title":"Combinatorica"},{"issue":"4","key":"552_CR3","first-page":"629","volume":"12","author":"L Auslander","year":"1963","unstructured":"Auslander, L., Brown, T.A., Youngs, J.W.T.: The imbedding of graphs in manifolds. J. Math. Mech. 12(4), 629\u2013634 (1963)","journal-title":"J. Math. Mech."},{"issue":"2","key":"552_CR4","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1007\/s00037-006-0210-9","volume":"15","author":"S Chawla","year":"2006","unstructured":"Chawla, S., Krauthgamer, R., Kumar, R., Rabani, Y., Sivakumar, D.: On the hardness of approximating multicut and sparsest-cut. Comput. Complex. 15(2), 94\u2013114 (2006)","journal-title":"Comput. Complex."},{"key":"552_CR5","doi-asserted-by":"publisher","first-page":"137","DOI":"10.4086\/toc.2006.v002a007","volume":"2","author":"C Chekuri","year":"2006","unstructured":"Chekuri, C., Khanna, S., Shepherd, F.B.: An $$O(\\sqrt{n})$$ approximation and integrality gap for disjoint paths and unsplittable flow. Theory Comput. 2, 137\u2013146 (2006)","journal-title":"Theory Comput."},{"issue":"2","key":"552_CR6","doi-asserted-by":"publisher","first-page":"248","DOI":"10.1016\/j.jctb.2012.11.002","volume":"103","author":"C Chekuri","year":"2013","unstructured":"Chekuri, C., Shepherd, F.B., Weibel, C.: Flow-cut gaps for integer and fractional multiflows. J. Comb. Theory Ser. B 103(2), 248\u2013273 (2013)","journal-title":"J. Comb. Theory Ser. B"},{"key":"552_CR7","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: Almost polynomial hardness of node-disjoint paths in grids. Theory Comput. 17(6), #\u00a06 (2021)","DOI":"10.4086\/toc.2021.v017a006"},{"key":"552_CR8","doi-asserted-by":"crossref","unstructured":"Chuzhoy, J., Kim, D.H.K., Nimavat, R.: New hardness results for routing on disjoint paths. SIAM J. Comput. 51(2), STOC17-189\u2013STOC17-237 (2022)","DOI":"10.1137\/17M1146580"},{"issue":"1","key":"552_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/18M1183297","volume":"50","author":"V Cohen-Addad","year":"2021","unstructured":"Cohen-Addad, V., Colin\u00a0de Verdi\u00e8re, \u00c9., de\u00a0Mesmay, A.: A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals. SIAM J. Comput. 50(1), 1\u201331 (2021)","journal-title":"SIAM J. Comput."},{"key":"552_CR10","unstructured":"Colin\u00a0de Verdi\u00e8re, \u00c9.: Computational topology of graphs on surfaces. In: Handbook of Discrete and Computational Geometry, pp. 605\u2013636 (chapter 23). CRC Press, Boca Raton (2018)"},{"issue":"1","key":"552_CR11","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.ejor.2003.10.037","volume":"162","author":"M-C Costa","year":"2005","unstructured":"Costa, M.-C., L\u00e9tocart, L., Roupin, F.: Minimal multicut and maximal integer multiflow: a survey. Eur. J. Oper. Res. 162(1), 55\u201369 (2005)","journal-title":"Eur. J. Oper. Res."},{"issue":"4","key":"552_CR12","doi-asserted-by":"publisher","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"key":"552_CR13","doi-asserted-by":"publisher","first-page":"83","DOI":"10.1007\/BF02392203","volume":"115","author":"DBA Epstein","year":"1966","unstructured":"Epstein, D.B.A.: Curves on $$2$$-manifolds and isotopies. Acta Math. 115, 83\u2013107 (1966)","journal-title":"Acta Math."},{"key":"552_CR14","doi-asserted-by":"crossref","unstructured":"Erickson, J., Whittlesey, K.: Transforming curves on surfaces redux. In: 24th Annual ACM-SIAM Symposium on Discrete Algorithms (New Orleans 2013), pp. 1646\u20131655. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.118"},{"issue":"1","key":"552_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s10107-006-0063-7","volume":"110","author":"S Fiorini","year":"2007","unstructured":"Fiorini, S., Hardy, N., Reed, B., Vetta, A.: Approximate min-max relations for odd cycles in planar graphs. Math. Program. 110(1), 71\u201391 (2007)","journal-title":"Math. Program."},{"key":"552_CR16","volume-title":"Flows in Networks","author":"LR Ford Jr","year":"1962","unstructured":"Ford, L.R., Jr., Fulkerson, D.R.: Flows in Networks. Princeton University Press, Princeton (1962)"},{"key":"552_CR17","doi-asserted-by":"crossref","unstructured":"Garg, N., Kumar, N., Seb\u0151, A.: Integer plane multiflow maximisation: flow-cut gap and one-quarter-approximation. In: 21st International Conference on Integer Programming and Combinatorial Optimization. Lecture Notes in Computer Science, vol. 12125, pp. 144\u2013157. Springer, Cham (2020)","DOI":"10.1007\/978-3-030-45771-6_12"},{"issue":"2","key":"552_CR18","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1137\/S0097539793243016","volume":"25","author":"N Garg","year":"1996","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25(2), 235\u2013251 (1996)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"552_CR19","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF02523685","volume":"18","author":"N Garg","year":"1997","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18(1), 3\u201320 (1997)","journal-title":"Algorithmica"},{"issue":"6","key":"552_CR20","doi-asserted-by":"publisher","first-page":"1828","DOI":"10.1007\/s00039-019-00517-0","volume":"29","author":"JE Greene","year":"2019","unstructured":"Greene, J.E.: On loops intersecting at most once. Geom. Funct. Anal. 29(6), 1828\u20131843 (2019)","journal-title":"Geom. Funct. Anal."},{"key":"552_CR21","first-page":"332","volume":"24","author":"PJ Heawood","year":"1890","unstructured":"Heawood, P.J.: Map colour theorem. Q. J. Math. 24, 332\u2013338 (1890)","journal-title":"Q. J. Math."},{"issue":"2","key":"552_CR22","doi-asserted-by":"publisher","first-page":"752","DOI":"10.1137\/20M1319401","volume":"35","author":"C-C Huang","year":"2021","unstructured":"Huang, C.-C., Mari, M., Mathieu, C., Schewior, K., Vygen, J.: An approximation algorithm for fully planar edge-disjoint paths. SIAM J. Discret. Math. 35(2), 752\u2013769 (2021)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"552_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"key":"552_CR24","doi-asserted-by":"crossref","unstructured":"Kawarabayashi, K., Kobayashi, Y.: An $${O}(\\log n)$$-approximation algorithm for the edge-disjoint paths problem in Eulerian planar graphs. ACM Trans. Algorithms 9(2), #\u00a016 (2013)","DOI":"10.1145\/2438645.2438648"},{"issue":"2","key":"552_CR25","doi-asserted-by":"publisher","first-page":"424","DOI":"10.1016\/j.jctb.2011.07.004","volume":"102","author":"K Kawarabayashi","year":"2012","unstructured":"Kawarabayashi, K., Kobayashi, Y., Reed, B.: The disjoint paths problem in quadratic time. J. Comb. Theory Ser. B 102(2), 424\u2013435 (2012)","journal-title":"J. Comb. Theory Ser. B"},{"key":"552_CR26","unstructured":"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 (Garching 2015). Leibniz Int. Proc. Inform., vol. 30, pp. 554\u2013567. Leibniz-Zent. Inform., Wadern (2015)"},{"key":"552_CR27","doi-asserted-by":"crossref","unstructured":"Klein, P., Plotkin, S.A., Rao, S.: Excluded minors, network decomposition, and multicommodity flow. In: 25th Annual ACM Symposium on Theory of Computing (San Diego 1993), pp. 682\u2013690. ACM, New York (1993)","DOI":"10.1145\/167088.167261"},{"key":"552_CR28","unstructured":"Korte, B., Lov\u00e1sz, L., Pr\u00f6mel, H.J., Schrijver, A. (eds.): Paths, Flows, and VLSI-Layout. Algorithms and Combinatorics, vol.\u00a09. Springer, Berlin (1990)"},{"key":"552_CR29","doi-asserted-by":"crossref","unstructured":"Lazarus, F., Rivaud, J.: On the homotopy test on surfaces. In: 53rd Annual Symposium on Foundations of Computer Science (New Brunswick 2012), pp. 440\u2013449. IEEE Computer Soc., Los Alamitos (2012)","DOI":"10.1109\/FOCS.2012.12"},{"key":"552_CR30","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10711-012-9827-9","volume":"168","author":"J Malestein","year":"2014","unstructured":"Malestein, J., Rivin, I., Theran, L.: Topological designs. Geom. Dedicata 168, 221\u2013233 (2014)","journal-title":"Geom. Dedicata"},{"issue":"1","key":"552_CR31","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/BF01202792","volume":"13","author":"M Middendorf","year":"1993","unstructured":"Middendorf, M., Pfeiffer, F.: On the complexity of the disjoint paths problem. Combinatorica 13(1), 97\u2013107 (1993)","journal-title":"Combinatorica"},{"key":"552_CR32","doi-asserted-by":"publisher","DOI":"10.56021\/9780801866890","volume-title":"Graphs on Surfaces","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces. Johns Hopkins Series in the Mathematical Sciences. Johns Hopkins University Press, Baltimore (2001)"},{"key":"552_CR33","doi-asserted-by":"crossref","unstructured":"Naves, G., Seb\u0151, A.: Multiflow feasibility: an annotated tableau. In: Research Trends in Combinatorial Optimization, pp. 261\u2013283. Springer, Berlin (2009)","DOI":"10.1007\/978-3-540-76796-1_12"},{"issue":"2","key":"552_CR34","doi-asserted-by":"publisher","first-page":"658","DOI":"10.1007\/s00039-015-0320-0","volume":"25","author":"P Przytycki","year":"2015","unstructured":"Przytycki, P.: Arcs intersecting at most once. Geom. Funct. Anal. 25(2), 658\u2013670 (2015)","journal-title":"Geom. Funct. Anal."},{"key":"552_CR35","doi-asserted-by":"crossref","unstructured":"Robertson, N., Sanders, D., Seymour, P., Thomas, R.: The four-colour theorem. J. Comb. Theory Ser. B 70(1), 2\u201344 (1997)","DOI":"10.1006\/jctb.1997.1750"},{"issue":"1","key":"552_CR36","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1006\/jctb.1995.1006","volume":"63","author":"N Robertson","year":"1995","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. XIII. The disjoint paths problem. J.\u00a0Comb. Theory Ser.\u00a0B 63(1), 65\u2013110 (1995)","journal-title":"J.\u00a0Comb. Theory Ser.\u00a0B"},{"key":"552_CR37","doi-asserted-by":"crossref","unstructured":"Schlomberg, N., Thiele, H., Vygen, J.: Packing cycles in planar and bounded-genus graphs. In: 34th Annual ACM-SIAM Symposium on Discrete Algorithms (Florence 2023), pp. 2069\u20132086. SIAM, Philadelphia (2023)","DOI":"10.1137\/1.9781611977554.ch79"},{"key":"552_CR38","volume-title":"Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics","author":"A Schrijver","year":"2003","unstructured":"Schrijver, A.: Combinatorial Optimization: Polyhedra and Efficiency. Algorithms and Combinatorics, vol. 24. Springer, Berlin (2003)"},{"issue":"2","key":"552_CR39","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1006\/jctb.1993.1062","volume":"59","author":"A Seb\u0151","year":"1993","unstructured":"Seb\u0151, A.: Integer plane multiflows with a fixed number of demands. J. Comb. Theory Ser. B 59(2), 163\u2013171 (1993)","journal-title":"J. Comb. Theory Ser. B"},{"issue":"1","key":"552_CR40","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1112\/plms\/s3-42.1.178","volume":"42","author":"PD Seymour","year":"1981","unstructured":"Seymour, P.D.: On odd cuts and plane multicommodity flows. Proc. Lond. Math. Soc. 42(1), 178\u2013192 (1981)","journal-title":"Proc. Lond. Math. Soc."},{"issue":"2","key":"552_CR41","doi-asserted-by":"publisher","first-page":"77","DOI":"10.1016\/0020-0190(93)90228-2","volume":"47","author":"\u00c9 Tardos","year":"1993","unstructured":"Tardos, \u00c9., 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\u201380 (1993)","journal-title":"Inf. Process. Lett."}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00552-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00454-023-00552-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-023-00552-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,25]],"date-time":"2023-11-25T23:04:21Z","timestamp":1700953461000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00454-023-00552-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,9]]},"references-count":41,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["552"],"URL":"https:\/\/doi.org\/10.1007\/s00454-023-00552-7","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2023,10,9]]},"assertion":[{"value":"31 May 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 August 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 October 2023","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}