Faster Algorithms for Parametric Global Minimum Cut Problems

Abstract

The parametric global minimum cut problem concerns a graph $G=(V,E)$ where the cost of each edge is an affine function of a parameter $\mu \in {\mathbb{R}}^d$ for some fixed dimension $d$. We consider the problems of finding the next breakpoint in a given direction, and finding a parameter value with maximum minimum cut value. We develop strongly polynomial algorithms for these problems that are faster than a naive application of Megiddo's parametric search technique. Our results indicate that the next breakpoint problem is easier than the max value problem.

20 pages, 2 figures