Improved Parameterized Algorithm for the Multicut Problem
Multicut问题参数算法的改进

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* 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*.