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

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

it's mutual knowledge coloring vertices of graph np-complete. it's known there efficient greedy algorithms can approximate solution. why not utilize these randomized greedy algorithms calculate coloring k colors , utilize slower algorithms cut down k?

in situation know minimal number of colors sufficient color graph g - let's phone call k. i've managed implement sl algorithm gave me (k+2)-coloring. 1 color used color 1 vertex managed remove manually recoloring other nodes. therefore, have (k+1)-coloring , write algorithm cut down k (or rather k+1) 1.

i've tried manually - found color used in minimal number of vertices colored same color , reduced color's uses 3. have recolor 3 nodes.

one thought create 3 recursive calls - 1 each badly colored nodes. let's analyze recursive function have node v. have check every color apart v's color , 1 we'd remove. each color c should set v's color c , create recursive phone call each node neighbour of v , has color c. after checking colors should retrieve v's old color , set again. 1 more optimisation may not trying alter v's color 1 more x of neighbours has (as recursion tree deep) - little x may not able alter color @ all.

another thought check nodes color can changed (not color want remove) wouldn't collide neighbours' colors. , create recursive calls alter other nodes' colors until 1 color want remove recolored.

here's implementation of first algorithm intended work n < 90 doesn't seem end (500 minutes of execution):

class="lang-cpp prettyprint-override">#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 = 1; <= 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 && != color_to_change && != 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 = 1; <= n; ++i) scanf("%d", &color[i]); for(int = 1; <= n; ++i) if(color[i] == color_to_change) change_color(i); for(int = 1; <= n; ++i) printf("%d ", color[i]); homecoming 0; }

any ideas how create faster?

i've looked @ code briefly, , read explaination, seems infinite loop switching , forth between neighbours. you'll need store flag in each node note it's beingness recoloured, , recurse neighbours not beingness recoloured.

however - algorithm looks exponential in worst case - , i'm pretty sure there cases k coloured graph can not recoloured k-1 graph without changing big fraction of graphs, if number of nodes of colour k 1.

here's illustration graph simple topology. clear can 2 coloured (r,g), , have 3 colour version using (r,g,b). way recolour correctly alter approximately 1/2 nodes colours, ending 1 of other versions below. () denotes single node of colour b, , [] denotes sections need 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 minimum depth of (potentially exponential) search may more 1/2 number of nodes. may kill sensible performance times (or may not depending on topology of graphs guess.)

algorithm optimization recursion np-complete graph-coloring