graph coloring with 3 colors

Question

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

Answer 1

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))$$

In your problem, the assignment cost is zero, and the label "discrepancy" function is the delta function on labels.

One complicating factor here is that the metric labelling family of problems, the label discrepancy is usually a distance, whereas here it's a similarity measure.