Parameterized algorithms for min-max multiway cut and list digraph homomorphism
作者：
Highlights：
• We design FPT-algorithms for the following two parameterized problems:
• List Digraph Homomorphism, which is a “list” version of the classical Digraph Homomorphism problem.
• Min-Max Multiway Cut, which is a variant of Multiway Cut.
• We introduce a general problem, List Allocation, and we present parameterized reductions of both aforementioned problems to it.
• We provide an FPT-algorithm for the List Allocation adapting of the randomized contractions technique introduced by Chitnis et al. (2012).
摘要
•We design FPT-algorithms for the following two parameterized problems:•List Digraph Homomorphism, which is a “list” version of the classical Digraph Homomorphism problem.•Min-Max Multiway Cut, which is a variant of Multiway Cut.•We introduce a general problem, List Allocation, and we present parameterized reductions of both aforementioned problems to it.•We provide an FPT-algorithm for the List Allocation adapting of the randomized contractions technique introduced by Chitnis et al. (2012).
论文关键词：Parameterized complexity,Fixed-Parameter Tractable algorithm,Multiway Cut,Digraph homomorphism
论文评审过程：Received 17 March 2016, Revised 16 December 2016, Accepted 6 January 2017, Available online 23 January 2017, Version of Record 27 February 2017.
论文官网地址：https://doi.org/10.1016/j.jcss.2017.01.003
