This problem belongs to the class of problems called Network Interdiction, or Network Inhibition problems.  See Phillips (193).

  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.

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.