On the parameterized complexity of separating certain sources from the target

DOI10.1016/j.tcs.2019.06.011zbMath1431.68051OpenAlexW2953744542WikidataQ127575551 ScholiaQ127575551MaRDI QIDQ2330108

Joanna Tomasik, Arpad Rimmel, Pierre Bergé

Publication date: 18 October 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2019.06.011

zbMATH Keywords

fixed-parameter tractabilitymulticutW[1-hardness]

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parameterized graph separation problems
• Partial multicuts in trees
• Computing small partial coverings
• An improved parameterized algorithm for the minimum node multiway cut problem
• On the Parameterized Complexity of Cutting a Few Vertices from a Graph
• Maximal Flow Through a Network
• Approximating the k-multicut problem
• The Complexity of Multiterminal Cuts
• Directed multicut is W[1-hard, even for four terminal pairs]
• Multiway cuts in node weighted graphs
• Multicut is FPT
• Fixed-parameter tractability of multicut parameterized by the size of the cutset