完全图上无限制性K Node Multicut问题的近似算法

Approximation Algorithm for Unrestricted k Node Multicut Problem on Complete Graph

Node Multicut问题是图论与组合优化的经典问题,无限制性node Multicut问题是它的一类子问题.而无限制性K node multicut问题是无限制性node multicut问题的进一步推广形式.主要研究了完全图上的无限制性k Node Multicut问题.首先将部分点覆盖问题(PVC)多项式时间内归约到此问题证明该问题是NP难的,其次利用完全图独有的性质将该问题转换成特殊的部分击中集合问题(Special Partial Hitting Set Problem)并运用递归的思想和局部比率定理设计了求解该问题的2近似算法.

The Node multicut problem is a classic problem of graph theory and combinatorial optimization.The unrestricted k Node multicut problem is a further extension of the unrestricted k Node multicut problem.This paper mainly studies the unrestricted k node multicut problem on complete graphs.Firstly,Partial vertex cover problem is reduced to this problem in polynomial time to prove that the problem is N P hard.Secondly,the problem is transformed into a special partial hit set problem by using the unique property of complete graph.Then,a 2-approximation algorithm is designed to solve the problem by using the recursive idea and the local ratio theorem.