OPTIMIZING CONSTRAINED SUBTREES OF TREES

Given a tree G = (V, E) and a weight function defined on subsets of it s nodes, we consider two associated problems. The first, called the '' rooted subtree problem'', is to find a maximum weight subtree, with a specified root, from a given set of subtrees. The second problem, call ed ''the subtree packing problem'', is to find a maximum weight packin g of node disjoint subtrees chosen from a given set of subtrees, where the value of each subtree may depend on its root. We show that the co mplexity status of both problems is related, and that the subtree pack ing problem is polynomial if and only if each rooted subtree problem i s polynomial, In addition we show that the convex hulls of the feasibl e solutions to both problems are related: the convex hull of solutions to the packing problem is given by ''pasting together'' the convex hu lls of the rooted subtree problems. We examine in detail the case wher e the set of feasible subtrees rooted at node i consists of all subtre es with at most k nodes, For this case we derive valid inequalities, a nd specify the convex hull when k less than or equal to 4.