Publication:5891121

DOI10.1007/978-3-642-31594-7_49zbMath1272.68158arXiv1202.5749OpenAlexW2065803871MaRDI QIDQ5891121

Magnus Wahlström, Stefan Kratsch, Michał Pilipczuk, Marcin Pilipczuk

Publication date: 12 August 2013

Published in: SIAM Journal on Discrete Mathematics, Automata, Languages, and Programming (Search for Journal in Brave)

Abstract: The MULTICUT problem, given a graph G, a set of terminal pairs T={(s_i,t_i) | 1 <= i <= r} and an integer p, asks whether one can find a cutset consisting of at most p non-terminal vertices that separates all the terminal pairs, i.e., after removing the cutset, t_i is not reachable from s_i for each 1 <= i <= r. The fixed-parameter tractability of MULTICUT in undirected graphs, parameterized by the size of the cutset only, has been recently proven by Marx and Razgon (STOC'11) and, independently, by Bousquet et al. (STOC'11), after resisting attacks as a long-standing open problem. In this paper we prove that MULTICUT is fixed-parameter tractable on directed acyclic graphs, when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains W[1]-hard.

Full work available at URL: https://arxiv.org/abs/1202.5749

zbMATH Keywords

directed acyclic graphfixed-parameter tractabilitymulticutshadow removalimportant separators

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonnumerical algorithms (68W05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40)

Related Items (25)

Adapting the directed grid theorem into an \textsf{FPT} algorithm ⋮ Parameterized complexity dichotomy for \textsc{Steiner Multicut} ⋮ Odd Multiway Cut in Directed Acyclic Graphs ⋮ What’s Next? Future Directions in Parameterized Complexity ⋮ Designing FPT Algorithms for Cut Problems Using Randomized Contractions ⋮ Clique Cover and Graph Separation ⋮ The complexity of multicut and mixed multicut problems in (di)graphs ⋮ Adapting the Directed Grid Theorem into an FPT Algorithm ⋮ Hitting Selected (Odd) Cycles ⋮ Parameterized complexity of weighted multicut in trees ⋮ Parameterized complexity of multicut in weighted trees ⋮ On the Parameterized Complexity of Counting Small-Sized Minimum \(\boldsymbol{(S,T)}\)-Cuts ⋮ A survey of parameterized algorithms and the complexity of edge modification ⋮ On Weighted Graph Separation Problems and Flow Augmentation ⋮ Multicut Is FPT ⋮ Parameterized complexity of critical node cuts ⋮ List H-coloring a graph by removing few vertices ⋮ Unnamed Item ⋮ NP-Hardness and Fixed-Parameter Tractability of Realizing Degree Sequences with Directed Acyclic Graphs ⋮ Feedback edge sets in temporal graphs ⋮ On the parameterized complexity of deletion to \(\mathcal{H}\)-free strong components ⋮ A relaxation of the directed disjoint paths problem: a global congestion metric helps ⋮ A Relaxation of the Directed Disjoint Paths Problem: A Global Congestion Metric Helps. ⋮ Fixed-Parameter Tractability of Multicut Parameterized by the Size of the Cutset ⋮ Acyclic Digraphs

This page was built for publication: Fixed-Parameter Tractability of Multicut in Directed Acyclic Graphs