- 作者：Karl Bringmanna ; 1 ; karlb@inf.ethz.ch" class="auth_mail" title="E-mail the corresponding author ; Danny Hermelinb ; 2 ; hermelin@bgu.ac.il" class="auth_mail" title="E-mail the corresponding author ; Matthias Mnichc ; 3 ; mmnich@uni-bonn.de" class="auth_mail" title="E-mail the corresponding author ; Erik Jan van Leeuwend ; erikjan@mpi-inf.mpg.de" class="auth_mail" title="E-mail the corresponding author
- 关键词：Cut problems ; Steiner multicut ; Parameterized complexity ; Kernelization
- 刊名：Journal of Computer and System Sciences
- 出版年：2016
- 出版时间：September 2016
- 年：2016
- 卷：82
- 期：6
- 页码：1020-1043
- 全文大小：867 K
- •
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 16000283&_mathId=si33.gif&_user=111111111&_pii=S0022000016000283&_rdoc=1&_issn=00220000&md5=07cfa220cc9f26892b3c9579769d1b05" title="Click to view the MathML source">k+t but node versions are 16000283&_mathId=si34.gif&_user=111111111&_pii=S0022000016000283&_rdoc=1&_issn=00220000&md5=750a99a05e3bab24072b3f2b5650a304" title="Click to view the MathML source">W[1]-hard.
- •
Edge Steiner multicut is 16000283&_mathId=si34.gif&_user=111111111&_pii=S0022000016000283&_rdoc=1&_issn=00220000&md5=750a99a05e3bab24072b3f2b5650a304" title="Click to view the MathML source">W[1]-hard for parameter k , treewidth 2, and 16000283&_mathId=si10.gif&_user=111111111&_pii=S0022000016000283&_rdoc=1&_issn=00220000&md5=3ea7d10380e982b51e2283bfe070323d" title="Click to view the MathML source">p=3.
- •
The results also imply a dichotomy on the classical complexity.