# House painting problem where the house row is split and converged back

I am trying to solve a house painting problem: There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs1 is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

This can be solved with dynamic programming (see solution in link house painting). I am trying to solve a very similar problem, but my house row is splitting somewhere in the middle and converging (but sometimes it doesn't), as shown in the picture attached:

Above you can see the problems that I am facing... Can I solve those problems with dynamic programming ? Is there any other solution for those problems ?

• Can you add the problem definition to your question to make it self contained? – Steven Apr 29 '20 at 18:31
• updated the question... – yehudahs Apr 30 '20 at 5:09

## 1 Answer

The problem you described can be solved in polynomial time using dynamic programming whenever the topology of the input houses is a tree (a path is just an even easier special case).

Unless $$P=NP$$, the problem is not solvable in polynomial time when the input instance is a general graph, since the $$k$$-coloring problem can be easily reduced to your problem.

However, in your particular case you are in luck since your input instances can always be decomposed in any of the following ways:

• into $$2$$ paths by deleting two vertices.
• into $$2$$ trees by deleting one vertex.

You can then guess the the color(s) of the deleted house(s) and update the cost matrix of their neighbors so that if a house $$u$$ is adjacent to a deleted house $$v$$ and $$v$$ is colored with color $$c$$, the cost of coloring $$u$$ with $$c$$ will be $$+\infty$$ (effectively ensuring that no optimal solution will color $$u$$ with $$c$$).

If $$k$$ is the number of colors, $$n$$ is the number of houses, and you delete $$2$$ vertices, solving your problem will take time $$O(k^2 \cdot n k) = O(n k^3)$$.

If you delete a single house and solve the problem on the resulting tree, you can reduce the time complexity to $$O(k \cdot nk) = O(n k^2)$$.

To solve the problem on trees in time $$O(n k)$$, root the input tree $$T$$ in an arbitrary vertex $$r$$ and let $$C(u,c)$$ be the cost of coloring vertex $$u$$ with color $$c = \{1, \dots, k\}$$.

Define $$OPT[u,c]$$ as the minimum cost needed to color the subtree of $$T$$ rooted in $$u$$ with the additional constraint that vertex $$u$$ must have a color different from $$c$$.

Then, if $$u$$ is a leaf of $$T$$, you have $$OPT[u,c] = \min_{c' \in \{1, \dots, k\} \setminus c} C(u,c')$$. Otherwise, if $$u$$ is an internal vertex of $$T$$, let $$v_1, \dots, v_h$$ be its children. You have $$OPT[u, c] = \min_{c' \in \{1, \dots, k\} \setminus c} \left( C(u, c') + \sum_{i=1}^h OPT[v_i, c'] \right)$$.

The optimal solution is $$\min\{ OPT[r, 1], OPT[r, 2] \}$$ (since if $$r$$ is not colored with color $$1$$ in an optimal coloring then $$OPT[r, 1]$$ is exactly the minimum cost to color $$T$$, while if $$r$$ is colored with color $$1$$ then it is not colored with color $$2$$ and $$OPT[r, 2]$$ must be the minimum cost needed to color $$T$$).

A similar argument shows that, for each fixed vertex $$u$$, all supbroblems $$OPT[u, c]$$ can be solved in an overall time of $$O(k)$$ (there are only two interesting values of $$c$$). The time complexity follows.

• you can't guess the color of the deleted nodes because, in dynamic programming, the total cost of the next nodes depend with the previous nodes (cost[n][c] = min(cost[n-1][!c]). In addition, the main problem is that different minimum can be taken when calculating the cost of house6, and different minimum can be taken for calculating house5 so the total minimum of the graph was calculated by taken 2 different colors for house4. – yehudahs May 1 '20 at 11:33
• Deleted nodes are... deleted and play no role at all in the dynamic programming. The feasibility of the solution is ensured by changing the costs. From your comment it seems that you want to decompose your instance into paths. As an example, in your first problem you would delete houses 6 and 11. You are left with 2 paths: $P_1$ goes from house 1 to house 9, while $P_2$ goes from house 8 to house 16. You then guess the color $c$ of house 6 and change the cost of paining houses 4 and 8 with $c$ to $+\infty$. You do the same for the color $c'$ of house 11 and change the costs of houses 9 and 13. – Steven May 1 '20 at 12:26
• Finally you solve the subproblems corresponding to $P_1$ and $P_2$ separately, using the known dynamic programming algorithm for paths. Since no house in $P_1$ is adjacent to a house in $P_2$, the colors chosen for the houses in $P_1$ will never conflict with the colors chosen for the houses in $P_2$. The only case in which the coloring of $P_1$ (resp. $P_2$) would not be feasible is that in which a neighbor of house 6 is colored with $c$ (resp. a neighbor of house 11 is colored with $c'$). This is impossible because the corresponding costs have been set to $+\infty$. – Steven May 1 '20 at 12:32
• but if you guess the color for nodes (houses 6 and 11) than you can not be sure to get the minimum cost... cause maybe, if you choose different colors for those nodes the minimum could have changed ... – yehudahs May 1 '20 at 17:12
• Of course you can... there are only $k^2$ choices of the colors $c$ and $c'$ of houses 6 and 11, respectively. One of these $k^2$ guesses must match the colors of the houses in an optimal solution. Solving the problem for each of the $k^2$ guesses takes time time $O(n \cdot k)$, therefore the total time to solve the problem is $O(nk^3)$. – Steven May 1 '20 at 17:15