Is "house coloring with three colors" NP?

Question

Consider the problem described here (reproduced below.) Can some better known NP-complete problem be reduced to it?

The problem:

There are a row of houses. Each house can be painted with three colors: red, blue and green. 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. You have to paint the houses with minimum cost. How would you do it?

Note: The cost of painting house 1 red is different from that of painting house 2 red. Each combination of house and color has its own cost.

Answer 1

No, it is not NP-hard (technically, "NP-complete" is the wrong term for this, as this is not a decision problem).

Dynamic programming works, and gives you an O(n) time algorithm. (n is the number of houses).

You maintain three arrays R[1..n], B[1..n], G[1..n], where R[i] is the minimum cost of painting houses 1, 2, 3 ... i such that i is colored Red. Similarly B[i] is min cost of painting 1, 2 ... i with i being colored Blue, and G[i] is with i being colored Green.

You can compute R[i+1]: R[i+1]= (Cost of painting house i+1 Red) + minimum {G[i], B[i]}.

Similarly B[i+1] and G[i+1] can be computed.

Ultimately you take the minimum of R[n], B[n] and G[n].

This is O(n) time and O(n) space.

For example consider the following cost matrix for the houses:

House #: 1   2   3
R      : 1   4   6
G      : 2  100  2
B      : 3  100  4

The algorithm is building the following matrix to get the answer:

Houses : 0  1   2    3
R      : 0  1   6   107
G      : 0  2  101   8
B      : 0  3  101  10

From the last column, where all 3 houses are painted, we can find the minimum cost, which is equal to 8 and corresponds to the combination [Green (2), Red (4), Green (2)].

Quick Python:

# rc = costs of painting red, bc of blue and gc of green.
def min_paint(rc, bc, gc):
    n, i = len(rc), 1
    r, b, g = [0]*n, [0]*n, [0]*n
    r[0], b[0], g[0] = rc[0], bc[0], gc[0]
    while i < n:
        r[i] = rc[i] + min(b[i-1], g[i-1])
        b[i] = bc[i] + min(r[i-1], g[i-1])
        g[i] = gc[i] + min(b[i-1], r[i-1])
        i += 1

    return min(r, b, g)

def main():
    print min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])

if __name__ == "__main__":
    main()

The output will be ([1, 6, 107], [2, 101, 8], [3, 101, 10]), which is a cost matrix leading to the solution.