Amirkabir University of Technology AUT Journal of Mathematics and Computing 2783-2449 1 2 2020 09 01 Approximation algorithms for multi-multiway cut and multicut problems on directed graphs 145 152 3810 10.22060/ajmc.2018.15109.1014 EN Ramin Yarinezhad Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran 0000-0003-1895-4833 Seyed Naser Hashemi Department of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran Journal Article 2018 10 08 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. https://ajmc.aut.ac.ir/article_3810_02ae6a786bbf135d3d223cbc0e770b6e.pdf