That conclusion may be too hasty. If min cut with k vertices is NP-hard on arbitrary graphs, that doesn't automatically mean that that applies to a 2D grid too.

Is NP hardness proven for just planar graphs? Those are closer to the 2D grid, but still slightly more general. All I could find was a reduction to densest k subgraphs, but Wikipedia tells me that whether that problem is NP hard for planar graphs is an open question.

To be clear, I would be very surprised if the problem turns out to be _not_ NP hard, but there is no trivial equivalence to min cut in general graphs to show that it is.

I agree, that is a good point. Although it is (induced) subgraphs of 2D grids, which gets you a bit closer to the planar case (albeit with bounded degree).

It might be polytime on planar graphs, but that would be surprising.

Also I don't think the equivalence between edge/vertex versions is trivial at all (though maybe we just have different standards of triviality).

For example, in a grid like this:

    ..####
    .....#
    #.#..#
    #...H#
    ######

A single wall placed (i.e. vertex removed) can block two edges, and it's not obvious what graph transformation can turn that into a single edge.

You transform it into the directed case and then you turn each vertex into an arc.

There is a standard construction for going between vertex and edge cuts.