This problem belongs to the class of problems called Network Interdiction, or Network Inhibition problems. See Phillips (1993). This specific problem is called Most Vital Node.
Assuming digraphs, we can replace each vertex with a capacitated directed edge, and thus consider only the removal of edges instead of vertices.
This problem is called Most Vital Link, and an algorithm was given by Wollmer in 1963. Lubore and Sicilia (1971) improved the algorithm, later followed by Sicilia and Ratliff (1975).
There is one main observation that gives the basis of the algorithm:
Theorem (Lubore and Sicilia, 1971). A necessary condition for an arc $uv$ to be a most vital link in a flow network $(G, s, t, \text{cap})$ is that for any flow $f$, the flow over $uv$ is at least as great as the flow over every arc in a minimum cut.
An algorithm that only consider such arc is a slight improvement over the naive algorithm. You can find the algorithm described in their paper.
If your graph is $s$-$t$-planar, I believe even faster algorithms should exist: Notice that the most vital link is the heaviest edge in a minimal cut when we don't count the heaviest edge. I.e., let $C$ be a minimal cut, and let $$h(C) = \sum_{e \in C} \text{cap}(e) - \max_{e \in C} \text{cap}(e).$$ Then $$\min_{C \text{ a minimal $s$-$t$-cut}} h(C)$$ is the new flow.
