Considere el problema descritoaquí (reproducido a continuación). ¿Se puede reducir a él algún problema NP-completo mejor conocido?

El problema:

Hay una hilera de casas. Cada casa puede pintarse con tres colores: rojo, azul y verde. El costo de pintar cada casa con un color determinado es diferente. Tienes que pintar todas las casas de modo que no haya dos casas adyacentes que tengan el mismo color. Tienes que pintar las casas con un costo mínimo. ¿Como lo harias?

Nota: El costo de pintar la casa 1 roja es diferente del de pintar la casa 2 roja. Cada combinación de casa y color tiene su propio costo.