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

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

• approximation algorithm
• complexity
• np-hard problems
• directed multi-multiway cut
• directed multicut cut