One of the most celebrated and re-discovered results in parametric optimization was best described by Gallo, Grigoriadis, and Tarjan (GGT). They showed that under certain conditions the min cuts coming from max flow with parametric capacities are {\em nested}, and that all of these cuts can be computed in the same time as one max flow. The GGT model allows only a single parameter, and only on arcs out of the source or into the sink.

Motivated by some applications in scheduling, we recently extended his result to parameters on directed trees at the source and sink, and to a multi-parametric version of the problem. This talk will also mention some extensions achieved by other researchers.

We then look at a common generalization of two of these problems and consider whether the GGT result can be further generalized to it.