Amirkabir University of TechnologyAUT Journal of Mathematics and Computing1220201001Approximation algorithms for multi-multiway cut and multicut problems on directed graphs145152381010.22060/ajmc.2018.15109.1014ENRaminYarinezhadDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, Iran0000-0003-1895-4833Seyed NaserHashemiDepartment of Mathematics and Computer Science, Amirkabir University of Technology, Tehran, IranJournal Article20181008In this paper, we study the directed multicut and directed multi-multiway 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,...,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),...,(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 $s_i$ to $t_i$.<br />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. <br />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_5e4da5297ba5154b4c1b08186e4dbb8e.pdf