# algorithms – Minimizing flow on a 2D matrix network

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 2×2 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 2×2 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.

Posted on