min-cut with extra condition

Question

I have a undirected graph with no edge costs. A subset of the nodes are labeled $c_1, c_2, ..., c_k$ and one node is labeled $K$. I want to find the minimum cut of the graph with the extra condition that all nodes $c_i$ are in the same half of the cut and the node K is in the other cut.

My idea was to begin by doing a BFS from $K$ to all nodes $c_i$, saving predecessors and then finding all paths from $K$ to a node $c_i$ and finally picking the minimum set of edges from the paths so that at least one edge from each path was chosen. Unfortunately, if I understand this correctly, this is equivalent to the NP-complete set cover problem.

Is there anything sane with this approach? Do you have any hints to push me in the right direction?

Note: this is homework so I'd rather have some hints than a full solution.

Answer 1

We'll use the max-flow min-cut theorem to solve this.

Therefore we map each instance $(G,K,\{c_{1},\dots,c_{k}\})$ to the network $N:=(V(G) \stackrel{.}{\cup} \{C\},E(N),e,K,C)$, where $C$ is a new vertex not in $V(G)$ (our sink), $K$ is our source and $e$ denotes the edge capacities,

$$E(N) := \{(u,v)|\{u,v\}\in E(G)\} \cup \{(c_i,C)|i\in\{1,\dots,k\}\}$$ and $$e((u,v)) := \begin{cases}2|E(G)|+1&v=C\\1&\text{else} \end{cases}\qquad.$$

Then $(V_1,V_2)$ is a minimum $K$-$C$-cut in $N$ if and only if $(V_1,V_2\setminus\{C\})$ is minimum cut in $G$ subject to the condition that $K\in V_1,\forall i: \, c_i\in V_2$:

"$\Rightarrow$": Every $K$-$C$-cut with the property $\forall i: \, c_i\in V_2$ has a capacity of at most $2E(G)$, every cut with $\exists i: \, c_i\in V_1$ has capacity of at least $2E(G)+1$. Therefore only those having the desired property can be a minimum cut. Since for each $(u,v), u\in V_1, v \in V_2$ of a minimum cut the edge capacity is $1$, $\mathrm{cap}(V_1,V_2)=||\{\{u,v\}\in E(G)|u\in V_1,v\in V_2\}||$.

"$\Leftarrow$": analogous to second part of "$\Rightarrow$".

If we have computed a maximum flow $f$ by e.g. the Edmonds–Karp algorithm, we compute the residual Network $N_f$ where $e(N_f)=e-f$ and $E(N_f)=E(N)\setminus\{(u,v)|f((u,v))=1\}$, i.e. we remove the edges used by the maximum flow. Let $V_1$ be the set of vertices reachable from $K$ in $N_f$ and $V_2=V(G)\setminus V_1$. Then $(V_1,V_2\cup\{C\})$ is a minimum cut in $N$ and thus $(V_1.V_2)$ is a minimum cut in $G$ separating $K$ and $\{c_1,\dots,c_k\}$.