(a) For any set $S \subseteq V,$ let $\delta(S)=c(S, V \backslash S)=\sum_{e \in E(S, V \backslash S)} c(e)$ be the capacity of the cut $S .$ Prove that for any two sets $S, T \subseteq V$, we have
$$
\delta(S \cap T)+\delta(S \cup T) \leq \delta(S)+\delta(T)
$$
There is a technical term for this: we say that the function $\delta(\cdot)$ is submodular. Hint: Draw Venn diagram. Try case analysis.
(b) Let $(A, V \backslash A)$ and $(B, V \backslash B)$ be s-t minimum cuts. Prove that $(A \cap B, V \backslash(A \cap B))$ and $(A \cup B, V \backslash(A \cup B))$ are also both $s-t$ minimum cuts.
(c) Conclude that there exists a unique $s-t$ minimum cut $(A, V \backslash A)$ closest to s. That is, for any other $s-t$ minimum cut $\left(A^{\prime}, V \backslash A^{\prime}\right),$ we know that $A \subseteq A^{\prime}$.
(d) Show how to compute the unique $s-t$ minimum cut closest to $s$ by a single call to the $s-t$ max flow algorithm plus additional linear time.

\begin{prob}

Integral Flow ( 4 points): It is a useful fact that Ford-Fulkerson and Dinic algorithms covered in class always return an integral max flow $f \in \mathbb{Z}_{\geq 0}^{E}$ if all edge capacities $c \in \mathbb{Z}_{\geq 0}^{E}$ are integral. For example, given any capacitated graph $G=(V, E, c),$ if we can construct a non-integral feasible flow $f \in \mathbb{R}_{\geq 0}^{E}$ in $G,$ then we know there must exist an integral flow $f^{\prime}$ of value $v\left(f^{\prime}\right) \geq v(f)$ (e.g. the flow $f^{\prime}$ returned by Ford-Folkerson satisfies this property). Below, you will see more concretely how to use exploit this fact.
(a) A bipartite graph $G=(A \cup B, E)$ is called $d$ -regular if each $u \in A$ is adjacent to $d$ vertices in $B$ and each $v \in B$ is adjacent to $d$ vertices in $A$. Prove that every $d$ -regular bipartite graph contains a perfect matching.

(b) You and $n-1$ of your friends are in a car pool club. On day $i$ a subset $A_{i} \subseteq\{1, \ldots, n\}$ pile into a bus and go to work. Of course, someone must take a hit for the team and drive the bus while everyone else works on their laptops, watches movies, etc. If the same people went to work every day then they would just take turns driving the bus, which is fair. Unfortunately, every day could be different: the sequence $A_{1}, A_{2}, \ldots, A_{t}$ is completely arbitrary. Prove that it is possible for each person $j$ to drive at most
$$
D_{j}=\left\lceil\sum_{1 \leq i \leq t: \atop j \in A_{i}} \frac{1}{\left|A_{i}\right|}\right.
$$
times. Analyze the time required to compute a schedule in which person $j$ drives $D_{j}$ times, for all $j$.

Fast Blocking Flow ( 4 points): Let $G=(V, E)$ be a directed flow graph with $c: E \rightarrow \mathbb{R}_{>0}$ and $s, t \in V$
(a) Give an algorithm based on depth first search to find a blocking flow $f$ and prove that it runs in $O(m n)$ time, $m=|E|, n=|V|$

(b) Prove that in a unit-capacity graph (i.e. when $c(e)=1$ for all $e \in E)$, it runs in $O(m)$ time.

Using Fast Blocking Flow (4 points): Let $G=(V, E)$ be a unit-capacity directed graph with $m$ edges and $n$ vertices. Let $s, t \in V$.
(a) Show how to compute an $s-t$ max flow in $G$ in $O(m \sqrt{n})$ time when every vertex $v$ has either in-degree 1 or out-degree 1 . Hint: This is a generalization of $O(m \sqrt{n})$ -time algorithm for computing maximum bipartite matching.
(b) Using (a), show how to compute a maximum vertex-disjoint $s-t$ paths and minimum $s-t$ vertex cut in $O(m \sqrt{n})$ time.
(c) Show how to compute an $s-t$ max flow in $G$ in $O\left(m^{3 / 2}\right)$ time.
(d) Show how to compute an $s-t$ max flow in $G$ in $O\left(m n^{2 / 3}\right)$ time.

Fastest $k$ -vertex connectivity ( 4 points): Explain how to modify the $k$ -edge connectivity algorithm shown in class to obtain an algorithm for solving $k$ -vertex connectivity (i.e. given a directed graph $G=(V, E),$ find a vertex cut $(L, S, R)$ where $|S|<k$ if exists.). The algorithm should run in $\tilde{O}\left(m k^{2}\right)$ time and should be correct with high probability. There should be two main modification:
(a) The local cut algorithm.
(b) The overall algorithms that separately considers the unbalanced case and the balanced cases.

