1
$\begingroup$

Given a network with flow on the nodes. How can we find min s-t cut in a network with flow on the nodes?

We know how to find min s-t cut whenever there’s a network with flow on the edges (Ford Fulkerson, Edmonds Karp)

$\endgroup$
2
  • 1
    $\begingroup$ This sounds like homework, what did you try to do? I don't think the correct question is "with flow on the nodes". Are you sure you're not supposed to find a minimum vertex separator? If so, you can model each node as an edge. $\endgroup$
    – Pål GD
    Sep 28, 2023 at 12:18
  • $\begingroup$ This is a small part of our final project in our B.sc Computer Science degree. We are given a graph (network) that every node has a capacity (the nodes, not the edges), and we need to find a min s-t cut on that graph. We've found a reduction that somehow managed to do it but we didn't understand it. $\endgroup$ Oct 1, 2023 at 18:20

1 Answer 1

2
$\begingroup$

Given a directed graph, you can construct a new graph $G'$ where you replace each vertex $v$ with two vertices $v_{\text{in}}$ and $v_{\text{out}}$. Then you add the edge $v_{\text{in}}v_{\text{out}}$ with capacity equal $v$'s capacity in $G$. Then for each edge $vu$ in $G$, you add the edge $u_{\text{out}}v_{\text{in}}$ with capacity $+\infty$.

Let $C$ be any set of vertices in $G$ and $C'$ the corresponding edges in $G'$. Then the cost of $C$ and $C'$ is the same, and $C$ is an $s$-$t$-separator if and only if $C'$ is as $s$-$t$-cut.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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