13.2.3. Multiway Edge Cut*

The multiway edge cut problem can be modelled as an ILP similar to (13.3), and it is possible to obtain a \(2\)-approximation of an optimal multiway edge cut by rounding an optimal solution of the LP relaxation of this ILP:

Exercise 13.2: Provide an ILP formulation of the multiway edge cut problem based on the same idea as the ILP formulation of the multiway vertex cut problem (13.3): Every path between two terminals must contain at least one edge in the cut. By mimicking the proof in Section 13.1.2, prove that the LP relaxation of this ILP has a half-integral optimal solution. Conclude that rounding up the variable values in this solution yields a \(2\)-approximation of an optimal multiway edge cut.

It can also be shown that this ILP has an integrality gap of \(2 - \frac{1}{k}\), that is, that there exist some inputs where \(\frac{\textrm{OPT}}{\textrm{OPT}_f} = 2 - \frac{1}{k}\). Since any feasible solution must have weight at least \(\textrm{OPT}\) but we prove the approximation ratio by comparing this weight to \(\textrm{OPT}_f\)—because we do not know \(\textrm{OPT}\)—this means that it is impossible to prove an approximation ratio better than \(2 - \frac{1}{k}\) for any algorithm based on rounding a solution of this LP relaxation. If \(k\) is large, then the approximation ratio of \(2\) that you are asked to prove in Exercise 13.2 is essentially tight. To obtain a better approximation ratio, we need a different ILP formulation of the multiway edge cut problem.

We discuss an improved algorithm, one that achieves an approximation ratio of \(\frac{3}{2}\), in three stages:

• First, we discuss a different ILP formulation of the multiway edge cut problem that forms the basis of this improved algorithm.

• Then we discuss how to apply randomized rounding to obtain a Monte Carlo algorithm whose approximation ratio is just slightly better than required: \(\frac{3}{2} - \frac{1}{k}\), where \(k\) is the number of terminals.

• Finally, we use the standard "repeat until we have the desired solution" approach to convert this Monte Carlo algorithm into a Las Vegas algorithm with approximation ratio \(\frac{3}{2}\). The fact that the Monte Carlo algorithm achieves a better approximation ratio than this will be crucial in this transformation.