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

2011/10/03 by Rajesh Chitnis, Chitnis, Rajesh, MohammadTaghi Hajiaghayi +3 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics #Computational Complexity (cs.CC) #Computer science #Data Structures and Algorithms (cs.DS) #Directed graph #Discrete mathematics #FOS: Computer and information sciences #Generalization #Graph #Kernelization #Mathematics #Maximum cut #Optimization and Packing Problems #Optimization and Search Problems #Parameterized complexity #Set (abstract data type) #Undirected graph #Vertex (graph theory) #cs.CC #cs.DS

paper · pdf · doi:10.48550/arxiv.1110.0259

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2011/10/03 · arxiv created 2013/04/25 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05

Abstract

Given a directed graph G, a set of k terminals and an integer p, the 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. 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 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 Directed Vertex Multiway Cut and 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 Directed Multicut is FPT for the case of k=2 terminal pairs, which answers another open problem raised in Marx and Razgon (STOC 2011).

Cited by

• Exploiting Low Scanwidth to Resolve Soft Polytomies
• Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
• All-Subsets Important Separators with Applications to Sample Sets, Balanced Separators and Vertex Sparsifiers in Directed Graphs

Related

• Fixed-parameter tractability of multicut in directed acyclic graphs
• Fixed-parameter tractability of multicut parameterized by the size of the cutset
• Directed multicut is W[1]-hard, even for four terminal pairs
• Directed Multicut with linearly ordered terminals
• Computing multiway cut within the given excess over the largest minimum isolating cut