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

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

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.

  • $\begingroup$ thx, i'll try it out, i'll let you know when i managed to get it working $\endgroup$ – Berty Mar 7 '11 at 7:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.