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.
