PRIMAL-DUAL APPROXIMATION ALGORITHMS FOR INTEGRAL FLOW AND MULTICUT IN TREES

We study the maximum integral multicommodity flow problem and the mini mum multicut problem restricted to trees. This restriction is quite ri ch and contains as special cases classical optimization problems such as matching and vertex cover for general graphs. It is shown that both the maximum integral multicommodity flow and the minimum multicut pro blem are NP-hard and MAX SNP-hard on trees, although the maximum integ ral flow can be computed in polynomial time if the edges have unit cap acity. We present an efficient algorithm that computes a multicut and integral flow such that the weight of the multicut is at most twice th e value of the flow. This gives a 2-approximation algorithm for minimu m multicut and a 1/2-approximation algorithm for maximum integral mult icommodity how in trees.