I am trying to solve an interesting problem in graph coloring which I believe is related to the vertex cover problem. The graph is a $12 \times 12$ grid, representing a field. The field needs to be colored in 3 colors: "green" representing a tree, "blue" representing water and "white" representing an empty space. The rules of the coloring are as follows:
- 2 trees cannot be adjacent.
- Every tree must be adjacent to at least one water.
- All the water-nodes must form one connected component (i.e. for any 2 nodes colored blue, there is a blue path between them).
- The total number of trees must be 34.
- 8 of the trees and 1 water are at fixed places and cannot be moved (see attached image).
The goal: Find a coloring respecting all the rules and using the minimal amount of water.
I saw this problem in a game so I don't think I am expected to find an analytical solution, but I am very interested in ways to solve this question using proper algorithms rather than just trying random things and expect it works. I also wonder what can be said about generalizations, $i.e.$ larger grids or any other graph with any initial condition.
I think this is somehow related to Steiner-trees or Vertex cover problems, and read few papers about solving for grids, but I did not find any clear way to address this problem (especially considering the fact that 26 trees positions are not given).
Thanks for your help.
You can solve the problem via integer linear programming as follows. Let $N$ be the set of nodes, let $E$ be the set of edges, and let $N_i$ be the neighbors of node $i$. For $i\in N$, let binary decision variables $t_i$ and $w_i$ indicate whether node $i$ is a tree or water, respectively. The problem is to minimize $\sum_{i\in N} w_i$ subject to linear constraints \begin{align} t_i + w_i &\le 1 &&\text{for $i\in N$} \tag0\label0\\ t_i + t_j &\le 1 &&\text{for ($i,j)\in E$} \tag1\label1 \\ t_i &\le \sum_{j\in N_i} w_j &&\text{for $i\in N$} \tag2\label2 \\ \sum_{i\in N} t_i &= 34 \tag3\label3 \\ t_i &= 1 &&\text{for the $8$ fixed green nodes $i$} \tag4\label4 \\ w_i &= 1 &&\text{for the fixed blue node $i$} \tag5\label5 \\ \end{align} Constraint \eqref{0} prevents a node from being both a tree and water. Constraint \eqref{1} prevents adjacent trees. Constraint \eqref{2} forces at least one adjacent water for each tree. Constraint \eqref{3} enforces $34$ trees. Constraints \eqref{4} and \eqref{5} respect the fixed nodes.
It remains to enforce contiguity of water. One approach is to introduce nonnegative flow variables and send one unit of flow from the given "source" water node to each other water node. A second approach is to introduce a binary distance variable $x_{id}$ that indicates whether water node $i$ is distance $d$ from the source. Only the source has distance $0$, and all other water nodes must satisfy $x_{id} \le \sum_{j\in N_i} x_{j,d-1}$. A third approach is to dynamically introduce "node separation" constraints $w_i + w_j - 1 \le \sum_{k\in S_{ij}} w_k$, where $S_{ij}$ is an $(i,j)$ node separator. That is, every path from $i$ to $j$ contains at least one node in $S_{ij}$.
Here's a solution with $33$ water nodes:
I suspect that $33$ is optimal, but the best lower bound I have found so far is $26$. If you omit constraint \eqref{1} and thus allow adjacent trees, $23$ is optimal: