An Approximation Algorithm for the B-prize-collecting Multicut Problem in Trees

In this paper, we consider the B-prize-collecting multicut problem in trees. In this problem, we are given a tree $$T=(V,E)$$ , a set of k source-sink pairs $$\mathcal {P}=\{(s_1,t_1),(s_2,t_2),\ldots , (s_k,t_k)\}$$ and a profit bound B. Every edge $$e\in E$$ has a cost $$c_e$$ , and every source-sink pair $$(s_j,t_j)\in \mathcal {P}$$ has a profit $$p_j$$ and a penalty $$\pi _j$$ . This problem is to find a multicut $$M\subseteq E$$ such that the total cost, which consists of the total cost of the edges in M and the total penalty of the pairs still connected after removing M, is minimized and the total profit of the disconnected pairs by removing M is at least B. Based on the primal-dual scheme, we present an $$(\frac{8}{3}+ \epsilon )$$ -approximation algorithm by carefully increasing the penalty, where $$\epsilon $$ is any fixed positive number.