Minimizing flow on a 2D matrix network

Question

I am currently dealing with a problem that I believe to be a network flow related problem, and I am trying to find some similar solved problems to help me formulate my solution. I want to make it clear that I am not searching for a solution here, but asking a community of more experienced individuals if they have experience with/heard of similar problems to what I am about to describe.

Given an nxn matrix, let some small number of matrix indices (I will refer to them as nodes from now on) be colored blue, and rest of the nodes be colored white. Any white node that is adjacent (not including diagonal) to a blue node will become blue unless a block is placed between them. So for example, in a 2x2 grid, if the node at (0, 0) is blue and the rest are white, the whole grid will become blue unless blocks are placed between (0,0) and (0, 1) as well as (0, 0) and (1, 0).

Now, each block placed has a cost of 1, and each white node being converted to a blue node will have some cost greater than zero (the cost will be the same for all white nodes). The goal is to place blocks on the matrix such that the total cost is minimized.

It most problem instances, especially with a low cost of white nodes becoming blue, it will be optimal to let some white nodes suffer becoming blue. For example, going back to the 2x2 problem instance, if each white to blue conversion only costs .25, then letting all the nodes become blue will cost .75, whereas placing 2 blocks would cost 2, and so the minimum cost would be .75 and letting the blue spread across the grid.

I am wondering if anyone can recall a problem instance/algorithm that is similar to what I am attempting to solve and could suggest researching it? I have scoured the internet relating to min-cut/max-flow algorithms, but I am having trouble relating this problem to anything regarding network flow. Any suggestions of problems to research would be much appreciated.

Answer 1

Build a grid graph, with one node per entry in the matrix, and edges between each pair of adjacent nodes. Also add a source node $s$ with an edge from $s$ to each blue node, and a sink node $t$ with an edge from each white node to $t$. Set the capacity of each edge to 1, except the $s$-to-blue edges have capacity $\infty$, and the white-to-$t$ edges have capacity given by the cost of allowing that white node to become blue.

Now, find the minimum $(s,t)$-cut in this graph, using any network flow algorithm. The $s$ side of this cut will contain all of the nodes that become blue, and the edges that cross the cut will indicate where to place blocks (for blue-to-white edges that cross the cut) and which white nodes become blue (for white-to-$t$ edges that cross the cut).

---

Why does this work? We're going to treat the final colors as defining a cut $(B,W)$: $B$ contains all nodes that are ultimately blue (and $s$), and $W$ contains all that remain white (and $t$). This means that any edge between an ultimately-blue node and an ultimately-white node crosses the cut, which matches the problem requirement that such an edge must have a block on it. Also, if $b \in B$ is any node that was originally white but becomes blue, then the edge $b \to t$ crosses the cut (since $t \in W$), so we think of it as having a block between it and $t$. Finally, we want to know the cheapest way to choose a set of blocks. The total cost of a set of blocks is the sum of the capacities of the edges that were blocked, so this total cost matches the total capacity of the edges that cross the cut $(B,W)$, i.e., the capacity of the cut. So, finding a min-capacity cut will find you the cheapest way to place a set of blocks that match the problem requirement.