logoalt Hacker News

emil-lp • last Tuesday at 4:47 PM • 2 replies • view on HN

It's NP-hard from Minimum s–t Cut with at least k Vertices. That's the edge version, but since the grid graph is 4-regular(-ish), the problem is trivially convertible to the vertex version.

Edit: apex-4-regular

Replies

sltkr • last Wednesday at 9:23 PM

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.
➕ show 1 reply
sltkr • last Wednesday at 9:15 PM

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.

➕ show 1 reply