Simple and improved parameterized algorithms for multiterminal cuts. (English) Zbl 1213.68472
Summary: Given a graph \(G=(V,E)\) with \(n\) vertices and \(m\) edges, and a subset \(T\) of \(k\) vertices called terminals, the Edge (respectively, Vertex) Multiterminal Cut problem is to find a set of at most \(l\) edges (non-terminal vertices), whose removal from \(G\) separates each terminal from all the others. These two problems are NP-hard for \(k\geq 3\) but well-known to be polynomial-time solvable for \(k=2\) by the flow technique.
In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in \(O(2^{l } kT(n,m))\) time and Vertex Multiterminal Cut can be solved in \(O(k ^{l } T(n,m))\) time, where \(T(n,m)=O(\text{min} (n ^{2/3},m ^{1/2})m)\) is the running time of finding a minimum \((s,t)\) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of \(k\): Edge 3-Terminal Cut can be solved in \(O(1.415^{l } T(n,m))\) time, and Vertex \(\{3,4,5,6\}\)-Terminal Cuts can be solved in \(O(2.059^{l } T(n,m)), O(2.772^{l } T(n,m)), O(3.349^{l } T(n,m))\) and \(O(3.857^{l } T(n,m))\) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: \(O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))\)-time algorithm for Edge Multicut and \(O((2k)^{k+l/2} T(n,m))\)-time algorithm for Vertex Multicut.
In this paper, based on a notion farthest minimum isolating cut, we design several simple and improved algorithms for Multiterminal Cut. We show that Edge Multiterminal Cut can be solved in \(O(2^{l } kT(n,m))\) time and Vertex Multiterminal Cut can be solved in \(O(k ^{l } T(n,m))\) time, where \(T(n,m)=O(\text{min} (n ^{2/3},m ^{1/2})m)\) is the running time of finding a minimum \((s,t)\) cut in an unweighted graph. Furthermore, the running time bounds of our algorithms can be further reduced for small values of \(k\): Edge 3-Terminal Cut can be solved in \(O(1.415^{l } T(n,m))\) time, and Vertex \(\{3,4,5,6\}\)-Terminal Cuts can be solved in \(O(2.059^{l } T(n,m)), O(2.772^{l } T(n,m)), O(3.349^{l } T(n,m))\) and \(O(3.857^{l } T(n,m))\) time respectively. Our results on Multiterminal Cut can also be used to obtain faster algorithms for Multicut: \(O((\min(\sqrt{2k},l)+1)^{2k}2^{l}T(n,m))\)-time algorithm for Edge Multicut and \(O((2k)^{k+l/2} T(n,m))\)-time algorithm for Vertex Multicut.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68Q25 | Analysis of algorithms and problem complexity |
References:
| [1] | Xiao, M.: Algorithms for multiterminal cuts. In: Hirsch, E.A., Razborov, A.A., Semenov, A.L., Slissenko, A. (eds.) CSR. Lecture Notes in Computer Science, vol. 5010, pp. 314–325. Springer, Berlin (2008) · Zbl 1142.68462 |
| [2] | Dahlhaus, E., Johnson, D., Papadimitriou, C., Seymour, P., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23(4), 864–894 (1994). A preliminary version appeared in STOC 1992 · Zbl 0809.68075 · doi:10.1137/S0097539792225297 |
| [3] | Yeh, W.C.: A simple algorithm for the planar multiway cut problem. J. Algorithms 39(1), 68–77 (2001) · Zbl 0974.68235 · doi:10.1006/jagm.2000.1148 |
| [4] | Costa, M.C., Létocart, L., Roupin, F.: Minimal multicut and maximal integer multiflow: A survey. Eur. J. Oper. Res. 162(1), 55–69 (2005) · Zbl 1132.90306 · doi:10.1016/j.ejor.2003.10.037 |
| [5] | Călinescu, G., Karloff, H.J., Rabani, Y.: An improved approximation algorithm for multiway cut. J. Comput. Syst. Sci. 60(3), 564–574 (2000). A preliminary version appeared in STOC 1998 · Zbl 0986.90043 · doi:10.1006/jcss.1999.1687 |
| [6] | Karger, D.R., Klein, P.N., Stein, C., Thorup, M., Young, N.E.: Rounding algorithms for a geometric embedding relaxation of minimum multiway cut. In: Proceedings of the 31th Annual ACM Symposium on Theory of Computing (STOC 1999), pp. 668–678 (1999) · Zbl 1082.90149 |
| [7] | Garg, N., Vazirani, V.V., Yannakakis, M.: Multiway cuts in node weighted graphs. J. Algorithms 50(1), 49–61 (2004) · Zbl 1068.68178 · doi:10.1016/S0196-6774(03)00111-1 |
| [8] | Naor, J., Zosin, L.: A 2-approximation algorithm for the directed multiway cut problem. SIAM J. Comput. 31(2), 477–482 (2001). A preliminary version appeared in FOCS 1997 · Zbl 1052.68103 · doi:10.1137/S009753979732147X |
| [9] | Hartvigsen, D.: The planar multiterminal cut problem. Discrete Appl. Math. 85(3), 203–222 (1998) · Zbl 0908.90259 · doi:10.1016/S0166-218X(98)00036-5 |
| [10] | Chen, D.Z., Wu, X.: Efficient algorithms for k-terminal cuts on planar graphs. Algorithmica 38(2), 299–316 (2003) · Zbl 1072.68078 · doi:10.1007/s00453-003-1061-2 |
| [11] | Marx, D.: Parameterized graph separation problems. Theor. Comput. Sci. 351(3), 394–406 (2006). A preliminary version appeared in IWPEC 2004 · Zbl 1086.68104 · doi:10.1016/j.tcs.2005.10.007 |
| [12] | Chen, J., Liu, Y., Lu, S.: An improved parameterized algorithm for the minimum node multiway cut problem. In: Proceedings of the 10th International Workshop on Algorithms and Data Structures (WADS 2007), pp. 495–506. Algorithmica (2007, to appear) · Zbl 1209.68615 |
| [13] | Guillemot, S.: FPT algorithms for path-transversals and cycle-transversals problems in graphs. In: Grohe, M., Niedermeier, R. (eds.) IWPEC. Lecture Notes in Computer Science, vol. 5018, pp. 129–140. Springer, Berlin (2008) · Zbl 1142.68599 |
| [14] | Feige, U., Mahdian, M.: Finding small balanced separators. In: Proceedings of the 38th Annual ACM symposium on Theory of Computing (STOC 2006), pp. 375–384 (2006) · Zbl 1301.68159 |
| [15] | Downey, R., Fellows, M.: Parameterized Complexity. Springer, New York (1999) |
| [16] | Flum, J., Grohe, M.: Parameterized Complexity Theory. Springer, Berlin (2006) |
| [17] | Niedermeier, R.: Invitation to Fixed-Parameter Algorithms. Oxford University Press, Oxford (2006) · Zbl 1095.68038 |
| [18] | Călinescu, G., Fernandes, C.G., Reed, B.A.: Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J. Algorithms 48(2), 333–359 (2003) · Zbl 1079.68069 · doi:10.1016/S0196-6774(03)00073-7 |
| [19] | Guo, J., Huffner, F., Kenar, E., Niedermeier, R., Uhlmann, J.: Complexity and exact algorithms for vertex multicut in interval and bounded treewidth graphs. Eur. J. Oper. Res. 186(2), 542–553 (2008). A preliminary version appeared in SOFSEM 2006 · Zbl 1138.90345 · doi:10.1016/j.ejor.2007.02.014 |
| [20] | Ford, J., Fulkerson, D.: Flows in Networks. Princeton University Press, Princeton (1962) · Zbl 0106.34802 |
| [21] | Goldschmidt, O., Hochbaum, D.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24–37 (1994). A preliminary version appeared in FOCS 1988 · Zbl 0809.90125 · doi:10.1287/moor.19.1.24 |
| [22] | Xiao, M.: An improved divide-and-conquer algorithm for finding all minimum k-way cuts. In: Hong, S.H., Nagamochi, H., Fukunaga, T. (eds.) ISAAC. Lecture Notes in Computer Science, vol. 5369, pp. 208–219. Springer, Berlin (2008) · Zbl 1183.05086 |
| [23] | Goldberg, A.V., Rao, S.: Beyond the flow decomposition barrier. J. ACM 45(5), 783–797 (1998). A preliminary version appeared in FOCS 1997 · Zbl 1064.90567 · doi:10.1145/290179.290181 |
| [24] | Dinic, E.: Algorithm for solution of a problem of maximum flow in networks with power estimation. Sov. Math. Dokl. 11, 1277–1280 (1970) · Zbl 0219.90046 |
| [25] | Beigel, R., Eppstein, D.: 3-coloring in time O(1.3289 n ). J. Algorithms 54(2), 168–204 (2005) · Zbl 1101.68716 · doi:10.1016/j.jalgor.2004.06.008 |
| [26] | Hu, T.C.: Multi-commodity network flows. Oper. Res. 11(3), 344–360 (1963) · Zbl 0123.23704 · doi:10.1287/opre.11.3.344 |
| [27] | Itai, A.: Two-commodity flow. J. ACM 25(4), 596–611 (1978) · Zbl 0388.68054 · doi:10.1145/322092.322100 |
| [28] | 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) · Zbl 0844.68061 · doi:10.1137/S0097539793243016 |
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.
