3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$. $\endgroup$ – frafl Mar 4 '13 at 14:46
  • $\begingroup$ Do you mean maximum flow <=> minimum cut? Because that's what I ended up doing and it seemed fine. $\endgroup$ – Zeta Two Mar 4 '13 at 15:26
  • 1
    $\begingroup$ 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$. $\endgroup$ – frafl Mar 4 '13 at 15:35
  • $\begingroup$ @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$). $\endgroup$ – user742 Mar 5 '13 at 7:29
  • $\begingroup$ @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? $\endgroup$ – frafl Mar 5 '13 at 14:34
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.