Improved Parameterized Algorithm for the Multicut Problem
Yun Liu · 2010
The Multicut problem is for a given graph and a given collection of terminal pairs to find a vertex set of minimum size such that the two terminals in any pair are not connected after deletion of this vertex set.This problem is NP-hard.Based on the deep analysis of its structural characteristics,employing the strategy of set partition and the improved results of another related problem,this paper proposes a parameterized algorithm of running time O*(︱(2l)～(1/2)︱~(2l)4~k) for the problem,in which l denotes the number of terminal pairs and k denotes the number of removed vertices.This algorithm significantly improves the previous one of running time O*(2 kl kk 4k3).