Tom McCormick

Title:
Parametric minimum cuts: how far, how fast?

Abstract:
Gallo, Grigoriadis, and Tarjan (GGT) proposed a class of parametric max
flow/min cut problems with two nice properties: (1) they have nested min
cuts, and (2) you can compute all min cuts in the same asymptotic time as
one call to Push-Relabel. McCormick and others proposed some generalizations
of this. Part (1) of all these results can be derived from a general result
on parametric submodular optimization by Topkis. We specialize Topkis'
result to parametric min cut to get a more general version than previous
results with wider applications, and we show how to do a flow update that
keeps part (2) of GGT. We further consider a similar model where we allow
only cuts that contain no backwards arcs from a given poset, and a
generalization of a model by Fleischer; both of these models also have both
of the GGT properties. Finally we consider Milgrom and Shannon's Single
Crossing Condition (SCC), which generalizes Topkis' result. SCC enjoys
nested min cuts, but so far we do not know a flow update that achieves part
(2) of GGT.

(with Frieda Granot, Maurice Queyranne, and Fabio Tardella)