树上推广的Multicut问题的近似算法

摘要

给定边上有费用的树T,终端集合族X={S1,S2,…,Sl},推广的Multicut问题询问费用最小边集,使得在树上删除边集中的边能够断开每一个终端集,推广的Multicut问题有其独立的研究意义因为该问题分别是经典的Multicut问题和Multiway Cut问题的自然推广,同时也是推广的SteinForest问题的对偶问题,树上推广的Multicut问题的完全版本可以归约到树上经典的Multicut问题似求解,对于该问题的Prize-collecting版本,给出了原始-对偶的3倍近似算法,对于该问题的k版本通过非一致的途径给出了近似比为min{2(l-k+1),k}的近似算法,以及找到了该问题的k版本与k-稠密子图问题之间的一个有趣的联系,从而证明了将k版本的树上推广的Multicut问题近似O(n1/6-g)以内是困难的(对某个小的常数ε>0).