<p>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 '<a href="http://ttic.uchicago.edu/~cjulia/papers/labeling-journal.pdf">metric labelling</a>'. 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</p>

<p>$$ \sum_{i \in V} c(i, l(i)) + \sum_{(u,v) \in E} d(l(u), l(v)) \cdot w((u,v))$$</p>

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

<p>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. </p>

CC BY-SA 2.5
2011-03-07T07:08:57.430Z
thx, i'll try it out, i'll let you know when i managed to get it working
Berty
CC BY-SA 2.5
2011-03-05T16:32:52.440Z
2011-03-05T16:32:52.440Z
Suresh Venkat
<p>I'm searching for an algorithm that can calculate a suboptimal solution for:</p>

<p>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</p>

<p>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</p>

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

<p>does anyone know a good algorithm  that is powerful enough to solve this?</p>

<p>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</p>

CC BY-SA 2.5
2011-03-05T23:40:20.657Z
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
CC BY-SA 2.5
2011-03-07T07:08:09.960Z
yes i'm looking for an algoritm that gets me a good solution within reasonable time (sub-optimal solution)
Berty
<ds.algorithms><np-hardness><graph-algorithms><graph-colouring>
graph coloring with 3 colors
Berty
# graph coloring with 3 colors

(Asked by: username_0 on 2011-03-05)

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

**Tags:** ds.algorithms, np-hardness, graph-algorithms, graph-colouring

> **Comments:**
> **username_1**: The problem is obviously NP-hard because it includes the 3-colorability problem as a special case.  Are you looking for an approximation algorithm?  
> **username_0**: yes i'm looking for an algoritm that gets me a good solution within reasonable time (sub-optimal solution)  

---

## 1 answers

### Answer by username_2 on 2011-03-05. Score: 6 | Accepted answer

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](http://ttic.uchicago.edu/~cjulia/papers/labeling-journal.pdf)'. 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.

> **Comments:**
> **username_0**: thx, i'll try it out, i'll let you know when i managed to get it working  

---

