Дано k-раскраска вершин графа (k-1) -краска

Question

Общеизвестно, что окрашивающие вершины графа NP-полны. Известно также, что существуют эффективные жадные алгоритмы, которые могут получить приблизительное решение. Почему бы не использовать эти рандомизированные жадные алгоритмы для расчета цвета с k цветами, а затем использовать некоторые более медленные алгоритмы для уменьшения k?

В моей ситуации я знаю минимальное количество цветов, достаточных для цветного графа G - назовем его K. Мне также удалось реализовать алгоритм SL, который дал мне (K + 2) -цвет. Один цвет использовался только для окраски одной вершины, поэтому мне удалось удалить ее, вручную перекрасив некоторые другие узлы. Поэтому у меня есть (K + 1) -коррекция и хотелось бы написать алгоритм, который бы уменьшил K (или, скорее, K + 1) на 1.

Я попытался сделать это вручную - я нашел цвет, который используется в минимальном количестве вершин, окрашенных одним и тем же цветом, и уменьшает использование этого цвета до 3. Я должен перекрасить только 3 узла.

Одна из идей - сделать 3 рекурсивных вызова - по одному для каждого плохого цвета. Давайте проанализируем, что рекурсивная функция должна была бы выполнить для узла v. Он должен был бы проверять каждый цвет отдельно от цвета v и того, который мы хотели бы удалить. Поэтому для каждого цвета c он должен установить цвет v в c и сделать рекурсивный вызов для каждого узла, который является соседом v и имеет цвет c. После проверки всех цветов мы должны получить старый цвет v и снова установить его. Еще одна оптимизация может не пытаться изменить цвет v на тот, который больше, чем у его соседей (поскольку дерево рекурсии будет слишком глубоким), но для слишком маленького x он вообще не сможет изменить цвет.

Другая идея - проверить узлы, цвет которых можно изменить (а не цвет, который мы хотим удалить), чтобы он не сталкивался с цветами соседей. И сделайте рекурсивные вызовы для изменения цветов других узлов, пока один цвет, который мы хотим удалить, будет перекрашен.

Вот моя реализация первого алгоритма, который был предназначен для работы на п < 90, но, кажется, не до конца (500 минут исполнения):

#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; 
} 

Любые идеи, как сделать это быстрее?

Answer 1

Я только кратко просмотрел код и прочитал ваше объяснение, но, похоже, вы попадаете в бесконечный цикл, переключаясь между соседями. Вам нужно будет сохранить флаг в каждом узле, чтобы отметить, что он в настоящее время перекрашивается, и только рекурсия в тех соседей, которые в настоящее время не перекрашены.

Однако - этот алгоритм выглядит как экспоненциальный в худшем случае - и я уверен, что есть случаи, когда цветной график K не может быть перекрашен в граф K-1, не меняя какую-либо значительную часть графиков, даже если количество узлов цвета K равно 1.

Вот пример Графа с простой топологией. Ясно, что он может быть двухцветным (R, G), и мы имеем трехцветную версию, используя (R, G, B). Единственный способ правильно его перекрасить - это изменить примерно 1/2 цвета узлов, в результате получив одну из других версий ниже. () обозначает единственный узел цвета B, а [] обозначает разделы, которые необходимо перекрасить.

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] 

Это означает, что минимальная глубина вашего (потенциально экспоненциального) поиска может быть более чем на 1/2 числа узлов. Это может убивать разумные времена выполнения (или может не зависеть от топологии графиков, которые, как я полагаю.)