Short description: Use max flow to solve related problems via reductions; prove correctness.
Relevant notes: Topic E: Max Flow.
Given a variant of max flow or a related problem, solve it by reducing it to max flow. Prove correctness of the solution. In cases where max-flow min-cut is needed for correctness, it may be assumed to hold.
Consider a max flow problem, but there are multiple possible sources of flow and multiple possible sinks. The new goal is to maximize the total flow into all of the sinks. The constraints on a flow are the same, except that now the net flow constraint does not apply to any of the sources or sinks.
Give a reduction from max flow with multiple sources and sinks to max flow. Sketch a proof of correctness.
First we give the reduction. We need two parts:
For 1, Let $G_1,c_1$ be the original graph. We construct a new graph $G_2$ by taking a copy of $G_1$ and adding a "supersource" $s^*$ and "supersink" $t^*$. For each source $s$ in $G_1$, we add an edge $(s^*, s)$ with capacity infinity. (Actually, we can just set the capacity to any large enough number, e.g. the sum of all the capacities of the original graph.) For each sink $t$ in $G_1$, we add an edge $(t, t^*)$ with capacity infinity as well.
For 2, given $f_2$, we simply remove $s^*,t^*$ and all of their edges, and this gives us $f_1$.
Now that we have the reduction, we sketch a proof of correctness. $G_2,c_2$ is a valid instance of max flow, since it has only one source and one sink. We assume the max-flow min-cut theorem applies with multiple sources and sinks. In this case, we can see that a min cut of $G_2,c_2$ would never contain any of the "infinity" edges, so a min cut in $G_2,c_2$ is the same as in $G_1,c_1$. Since the flow amounts are the same as well, this proves that $f_1$ is optimal in $G_1,c_1$.
To pass, a solution must follow the course requirements for writing and proofs.
To pass, a solution must have a correct reduction and a correct proof. Because we asked for a proof sketch, the proof may be at a high-level and omit some details, as in the example solution.
The reduction must do two things: (1) explain how to convert an instance with multiple sources and sinks into an instance of the original max flow problem; and (2) explain how to convert the solution to that original problem back into a solution for multiple sources and sinks.
The solution must show (a) that it produces an instance of the original max flow problem. Then it must show (b) that the output of the algorithm is optimal. It should ideally argue this using max-flow min-cut. However, a solution that argues from the correctness of the original algorithm may also be accepted if it is supported and the rest of the solution is correct.
The numerical rubric for this problem is: