Given k-coloring of graph's vertices calculate (k-1)-coloring

Question

It's a common knowledge that coloring vertices of a graph is NP-complete. It's also known that there are efficient greedy algorithms that can get an approximate solution. Why not use these randomized greedy algorithms to calculate a coloring with k colors and then use some slower algorithms to reduce k?

In my situation I know the minimal number of colors that are sufficient to color graph G - let's call it K. I've also managed to implement SL algorithm which gave me (K+2)-coloring. One color was used only to color one vertex so I managed to remove it by manually recoloring some other nodes. Therefore, I have (K+1)-coloring and would like to write an algorithm that would reduce K (or rather K+1) by 1.

I've tried to do it manually - I found a color that is used in the minimal number of vertices colored by the same color and reduced this color's uses to 3. I have to recolor only 3 nodes.

One idea is to make 3 recursive calls - one for each badly colored nodes. Let's analyze what the recursive function would have to do for node v. It would have to check every color apart from v's color and the one we'd like to remove. So for each color c it should set v's color to c and make a recursive call for each node which is a neighbour of v and has color c. After checking all colors we should retrieve v's old color and set it again. One more optimisation may be not trying to change v's color to one that more than x of his neighbours has (as the recursion tree would be too deep) - but for too small x it may not be able to change the color at all.

Another idea is to check nodes whose color can be changed (not to a color that we want to remove) so that it wouldn't collide with neighbours' colors. And make recursive calls to change other nodes' colors until one color which we want to remove will be recolored.

Here's my implementation of the first algorithm which was intended to work for n < 90 but doesn't seem to end (500 minutes of execution):

#include<stdio.h>
#include<assert.h>
#include<vector>
using namespace std;

vector<int> graph[99];
int hash[10009], color[99];
const int colors = 9, color_to_change = 7;

void change_color(int v)
{
    int tmp = color[v], count;
    for(int i = 1; i <= colors; ++i)
    {
        count = 0;
        for(int j = 0; j < graph[v].size(); ++j)
            count += color[graph[v][j]] == i;
        if(!count)
        {
            color[v] = i;
            return;
        }
        if(count < 4 && i != color_to_change && i != color[v])
        {
            color[v] = i;
            for(int j = 0; j < graph[v].size(); ++j)
                if(color[graph[v][j]] == i)
                    change_color(graph[v][j]);
        }
    }
    color[v] = tmp;
}

int main()
{
    int n, m, a, b, max = 0, j = -1;

    scanf("%d%d", &n, &m);
    while(m--)
    {
        scanf("%d%d", &a, &b);
        assert(a != b);
        if(hash[a*100+b] || hash[b*100+a])
            continue;
        assert(a*100+b < 10000 && b*100+a < 10000);
        hash[a*100+b] = hash[b*100+a] = 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    for(int i = 1; i <= n; ++i)
        scanf("%d", &color[i]);
    for(int i = 1; i <= n; ++i)
        if(color[i] == color_to_change)
            change_color(i);
    for(int i = 1; i <= n; ++i)
        printf("%d ", color[i]);
    return 0;
}

Any ideas how to make it faster?

Answer 1

I've only looked at the code briefly, and read your explaination, but it seems you get into an infinite loop with switching back and forth between neighbours. You'll need to store a flag in each node to note that it's currently being recoloured, and only recurse into those neighbours that are not currently being recoloured.

However - this algorithm looks like its exponential in the worst case - and I'm pretty sure there are cases where a K coloured graph can not be recoloured to a K-1 graph without changing some large fraction of the graphs, even if the number of nodes of colour K is only 1.

Here's an example Graph with simple topology. Its clear that it can be two coloured (R,G), and we have a three colour version using (R,G,B). The only way to recolour it correctly is to change approximately 1/2 the nodes colours, ending up with one of the other versions below. () denotes the single node of colour B, and [] denotes the sections that need to get recoloured.

3 colour version  :  R-G-R-G-R-G-(B)-R-G-R-G-R-G-R
2 colour version 1: [R-G-R-G-R-G- R]-G-R-G-R-G-R-G
2 colour version 2:  G-R-G-R-G-R-[G -R-G-R-G-R-G-R]

This means the minimum depth of your (potentially exponential) search may be more than 1/2 the number of nodes. This may kill sensible performance times (or may not depending on the topology of the graphs I guess.)