The traditional s-t cut problem is the problem where we have only one single pair and in that case one very important and also old result from the sixties says that the optimum max-flow solution is equal to the optimum min-cut solution. This means that the maximum flow that we can route from a source s to a sink t is equal to the min-cut in the graph. We will see how this extends to our case: the min multi-cut problem. In this case we cannot state anymore such statement. In fact, we have that while the s-t cut problem is polynomial time solvable. In particulat the linear programming formulation, even with fractional variables, has actually an integral optimal solution. In our case we have that the multi-cut problem is a NP-hard problem. Moreover, the optimal solution of a linear programming relaxation is away from the optimal solution of the dual problem, that is the maxi multi commodity flow problem.
