Multicut问题参数算法的改进

Improved Parameterized Algorithm for the Multicut Problem

Multicut问题即在一个图上删除最少个数的顶点,使得预先给定的一组顶点对均不连通.该问题是NP难的.在深入分析问题结构特点的基础上,运用集合划分策略和相关问题的最新研究结果,对它提出了一种时间复杂度为O*(︱(2l)～(1/2)︱^(2l)4~k)的参数化算法,其中,l为给定的顶点对数目,k为需删除的顶点个数.该算法明显改进了当前时间复杂度为O*(2klkk4k3)的最好算法.

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^＊（┌√21^┐214^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^klk^k4^k^3）.