3 ms·

I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you fin

I think it's NP hard, maybe from Sparsest Cut. But you could probably find the min-cut and then iterate by adding capacity on edges in the min cut until you find a cut of the right size. (if the desired cut-size is close to the min cut size at least).

emil-lp 9mo ago
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
- sltkr 9mo ago
  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.
  - emil-lp 9mo ago
    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.
- sltkr 9mo ago
  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.
  - emil-lp 9mo ago
    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.

emil-lp 9mo ago

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

sltkr 9mo ago
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.
- emil-lp 9mo ago
  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.
sltkr 9mo ago
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.
- emil-lp 9mo ago
  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.