Parameterized complexity dichotomy for Steiner Multicut
作者：
Highlights：
• Steiner multicut seeks k elements to disconnect a pair from each of t terminal sets.
• Parameterized complexity dichotomy for k, t, treewidth and size p of terminal sets.
• Edge Steiner multicut is FPT for parameter k+t but node versions are W[1]-hard.
• Edge Steiner multicut is W[1]-hard for parameter k, treewidth 2, and p=3.
• The results also imply a dichotomy on the classical complexity.
摘要
•Steiner multicut seeks k elements to disconnect a pair from each of t terminal sets.•Parameterized complexity dichotomy for k, t, treewidth and size p of terminal sets.•Edge Steiner multicut is FPT for parameter k+t but node versions are W[1]-hard.•Edge Steiner multicut is W[1]-hard for parameter k, treewidth 2, and p=3.•The results also imply a dichotomy on the classical complexity.
论文关键词：Cut problems,Steiner multicut,Parameterized complexity,Kernelization
论文评审过程：Received 30 March 2015, Revised 7 December 2015, Accepted 9 March 2016, Available online 21 April 2016, Version of Record 10 June 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.03.003
