# Number of breakpoints in parametric maximum flow problems

The parametric maximum flow problem can be formulated as $$f(\lambda) = \min_{x\in\{0,1\}^n} \left( \sum_{i}(a_i + b_i\lambda)x_i + \sum_{i,j}c_{ij}x_ix_j \right),$$ where all $c_{ij}<0$ (so that the function can be evaluated in polynomial time). $f$ will be piecewise affine and the number of breakpoints can in general be exponential in the size of $x$. The example of this uses a similar construction as in the proof that the simplex method can require an exponential number of steps.

But what if we impose some other restrictions? For example, many graphs occuring in e.g. computer vision have a limited number of connections between the variables. That is, for any $i$, the number of $c_{ij}\neq 0$ is less than or equal to $K$. Can we then prove that the number of breakpoints of $f$ will be polynomially bounded, e.g. less than $p(n)2^K$? This would be interesting to the field of computer vision, where these problems appear.

-