Minmax subtree cover problem on cacti

Let G=(V,E)G=(V,E) be a connected graph such that edges and vertices are weighted by nonnegative reals. Let p   be a positive integer. The minmax subtree cover problem (MSC) asks to find a pair (X,T)(X,T) of a partition X={X1,X2,…,Xp}X={X1,X2,…,Xp} of V   and a set TT of p   subtrees T1,T2,…,TpT1,T2,…,Tp, each TiTi containing XiXi so as to minimize the maximum cost of the subtrees, where the cost of TiTi is defined to be the sum of the weights of edges in TiTi and the weights of vertices in XiXi. In this paper, we propose an O(p2n)O(p2n) time (4-4/(p+1))(4-4/(p+1))-approximation algorithm for the MSC when G is a cactus.