# min-cut with extra condition

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.

• Does this work? Turn your graph into a directed one, add vertex $C$ which is has an incoming edge from every $c_i$ with capacity $2m+1$, where $m$ is the number of edges of the old graph. Then compute a minimal flow, from $K$ to $C$. – frafl Mar 4 '13 at 14:46
• Do you mean maximum flow <=> minimum cut? Because that's what I ended up doing and it seemed fine. – Zeta Two Mar 4 '13 at 15:26
• Yes, I think, the only thing you have to do is ensuring every minimal cut (in the sense of networks) separates all $c_i$ from $K$. – frafl Mar 4 '13 at 15:35
• @frafl, your answer is correct, is better to turn your comment in an answer, also Zeta two, this isn't np-complete because max-flow mean cut is in $P$ (unless $P=NP$). – user742 Mar 5 '13 at 7:29
• @SaeedAmiri: ZetaTwo only wanted hints, so I thought he would like to answer himself. Also, I left out, where the cut is, but that's easily found on the web if it wasn't mentioned in his class. ZetaTwo: Shall I answer or would you like to? – frafl Mar 5 '13 at 14:34

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\}$.