树上的限制性node multicut问题

Restricted Node Multicut Problem in Trees

割集问题在图论和组合优化中占有重要地位,限制性node multicut问题是割集问题的一类比较重要的推广问题。树上的限制性node multicut问题是值得研究的一个问题。首先说明此问题是NP难的,其次用线性规划理论中的互补松弛条件设计了一个近似值2且时间复杂度为O(max{kn,n log n})的算法。并进一步说明了通过算法得到的解具有半整数的性质。

The problem of cut set holds an important position in graph theory and combinatorial optimization and restricted node multicut is a significant problem in cut set. And restricted node multicut problem in trees is worth studying. The paper first explains that the node multicut problem is hard, then designs an algorithm with the approximate value of 2 and time complexity of by applying complementary slackness conditions in linear programming theory, and finally further explains the solution from the algorithm is a half-integer.