# Finding min s-t cut of network with flow on the nodes

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)

• 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. Sep 28, 2023 at 12:18
• 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. Oct 1, 2023 at 18:20

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.