A shifting algorithm for constrained min-max partition on trees

Let T = (V,E) be a rooted tree with n edges. We associate nonnegative weight w(v) and size s(v) with each vertex v in V. A q-partition of T into q connected components T₁,T₂,...,T_q is obtained by deleting k = q-1 edges of T, 1 ≤ k < n. The weight W(T_i) (or size S(T_i)) of component T_i is then the sum o weights (sizes) of the vertices of T_i. The height h(T) is the maximum number of edges of paths having one end at the root. If P is a partition with components T₁...,T_q let W_P = max_{1 ≤ i ≤ q} W(T_i). The following two problems are considered: 1. Size-constrained min-max problem: Find a q-partition of T for which W_P is a minimum over all partitions P satisfying S(T_i) ≤ M (M > 0). 2. Height-constrained min-max problem: Find a q-partition of T for which W_P is a minimum over all partitions P satisfying height h(T_i) ≤ H (H is a positive integer). The first problem is shown to be NP-complete, while a polynomial algorithm is presented for the second problem.