×

A near-linear approximation scheme for multicuts of embedded graphs with a fixed number of terminals. (English) Zbl 1458.05244

Summary: For an undirected edge-weighted graph \(G\) and a set \(R\) of pairs of vertices called pairs of terminals, a multicut is a set of edges such that removing these edges from \(G\) disconnects each pair in \(R\). We provide an algorithm computing a \((1+\varepsilon)\)-approximation of the minimum multicut of a graph \(G\) in time \((g+t)^{(O(g+t)^3)}\cdot(1/\varepsilon)^{O(g+t)} \cdot n \log n\), where \(g\) is the genus of \(G\) and \(t\) is the number of terminals. This is tight in several aspects, as the minimum multicut problem is both APX-hard and W[1]-hard (parameterized by the number of terminals), even on planar graphs (equivalently, when \(g=0)\). Our result, in the field of fixed-parameter approximation algorithms, mostly relies on concepts borrowed from computational topology of graphs on surfaces. In particular, we use and extend various recent techniques concerning homotopy, homology, and covering spaces. Interestingly, such topological techniques seem necessary even for the planar case. We also exploit classical ideas stemming from approximation schemes for planar graphs and low-dimensional geometric inputs. A key insight toward our result is a novel characterization of a minimum multicut as the union of some Steiner trees in the universal cover of the surface in which \(G\) is embedded.

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
05C10 Planar graphs; geometric and topological aspects of graph theory
57M15 Relations of low-dimensional topology with graph theory
68Q25 Analysis of algorithms and problem complexity
68W05 Nonnumerical algorithms
68W25 Approximation algorithms
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar, Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs, SIAM J. Comput., 48 (2019), pp. 1120-1145. · Zbl 1432.05077
[2] S. Arora, Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems, J. ACM, 45 (1998), pp. 753-782. · Zbl 1064.90566
[3] M. Bateni, M. Hajiaghayi, P. N. Klein, and C. Mathieu, A polynomial-time approximation scheme for planar multiway cut, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2012, pp. 639-655. · Zbl 1422.68294
[4] M. Bateni, M. Hajiaghayi, and D. Marx, Approximation schemes for Steiner forest on planar graphs and graphs of bounded treewidth, J. ACM, 58 (2011), 21. · Zbl 1281.68233
[5] G. Borradaile, E. D. Demaine, and S. Tazari, Polynomial-time approximation schemes for subset-connectivity problems in bounded-genus graphs, in Proceedings of the 26th Annual Symposium on Theoretical Aspects of Computer Science (STACS), 2009, pp. 171-182. · Zbl 1236.68010
[6] G. Borradaile, D. Eppstein, A. Nayyeri, and C. Wulff-Nilsen, All-pairs minimum cuts in near-linear time for surface-embedded graphs, in Proceedings of the 32nd International Symposium on Computational Geometry (SoCG 2016), S. Fekete and A. Lubiw, eds., Dagstuhl, Germany, 2016. · Zbl 1387.05054
[7] G. Borradaile, P. Klein, and C. Mathieu, An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs, ACM Trans. Algorithms (TALG), 5 (2009), 31. · Zbl 1300.05294
[8] G. Borradaile and Ph. Klein, An \({O}(n\log n)\) algorithm for maximum \(st\)-flow in a directed planar graph, J. ACM, 56 (2009). · Zbl 1325.05161
[9] N. Bousquet, J. Daligault, and S. Thomassé, Multicut is FPT, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing, ACM, New York, 2011, pp. 459-468. · Zbl 1288.05264
[10] E. Chambers, J. Erickson, and A. Nayyeri, Minimum cuts and shortest homologous cycles, in Proceedings of the 25th Annual Symposium on Computational Geometry (SOCG), ACM, 2009, pp. 377-385. · Zbl 1388.05177
[11] E. W. Chambers, É. Colin de Verdière, J. Erickson, F. Lazarus, and K. Whittlesey, Splitting (complicated) surfaces is hard, Comput. Geom., 41 (2008), pp. 94-110. · Zbl 1152.65026
[12] E. W. Chambers, J. Erickson, and A. Nayyeri, Homology flows, cohomology cuts, SIAM J. Comput., 41 (2012), pp. 1605-1634. · Zbl 1260.05070
[13] S. Chawla, R. Krauthgamer, R. Kumar, Y. Rabani, and D. Sivakumar, On the hardness of approximating multicut and sparsest-cut, Comput. Complexity, 15 (2006), pp. 94-114. · Zbl 1132.68418
[14] C. Chekuri and V. Madan, Approximating multicut and the demand graph, in Proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms, P. N. Klein, ed., 2017, pp. 855-874. · Zbl 1410.90232
[15] É. Colin de Verdière, Shortest cut graph of a surface with prescribed vertex set, in Proceedings of the 18th European Symposium on Algorithms (ESA), Part 2, Lecture Notes in Comput. Sci. 6347, 2010, pp. 100-111. · Zbl 1287.05154
[16] É. Colin de Verdière, Multicuts in planar and bounded-genus graphs with bounded number of terminals, Algorithmica, 78 (2017), pp. 1206-1224. · Zbl 1371.05285
[17] É. Colin de Verdière, Computational topology of graphs on surfaces, 3rd ed., in Handbook of Discrete and Computational Geometry, J. E. Goodman, J. O’Rourke, and C. Toth, eds., CRC Press, Boca Raton, FL, 2018, ch. 23, pp. 605-636.
[18] É. Colin de Verdière and J. Erickson, Tightening nonsimple paths and cycles on surfaces, SIAM J. Comput., 39 (2010), pp. 3784-3813. · Zbl 1216.05156
[19] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, and M. Yannakakis, The complexity of multiterminal cuts, SIAM J. Comput., 23 (1994), pp. 864-894. · Zbl 0809.68075
[20] M. de Graaf and A. Schrijver, Making curves minimally crossing by Reidemeister moves, J. Combin. Theory Ser. B, 70 (1997), pp. 134-156. · Zbl 0888.57001
[21] S. E. Dreyfus and R. A. Wagner, The Steiner problem in graphs, Networks, 1 (1971), pp. 195-207. · Zbl 0229.05125
[22] D. B. A. Epstein, Curves on 2-manifolds and isotopies, Acta Math., 115 (1966), pp. 83-107. · Zbl 0136.44605
[23] J. Erickson, Maximum flows and parametric shortest paths in planar graphs, in Proceedings of the 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2010, pp. 794-804. · Zbl 1288.05055
[24] J. Erickson, K. Fox, and A. Nayyeri, Global minimum cuts in surface embedded graphs, in Proceedings of the 23rd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2012, pp. 1309-1318. · Zbl 1423.05168
[25] J. Erickson and S. Har-Peled, Optimally cutting a surface into a disk, Discrete Comput. Geom., 31 (2004), pp. 37-59. · Zbl 1060.68129
[26] J. Erickson and A. Nayyeri, Minimum cuts and shortest non-separating cycles via homology covers, in Proceedings of the 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2011, pp. 1166-1176. · Zbl 1376.05146
[27] R. E. Erickson, C. L. Monma, and A. F. Veinott, Jr., Send-and-split method for minimum-concave-cost network flows, Math. Oper. Res., 12 (1987), pp. 634-664. · Zbl 0667.90036
[28] J. Fakcharoenphol and K. Talwar, An improved decomposition theorem for graphs excluding a fixed minor, in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, Springer, New York, 2003, pp. 36-46. · Zbl 1279.05053
[29] N. Garg, V. V. Vazirani, and M. Yannakakis, Approximate max-flow min-(multi) cut theorems and their applications, SIAM J. Comput., 25 (1996), pp. 235-251. · Zbl 0844.68061
[30] N. Garg, V. V. Vazirani, and M. Yannakakis, Primal-dual approximation algorithms for integral flow and multicut in trees, Algorithmica, 18 (1997), pp. 3-20. · Zbl 0873.68075
[31] J. Hass and P. Scott, Intersections of curves on surfaces, Israel J. Math., 51 (1985), pp. 90-120. · Zbl 0576.57009
[32] R. Hassin, Maximum flow in \((s,t)\)-planar networks, Inform. Process. Lett., 13 (1981).
[33] R. Hassin and D. B. Johnson, An \({O}(n\log^2n)\) algorithm for maximum flow in undirected planar networks, SIAM J. Comput., 14 (1985), pp. 612-624. · Zbl 0565.90018
[34] A. Hatcher, Algebraic Topology, Cambridge University Press, Cambridge, 2002; also available online from http://www.math.cornell.edu/ hatcher/. · Zbl 1044.55001
[35] M. R. Henzinger, Ph. Klein, S. Rao, and S. Subramanian, Faster shortest-path algorithms for planar graphs, J. Comput. System Sci., 55 (1997), pp. 3-23. · Zbl 0880.68099
[36] T. C. Hu, Multi-commodity network flows, Oper. Res., 11 (1963), pp. 344-360. · Zbl 0123.23704
[37] G. F. Italiano, Y. Nussbaum, P. Sankowski, and Ch. Wulff-Nilsen, Improved algorithms for Min Cut and Max Flow in undirected planar graphs, in Proceedings of the 43rd Annual ACM Symposium on Theory of Computing (STOC), 2011, pp. 313-322. · Zbl 1288.05276
[38] M. Juvan, A. Malnic̆, and B. Mohar, Systems of curves on surfaces, J. Combin. Theory Ser. B, 68 (1996), pp. 7-22. · Zbl 0859.57014
[39] K.-i. Kawarabayashi, B. Mohar, and B. Reed, A simpler linear time algorithm for embedding graphs into an arbitrary surface and the genus of graphs of bounded tree-width, in Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2008, pp. 771-780.
[40] S. Khuller and J. S. Naor, Flow in planar graphs: A survey of recent results, in Planar Graphs, W. T. Trotter, ed., DIMACS Ser. Discrete Math. Theoret. Comput. Sci., AMS, Providence, RI, 1993, pp. 59-84. · Zbl 0801.68121
[41] P. Klein, S. A. Plotkin, and S. Rao, Excluded minors, network decomposition, and multicommodity flow, in Proceedings of the 25th Annual ACM Symposium on Theory of Computing, ACM, New York, 1993, pp. 682-690. · Zbl 1310.90017
[42] P. N. Klein and D. Marx, Solving planar \(k\)-terminal cut in \({O}(n^{c\sqrt{k}})\) time, in Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP), 2012, pp. 569-580. · Zbl 1272.68157
[43] Ph. N. Klein, Multiple-source shortest paths in planar graphs, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2005, pp. 146-155. · Zbl 1297.05059
[44] D. Marx, Parameterized complexity and approximation algorithms, Comput. J., 51 (2008), pp. 60-78.
[45] D. Marx, A tight lower bound for planar multiway cut with fixed number of terminals, in Proceedings of the International Colloquium on Automata, Languages, and Programming, Springer, New York, 2012, pp. 677-688. · Zbl 1272.68147
[46] D. Marx and I. Razgon, Fixed-parameter tractability of multicut parameterized by the size of the cutset, SIAM J. Comput., 43 (2014), pp. 355-388. · Zbl 1304.68078
[47] J. S. B. Mitchell, Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric TSP, \(k\)-MST, and related problems, SIAM J. Comput., 28 (1999), pp. 1298-1309. · Zbl 0940.68062
[48] J. H. Reif, Minimum \(s-t\) cut of a planar undirected network in \(O(n\log^2(n))\) time, SIAM J. Comput., 12 (1983), pp. 71-81. · Zbl 0501.68031
[49] A. Schrijver, On the history of combinatorial optimization (till \(1960)\), Handb. Oper. Res. Manag. Sci., 12 (2005), pp. 1-68. · Zbl 1278.90006
[50] J. Stillwell, Classical Topology and Combinatorial Group Theory, 2nd ed., Springer, New York, 1993. · Zbl 0774.57002
[51] J. Vygen, Faster algorithm for optimum Steiner trees, Inform. Process. Lett., 111 (2011), pp. 1075-1079. · Zbl 1260.68305
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.