Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the CutsetReport as inadecuate



 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 - Download this document for free, or read online. Document in PDF available to download.

Download or read this book online for free in PDF: Fixed-Parameter Tractability of Directed Multiway Cut Parameterized by the Size of the Cutset
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 W1-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).



Author: Rajesh Chitnis; MohammadTaghi Hajiaghayi; Dániel Marx

Source: https://archive.org/







Related documents