Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

Details Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset

2011-10-03

arxiv.org/abs/1110.0259v1

Computer Science

Data Structures and Algorithms

To appear in SODA 2012

Scientific paper

Given a directed graph $G$, a set of $k$ terminals and an integer $p$, the \textsc{Directed Vertex Multiway Cut} problem asks if there is a set $S$ of at most $p$ (nonterminal) vertices whose removal disconnects each terminal from all other terminals. \textsc{Directed Edge Multiway Cut} is the analogous problem where $S$ is a set of at most $p$ edges. These two problems indeed are known to be equivalent. A natural generalization of the multiway cut is the \emph{multicut} problem, in which we want to disconnect only a set of $k$ given pairs instead of all pairs. Marx (Theor. Comp. Sci. 2006) showed that in undirected graphs multiway cut is fixed-parameter tractable (FPT) parameterized by $p$. Marx and Razgon (STOC 2011) showed that undirected multicut is FPT and directed multicut is W[1]-hard parameterized by $p$. We complete the picture here by our main result which is that both \textsc{Directed Vertex Multiway Cut} and \textsc{Directed Edge Multiway Cut} can be solved in time $2^{2^{O(p)}}n^{O(1)}$, i.e., FPT parameterized by size $p$ of the cutset of the solution. This answers an open question raised by Marx (Theor. Comp. Sci. 2006) and Marx and Razgon (STOC 2011). It follows from our result that \textsc{Directed Multicut} is FPT for the case of $k=2$ terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

Affiliated with

Also associated with

No associations

Rating

Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-270438