Modeling problems as LPs (8 points): Later in class, you will see that just by formulating of problems as an LP and its dual, we can get a good starting point for designing algorithms (without solving LP itself) $^{1}$. The initial steps are the following.
– Formulate the problem as a linear program (LP).
– Write its dual LP.
– Give a combinatorial interpretation of the problem that the dual LP solves.
In this problem, you will practice the above process for each of the problems below.
(a) An $s-t$ flow measures the rate at which one kind of “stuff” can flow from $s$ to $t$. In this problem you’re given a directed graph $G=(V, E, c)$ with $c \in \mathbb{R}_{>0}^{E}$ and two sources $s_{o}, s_{v}$ and two sinks $t_{o}, t_{v} .$ Olive oil is produced at $s_{o},$ travels through the network, and is consumed at $t_{o} .$ At the same time, vinegar is produced at $s_{v},$ travels through the network, and is consumed at $t_{v} . \mathrm{A}$ vinaigrette flow satisfies:
– the total flow (olive oil + vinegar) passing through any edge does not exceed its capacity.
– the olive oil and vinegar flows each satisfy flow conservation, except at their respective sources and sinks.

The value of a vinaigrette flow is the net olive oil leaving $s_{o}$ plus the net vinegar leaving $s_{v} .$ The goal is to find a vinaigrette flow with maximum value.
(b) A vinaigrette flow has concurrent value of $v$ if the minimum of the net olive oil leaving $s_{o}$ and the net vinegar leaving $s_{v}$ is $v .$ The goal is to find a vinaigrette flow with maximum concurrent value.
(c) There are $n$ students and $k$ jobs. Student $i$ can work up to $h(i)$ hours per week and gets paid $p(i)$ dollars per hour. Job $j$ demands $l(j)$ hours per week. Here $h, p, l$ assign non-negative integers. A student can work multiple jobs and a job can be done by multiple students. The goal is to allocate each student’s time to various jobs so that each job $j$ is assigned exactly $l(j)$ hours and each student $i$ is assigned at most $h(i)$ hours, and subject to these constraints, the total wages are minimized. (The interpretation of the dual LP might not be very nice.)
(d) What if the goal is to find an the assignment that maximizes the total wage of the students?

Global edge mincut: In class, we did not solve the global mincut problem exactly, but we see how to check if the graph is $k$ -edge connected. That is, we have seen a randomized algorithm that, given $k$, returns a cut $(A, B)$ such that $|E(A, B)|<k$ if exists. So the cut might not be a minimum cut, it just has size less than $k .$ Let $\lambda=\min _{(A, B): \text { cut }}|E(A, B)| .$ A global mincut $(A, B)$ is such that $\lambda=|E(A, B)| .$ Show a randomized algorithm that computes $\lambda$ and a global mincut in $\tilde{O}\left(m \lambda^{2}\right)$ time with high probability.

Extension of $s-t$ max flow: Given a graph $G=(V, E,),$ lower and upper bounds on edges $\ell, u \in \mathbb{R}_{\geq 0}^{E},$ and a demand $d \in \mathbb{R}^{V}$, we want to check if there exists a circulation $f \in \mathbb{R}_{\geq 0}^{E}$ such that
$$
\ell(e) \leq f(e) \leq u(e) \quad \forall e \in E
$$
and
$$
\sum_{(x, u) \in E} f(x, u)-\sum_{(u, x) \in E} f(u, x)=d(u) \quad \forall u \in V
$$
Show how to reduce this problem the just the $s-t$ max flow problem (i.e. solve it by calling a subroutine for computing an $s-t$ max flow as a black box).

Generality of minimum cost circulation: In the minimum cost circulation problem, you are given a graph $G=(V, E, c, w)$ with capacities $c \in \mathbb{R}_{>0}^{E},$ weights $w \in \mathbb{R}^{E}$, and demand $d \in \mathbb{R}^{V}$, and you need to find a circulation $f \in \mathbb{R}_{\geq 0}^{E}$ such that
$$
\begin{array}{lll}
\min & \sum_{e \in E} w_{e} f_{e} \\
\text { s.t. } & \sum_{(x, u) \in E} f_{x, u}-\sum_{(u, x) \in E} f_{u, x}=d_{u} & \forall u \in V \\
& 0 \leq f_{u, v} \leq c_{u, v} & \forall(u, v) \in E
\end{array}
$$
Explain in a few sentences why each of the following problems is a special case of the minimum cost circulation problem:
(a) s-t max flow
(b) $s-t$ shortest paths
(c) finding a perfect matching in bipartite graphs.
(d) finding a minimum weight perfect matching in bipartite graphs (i.e. an assignment problem)
(e) transshipment problems (for definition, see https://en.wikipedia.org/wiki/Transshipment_problem)