Радиораскраска в планарных графах: различия между версиями

• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем исполнения) с коэффициентом <math>n^{1/2 - \epsilon} \;</math> (для любого <math>\epsilon > 0 \;</math>), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще.

• Был представлен алгоритм с временем исполнения <math>O(n \Delta (G)) \;</math>, аппроксимирующий минимальный порядок радиораскраски, X_{order_, в планарном графе G ''с константным коэффициентом, который стремится к 2'' по мере возрастания максимальной степени <math>\Delta(G) \;</math> графа G.

Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем <math>O(n^2) \;</math>, предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность алгоритма аппроксимации была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения.

• Наконец, была рассмотрена задача ''оценки количества различных радиораскрасок'' планарного графа G. Это #P-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство быстрой сходимости (см., например, [10]) и представляют ''полностью полиномиальную рандомизированную схему аппроксимации'' для оценки количества радиораскрасок с <math>\lambda \;</math> цветами для планарного графа G, когда <math>\lambda \ge 4 \Delta (G) + 50 \;</math>.

В [8] и [7] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [11] было доказано, что задача раскраски квадрата графа общего вида является NP-полной.

Другая вариация алгоритма радиораскраски для планарных графов под названием ''раскраска на расстоянии 2'' была рассмотрена в [12]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии ''не больше 2'' были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа <math>G (G^2) \;</math>. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является NP-полной. В [5, 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [12] не следует NP-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен алгоритм аппроксимации с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов.

Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней <math>(G^k) \;</math>. В частности, они предложили алгоритм аппроксимации с коэффициентом 1,8 для раскраски квадрата планарного графа более высокой степени <math>(\Delta(G) \ge 749) \;</math>. Их метод использует понятие [[индуктивность|индуктивности]] квадрата планарного графа.

Бодлендер и коллеги [2], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название <math>\lambda</math>-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: [[внешнепланарный граф|внешнепланарных]] графов, [[древесная ширина графа|графов с ограниченной древесной шириной]], [[перестановочный граф|перестановочных]] и [[расщепляемый граф|расщепляемых графов]].