# Algorithm Design

- Jon Kleinberg, Cornell University
- Éva Tardos, Cornell University

question (see attachment):

In a standard minimum s-t cut problem, we assume that all

capacities are nonnegative; allowing an arbitrary set of positive and negative capacities results

in a problem that is computationally much more difficult. However, as we’ll see here, it is

possible to relax the nonnegativity requirement a little and still have a problem that can be

solved in polynomial time.

Let G = (V, E) be a directed graph, with source s ∈ V , sink t ∈ V , and edge capacities {ce}.

Suppose that for every edge e that has neither s nor t as an endpoint, we have ce ≥ 0. Thus

ce can be negative for edges that have at least one end equal to either s or t.

Give a polynomial-time algorithm to find an s-t cut of minimum value in such a graph.

(Despite the new nonnegativity requirements, we still define the value of an s-t cut (A, B):

X

(u,v)∈E

u∈A, v∈B

c(u,v)