Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2010-019 (December 16, 2010)

FPTAS's for Trimming Weighted Trees
by Mingyu Xiao, Takuro Fukunaga, Hiroshi Nagamochi

pdf File

Given a tree with nonnegative edge cost and nonnegative vertex weight, and a number $k\geq0$, we consider the following four cut problems: cutting vertices of weight at most or at least $k$ from the tree by deleting some edges such that the remaining part of the graph is still a tree and the total cost of the edges being deleted is minimized or maximized. The {\rm MinMstCut} problem (cut vertices of weight \emph{at most} $k$ and \emph{minimize} the total cost of the edges being deleted) can be solved in linear time and space and the other three problems are NP-hard. In this paper, we design an $O(nl/\varepsilon)$-time $O(l^2/\varepsilon+n)$-space algorithm for {\rm MaxMstCut}, and $O(nl(1/\varepsilon+\log n))$-time $O(l^2/\varepsilon+n)$-space algorithms for the other two problems, {MinLstCut} and {\rm MaxLstCut}, where $n$ is the number of vertices in the tree, $l$ the number of leaves, and $\varepsilon>0$ the prescribed error bound.