Approximation algorithms for multi-multiway cut and multicut problems on directed graphs

Document Type : Original Article

Authors

Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran

Abstract

In this paper, we study the directed multicut and directed multimultiway cut problems. The input to the directed multi-multiway cut problem is a weighted directed graph $G=(V,E)$ and $k$ sets $S_1, S_2,\cdots, S_k$ of vertices. The goal is to find a subset of edges of minimum total weight whose removal will disconnect all the connections between the vertices in each set $S_i$, for $1\leq i\leq k$. A special case of this problem is the directed multicut problem whose input consists of a weighted directed graph $G=(V,E)$ and a set of ordered pairs of vertices $(s_1,t_1),\cdots,(s_k,t_k)$. The goal is to find a subset of edges of minimum total weight whose removal will make for any $i, 1\leq i\leq k$, there is no directed path from si to ti . In this paper, we present two approximation algorithms for these problems. The so called region growing paradigm is modified and used for these two cut problems on directed graphs. using this paradigm, we give an approximation algorithm for each problem such that both algorithms have the approximation factor of $O(k)$ the same as the previous works done on these problems. However, the previous works need to solve $k$ linear programming, whereas our algorithms require only one linear programming. Therefore, our algorithms improve the running time of the previous algorithms.

Keywords

Main Subjects

References

[1] E. Dahlhaus, D. S. Johnson, C. H. Papadimitriou, P. D. Seymour, M. Yannakakis, The complexity of multiway cuts, In Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, (1992) 241-251.
[2] G. C˘alinescu, H. Karloff, Y. Rabani, An improved approximation algorithm for multiway cut, In Proceedings of the thirtieth annual ACM symposium on Theory of computing, (1998) pages 48-52.
[3] D. R. Karger, P. Klein, C. Stein, M. Thorup, N. E. Young, Rounding algorithms for a geometric embedding of minimum multiway cut, Mathematics of Operations Research, 29(3) (2004) 436-461.
[4] N. Garg, V. V. Vazirani, M. Yannakakis, Multiway cuts in directed and node weighted graphs, In International Colloquium on Automata, Languages, and Programming, 487-498, Springer, 1994.
[5] J. Naor, L. Zosin, A 2-approximation algorithm for the directed multiway cut problem, SIAM Journal on Computing, 31(2) (2001) 477-482.
[6] N. Garg, V. V. Vazirani, M. Yannakakis, Approximate max-flow min-(multi) cut theorems and their applica[1]tions, SIAM Journal on Computing, 25(2) (1996) 235-251.
[7] J. Chuzhoy, Y. Makarychev, A. Vijayaraghavan, Y. Zhou, Approximation algorithms and hardness of the k-route cut problem, ACM Transactions on Algorithms (TALG), 12(1) (2015) 1-40.
[8] J. Bang-Jensen, A. Yeo, The complexity of multicut and mixed multicut problems in (di) graphs, Theoretical Computer Science, 520 (2014) 87-96.
[9] G. Even, J. S. Naor, S. Rao, B. Schieber, Divide-and-conquer approximation algorithms via spreading metrics, Journal of the ACM (JACM), 47(4) (2000) 585-616.
[10] T. Leighton, S. Rao, An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms, Technical report, MASSACHUSETTS INST OF TECH CAMBRIDGE MICROSYSTEMS RESEARCH CENTER, 1989.
[11] G. Even, J. S. Naor, B. Schieber, M. Sudan, Approximating minimum feedback sets and multicuts in directed graphs, Algorithmica, 20(2) (198) 151-174.
[12] P. N. Klein, S. A. Plotkin, S. Rao, E. Tardos, Approximation algorithms for steiner and directed multicuts, Journal of Algorithms, 22(2) (1997) 241-269.
[13] J. Cheriyan, H. Karloff, Y. Rabani, Approximating directed multicuts, Combinatorica, 25(3) (2005) 251-269.
[14] A. Agarwal, N. Alon, M. S. Charikar, Improved approximation for directed cut problems, In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, (2007) 671-680.
[15] M. Saks, A. Samorodnitsky, L. Zosin, A lower bound on the integrality gap for minimum multicut in directed networks, Combinatorica, 24(3) (2004) 525-530.
[16] A. Avidor, M. Langberg, The multi-multiway cut problem, Theoretical Computer Science, 377(1-3) (2007) 35-42.
[17] I. Kanj, G. Lin, T. Liu, W. Tong, G. Xia, J. Xu, B. Yang, F. Zhang, P. Zhang, B. Zhu, Improved parameterized and exact algorithms for cut problems on trees, Theoretical Computer Science, 607 (2015) 455-470.
[18] P. Zhang, D. Zhu, J. Luan, An approximation algorithm for the generalized k-multicut problem, Discrete Applied Mathematics, 160(7-8) (2012) 1240-1247.
[19] M. Gr¨otschel, L. Lov´asz, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization, Combinatorica, 1(2) (1981) 169-197.
AUT Journal of Mathematics and Computing
Volume 1, Issue 2
September 2020
Pages 145-152

Files

Share

How to cite

Statistics