Lesson 2

Advanced Problems.

1. (20 points)
   • (10 points) Let's call a \(k\)-fan from vertex \(x\) to set \(Y\) the set of \(k\) paths starting at \(x\), ending at \(Y\) and having no common vertices except vertex \(x\). Let \(G\) be a \(k\)-connected graph, \(x\) some vertex of it, and \(Y\) the set of at least \(k\) vertices of graph \(G\) not containing \(x\). Prove that there exists a \(k\)-fan from \(x\) to \(Y\).
   
   
   • (10 points) Let \(G\) be a \(k\)-connected undirected graph with \(k\ge 2\). Prove that for any \(k\) vertices of \(G\) there is a cycle \(C\) on which all these \(k\) vertices lie.
   
   

   Hint:

   For the second point, use induction to insert one extra vertex into a cycle without losing previously included vertices.
2. (20 points) Give a necessary and sufficient condition for an \(s\)–\(t\) network \((G,c)\) to have a unique minimum cut, where the condition is checkable from the output of a max-flow algorithm (using one residual graph and/or strongly connected components). Then design an algorithm that either outputs “unique” and returns the cut, or outputs “not unique” and returns two different minimum cuts.
3. (20 points) Let \(G=(V,E)\) be a directed network with nonnegative capacities \(c\colon E\to\mathbb{R}_{\ge 0}\), and let \(s,t\in V\) be distinct. Define \(\mathcal{S}\) to be the family of vertex sets \(S\subseteq V\) such that \(s\in S\), \(t\notin S\), and the cut \((S,V\setminus S)\) is a minimum \(s\)–\(t\) cut.
   • (10 points) Show that there exist unique sets \(S_{\min}=\bigcap_{S\in\mathcal{S}}S\) and \(S_{\max}=\bigcup_{S\in\mathcal{S}}S\), and that both correspond to minimum cuts.
   
   
   • (10 points) Give an algorithm to compute \(S_{\min}\) and \(S_{\max}\) using only a constant number of max-flow computations and near-linear extra work.
   
   

4. (20 points) Prove that if the Ford–Fulkerson algorithm always chooses an augmenting path of minimum number of edges (i.e., it runs BFS in the residual network each iteration), then: (a) each augmentation increases the length (in edges) of the shortest residual path for at least one saturated edge in a monotone way, and (b) the number of augmentations is \(O(|V|\cdot |E|)\).
   Hint:

   Let \(d_{f}(u)\) denote the shortest path distance from the source \(s\) to node \(u\) in the residual graph \(G_{f}\). Show that for all \(v \in V\), the distance \(d_{f}(v)\) is non-decreasing throughout the algorithm.
5. (20 points) Consider a directed graph \(G=(V, E)\) with a source \(s\), a sink \(t\), integer capacities \(c(e)\), and edge costs \(\operatorname{cost}(e)\). Assume that the initial graph contains no negative-cost cycles. Construct an algorithm to find a minimum-cost maximum flow that runs in time \(O(F \cdot m n)\), where \(F\) is the value of the maximum flow and \(m\) is the number of edges.
6. (25 points) For a graph \(G = (V,E,w)\) and a subset \(U \subseteq V\) of vertices, define \(\partial_{G} U\) as the set of edges of \(G\) having exactly one endpoint in \(U\). For a subset \(F \subseteq E\) of edges, define \(w(F) := \sum_{e \in F}w(e)\) as the total weight of the edges in \(F\).

   Let a weighted, undirected graph \(G = (V,E)\) and a subset \(R \subseteq V, |R| \ge 2\). We say that the minimum isolating cuts for \(R\) is a collection of sets \(\{S_{v} : v \in R\}\) satisfying \[S_{v} = \arg\min \{ w(\partial S) \mid S \cap R = \{v\} \} \quad \text{for all \(v \in R\)}.\]

   Show that there exists an algorithm that computes the minimum isolating cuts for \(R\) using \(O(\log R)\) calls to usual max–flow on weighted graphs with \(O(n)\) vertices and \(O(m)\) edges, and that runs in \(O(m \log n)\) deterministic time outside the max–flow calls. If the original graph \(G\) is unweighted, then the inputs to the max–flow calls should be also unweighted.