# graph coloring with 3 colors

I'm searching for an algorithm that can calculate a suboptimal solution for:

color a graph with 3 colors some vertices already have a color and can't be changed the edges have values and the algorithm has to search for a solution where the sum of all the values of all the edges with vertices with the same color is smallest

this is for a practical problem: a wireless network with wireless accesspoints (vertices) you can ask the accespoints what neighbors they see and with what signal strength and i can create a graph out of that information some accespoints are not part of the network, and already have a channel assigned

and accespoint can only have 3 channels that don't interfere (1,6,11) these are the 3 colors

does anyone know a good algorithm that is powerful enough to solve this?

i heard this was used somewhere in cpu theory, where registers are already filled in (colored) and you need to assign registers to some programs (colors) but i can't find it

• The problem is obviously NP-hard because it includes the 3-colorability problem as a special case. Are you looking for an approximation algorithm? – Tsuyoshi Ito Mar 5 '11 at 23:40
• yes i'm looking for an algoritm that gets me a good solution within reasonable time (sub-optimal solution) – Berty Mar 7 '11 at 7:08

The variant of the problem you're referring to is very close to a problem called the $0$-extension problem: it's a special case of a class of problems called 'metric labelling'. In this class of problems, you're given a weighted graph $G = (V, E, w)$, a set of labels $L$, an assignment cost of labels to vertices $c : V \times L \rightarrow R$, and a "discrepancy cost" $d : L \times L \rightarrow R$. The goal is to assign labels to vertices so as to minimize the sum of the assignment costs and the discrepancy cost for the labels on an edge (weighted by the edge weight). In short, find a labelling $l : V \rightarrow L$ to minimize
$$\sum_{i \in V} c(i, l(i)) + \sum_{(u,v) \in E} d(l(u), l(v)) \cdot w((u,v))$$