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

Требуется: найти функцию <math>\phi : V \to \{ 1, ..., \infty \} \;</math>, называемую ''k-раскраской графа'' G, такую, что <math>\forall u, v \in V, x \in \{0, 1, ..., k \} \;</math>: если <math>d(u, v) \ge k - x + 1 \;</math>, то <math>| \phi(u) - \phi(v)| = x \;</math>.

• минимальный диапазон: <math>\lambda_{ \phi } \;</math> является минимальным среди всех возможных функций <math>\phi \;</math> на G;

'''Определение 3.''' Пусть дан граф G(V, E). <math>G^2 \;</math> представляет собой граф с тем же множеством вершин V и множеством ребер <math>E': \{ u, v \} \in E' \;</math> в том и только том случае, если <math>d(u, v) \le 2 \;</math> в G.

Родственная задача заключается в раскраске квадрата графа G, <math>G^2 \;</math>, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается <math>\chi (G^2) \;</math> и называется [[хроматическое число|хроматическим числом]] квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение <math>X_{order}(G) \;</math> совпадает с (вершинным) хроматическим числом <math>G^2 \;</math>, т.<math>е. X_{order}(G) = \chi (G^2) \;</math>.

В работах [5, 6] исследовались задачи нахождения минимального порядка диапазона, минимального диапазона и минимального порядка для радиораскраски в планарном графе G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты:

• Вначале было показано, что количество цветов, используемое при нахождении минимального порядка диапазона для радиораскраски графа G, отличается от хроматического числа квадрата этого графа –/(G2). В частности, оно может быть больше /(G2).

• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая 34T = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем исполнения) с коэффициентом nll2~€ (для любого e > 0), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще.

• Был представлен алгоритм с временем исполнения O{nA{G)), аппроксимирующий минимальный порядок радиораскраски, Xorder, в планарном графе G с константным коэффициентом, который стремится к 2 по мере возрастания максимальной степени A(G) графа G.

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

• Наконец, была рассмотрена задача оценки количества различных радиораскрасок планарного графа G. Это #P-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство быстрой сходимости (см., например, [10]) и представляют полную полиномиальную рандомизированную схему аппроксимации для оценки количества радиораскрасок с Я цветами для планарного графа G, когда Я > AA{G) + 50.

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

Другая вариация алгоритма радиораскраски для планарных графов под названием «раскраска на расстоянии 2» была рассмотрена в [ ]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии не больше 2 были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа G – G2. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является 34 T-полной. В [5 , 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [ ] не следует 34 T-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен алгоритм аппроксимации с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов.

Независимо и параллельно в своей работе [ ] Агнарссон и Хальдорссон представили алгоритмы аппроксимации для нахождения хроматического числа в квадратах графов и в графах более высоких степеней (Gk). В частности, они предложили алгоритм аппроксимации с коэффициентом 1:8 для раскраски квадрата планарного графа более высокой степени (A(G) > 749). Их метод использует понятие индуктивности квадрата планарного графа.

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