## ICS 269, Fall 2005: Theory Seminar

# The Weighted Maximum-Mean Subtree and Other
Bicriterion Subtree Problems

## Josiah Carlson

### October 7, 2005, in CS 259

Abstract:

We consider problems in which we are given a rooted tree as input, and must
find a subtree with the same root, optimizing some objective function of
the nodes in the subtree. When this function is the sum of constant node
weights, the problem is trivially solved in linear time. When the objective
is the sum of weights that are linear functions of a parameter, we show how
to list all optima for all possible parameter values in O(n log n) time;
this parametric optimization problem can be used to solve many bicriterion
optimizations problems, in which each node has two values xi and yi
associated with it, and the objective function is a bivariate function
f(SUM(xi),SUM(yi)) of the sums of these two values. A special case, when f
is the ratio of the two sums, is the Weighted Maximum-Mean Subtree Problem,
or equivalently the Fractional Prize-Collecting Steiner Tree Problem on
Trees; for this special case, we provide a linear time algorithm for this
problem when all weights are positive, improving a previous O(n log n)
solution, and prove that the problem is NP-complete when negative weights
are allowed.

(Joint work with D. Eppstein.)