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

<math><math>\lambda</math>-раскраска</math>; <math>k-раскраска</math>; <math>раскраска на расстоянии 2</math>; <math>раскраска квадрата графа</math>

Рассмотрим граф G(V, E). Обозначим для любой пары вершин u, v 2 V за d(u,v) расстояние между u и v в графе G. В общем виде задачу раскраски графа G можно определить следующим образом:

Определение 1 (задача k-раскраски)

Требуется: найти функцию ф : V !f 1..: ; 1g, называемую k-раскраской графа G, такую, что 8U; V 2 V, x 2 f0; 1... kg: если d(u, v) > k - x + 1, то \ф(и) - 0(v)| = x.

Цель: Пусть \<p(V)\ = A#. Тогда A^ - количество цветов, фактически используемых ' (обычно называемое порядком G относительно <p). Количество Уф = тах„еуф(у)—т1пиеуф(и)+ 1 обычно называется диапазоном графа G относительно '. Функция ' удовлетворяет одной из следующих целей:

• минимальный диапазон: Хф является минимальным среди всех возможных функций ' на G;

• минимальный порядок: Yф является минимально возможным среди всех возможных функций ' на G;

• минимальный порядок диапазона: находит минимальный диапазон и затем среди всех присваиваний по минимальному диапазону ' находит минимальный порядок.

• минимальный диапазон порядка: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку ' находит минимальный диапазон.

Отметим, что случай k = 1 соответствует хорошо известной задаче вершинной раскраски графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей радиораскраски.

Определение 2 (задача радиораскраски) (Radiocoloring Problem, RCP [7])

Требуется: найти функцию ф : V ! N*, такую, что \Ф(и) - Ф(у)|   >   2, если d(u, v) = 1, и \Ф(u) - Ф(v)j > 1, если d(u, v) = 2.

Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как Xorder(G). Наименьшее возможное число maxv2V Ф(у) — minu2V Ф(и) + 1 (диапазон), необходимое для радиораскраски G, обозначим как Xspan(G). Функция Ф удовлетворяет одному из следующих условий:

• минимальный диапазон для радиораскраски:  Ф находит минимальный диапазон, т.е. Аф = Xspan(G);

• минимальный порядок для радиораскраски:  Ф находит минимальный порядок v<p = Xorder(G);

• минимальный порядок диапазона для радиораскраски: находит минимальный диапазон и затем среди всех присваиваний по минимальному диапазону Ф находит минимальный порядок.

• минимальный диапазон порядка для радиораскраски: находит минимальный порядок и затем среди всех присваиваний по минимальному порядку Ф находит минимальный диапазон.

Определение 3. Пусть дан граф G(V, E). G2 представляет собой граф с тем же множеством вершин V и множеством ребер E0 : {u, v} 2 E0 в том и только том случае, если d(u, v) < 2 в G.

Еще одна родственная задача заключается в раскраске квадрата графа G, G2, таким образом, чтобы никакие две соседние вершины в G2 не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается /(G2) и называется хроматическим числом квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение Xorder(G) совпадает с (вершинным) хроматическим числом G2, т.е. Xorder(G) = 2.

В работах [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]. В той же работе авторы представили алгоритмы аппроксимации для решения этой задачи для некоторых интересных семейств графов: внешнепланарных графов, графов с ограниченной древесной шириной, перестановочных и расщепляемых графов.