Restricted Node Multicut Problem in Trees

Abstract

Abstract:

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

Key words: restricted node multicut, approximation algorithm, complementary slackness conditions

CLC Number:

O157.5

YANG Huijuan. Restricted Node Multicut Problem in Trees[J]. J4, 2014, 13(12): 21-25.

References

〔1〕拉文德拉K. 阿胡亚，托马斯L. 马南提，詹姆斯B. 沃琳，
等.网络流理论算法与应用〔M〕. 北京: 机械工业出版社，
2005:207-240.
〔2〕刘振宏，蔡茂诚. 组合最优化:计算机算法和复杂
性〔M〕. 北京: 清华大学出版社，1988:248-269.
〔3〕STEFAN K，MARCIN P，MICHAL P.Fixed-parameter trac?
tability of multicut in directed acyclic graphs〔J〕.Computer
Science，2012（7391）:581-593.
〔4〕JORGEN B J，ANDERS Y.The complexity of multicut and
mixed multicut problems in （di）graphs〔J〕. Theoretical
Computer Science，2014（520）:87-96.
〔5〕HU T C. Multicommodity network flows〔J〕.Oper Res，1963
（9）:898-900.
〔6〕DAHLHAUS E，JOHNSON D S，PAPADIMITRIOU C H，
et al. The complexity of multiterminal cuts〔J〕.SIAM J Com?
put，1994，23（4）:864-894.
〔7〕CHAWLA S，KRAUTHGAMER R，KUMAR R，et al. On
the hardness of approximating multicut and sparsestcut
〔J〕. Computational Complexity，2006，15（2）:94-114 .
〔8〕GARG N，VAZIRANI V，YANNAKAKIS M. Primal-dual
approximation algorithms for integral flow and multicut in
trees〔J〕.Algorithmica，1997（18）:3-20.
〔9〕Costa M C，Letocart L，Roupin F. A greedy algorithm for
multicut and integral multiflow in rooted trees〔J〕.Opera?
tions Research Letters，2003（31）: 21-27.
〔10〕CALINESCU G，FERNANDES C G，REED B. Multicuts
in unweighted graphs and digraphs with bounded degree
and bounded tree-width〔J〕. Journal of Algorithms，2003
（48）:333-359.
〔11〕GUO J，HUFFNER F，KENAR E，et al.Complexity and
exact algorithms for vertex multicut in interval and bound?
ed treewidth graphs〔J〕.European Journal of Operational
Research，2008（186）:542-553.
〔12〕CHARIS P.Restricted vertex multicut on permutation
graphs〔J〕.Discrete Applied Mathematics，2012（160）:
1791-1797.
〔13〕JULIAN M.Lagrangian relaxation and partial cover（ex?
tended abstract）〔J〕.Theoretical Aspects of Computer Sci?
ence，2008（25）:539-550.
〔14〕ZHANG P，ZHU D，LUAN J F.An approximation algo?
rithm for the Generalized k-Multicut problem〔J〕.Discrete
Applied Mathematics，2012（160）:1240-1247.