Радиораскраска в планарных графах
Ключевые слова и синонимы
[math]\displaystyle{ \lambda }[/math]-раскраска; k-раскраска; раскраска на расстоянии 2; раскраска квадрата графа
Постановка задачи
Рассмотрим граф G(V, E). Обозначим для любой пары вершин [math]\displaystyle{ u, v \in V \; }[/math] за d(u, v) расстояние между u и v в графе G. В общем виде задачу раскраски графа G можно определить следующим образом:
Определение 1 (задача k-раскраски)
Дано: граф G(V, E).
Требуется: найти функцию [math]\displaystyle{ \phi : V \to \{ 1, ..., \infty \} \; }[/math], называемую k-раскраской графа G, такую, что [math]\displaystyle{ \forall u, v \in V, x \in \{0, 1, ..., k \} \; }[/math]: если [math]\displaystyle{ d(u, v) \ge k - x + 1 \; }[/math], то [math]\displaystyle{ | \phi(u) - \phi(v)| = x \; }[/math].
Цель: Пусть [math]\displaystyle{ | \phi (V) | = \lambda_{ \phi } \; }[/math]. Тогда [math]\displaystyle{ \lambda_{ \phi } \; }[/math] - количество цветов, фактически используемых [math]\displaystyle{ \phi \; }[/math] (обычно называемое порядком G относительно [math]\displaystyle{ \phi \; }[/math]). Количество [math]\displaystyle{ v_{ \phi } = max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \; }[/math] обычно называется диапазоном графа G относительно [math]\displaystyle{ \phi \; }[/math]. Функция [math]\displaystyle{ \phi \; }[/math] удовлетворяет одной из следующих целей:
• минимальный диапазон: [math]\displaystyle{ \lambda_{ \phi } \; }[/math] является минимально возможным среди всех возможных функций [math]\displaystyle{ \phi \; }[/math] на G;
• минимальный порядок: [math]\displaystyle{ v_{ \phi } \; }[/math] является минимально возможным среди всех возможных функций [math]\displaystyle{ \phi \; }[/math] на G;
• минимальный порядок диапазона: находим минимальный диапазон, и затем среди всех присваиваний по минимальному диапазону [math]\displaystyle{ \phi \; }[/math] находит минимальный порядок.
• минимальный диапазон порядка: находим минимальный порядок, и затем среди всех присваиваний по минимальному порядку [math]\displaystyle{ \phi \; }[/math] находит минимальный диапазон.
Отметим, что случай k = 1 соответствует хорошо известной задаче вершинной раскраски графа. Таким образом, задача k-раскраски (где k служит входным параметром) является NP-полной [4]. В случае, когда k = 2, задача k-раскраски называется задачей радиораскраски.
Определение 2 (задача радиораскраски) (Radiocoloring Problem, RCP [7])
Дано: граф G(V, E).
Требуется: найти функцию [math]\displaystyle{ \Phi : V \to N^* \; }[/math], такую, что [math]\displaystyle{ | \Phi (u) - \Phi (v) | \ge 2 \; }[/math], если d(u, v) = 1, и [math]\displaystyle{ | \Phi (u) - \Phi (v) | \ge 1 \; }[/math], если d(u, v) = 2.
Цель: наименьшее возможное число (порядок), необходимое для радиораскраски G, обозначим как [math]\displaystyle{ X_{order}(G) \; }[/math]. Наименьшее возможное число [math]\displaystyle{ max_{v \in V } \phi (v) - min_{ u \in V } \phi (u) + 1 \; }[/math] (диапазон), необходимое для радиораскраски G, обозначим как [math]\displaystyle{ X_{span}(G) \; }[/math]. Функция [math]\displaystyle{ \Phi \; }[/math] удовлетворяет одному из следующих условий:
• минимальный диапазон для радиораскраски: [math]\displaystyle{ \Phi \; }[/math] находит минимальный диапазон, т.е. [math]\displaystyle{ \lambda_{ \Phi } = X_{span}(G) \; }[/math];
• минимальный порядок для радиораскраски: [math]\displaystyle{ \Phi \; }[/math] находит минимальный порядок [math]\displaystyle{ v_{ \Phi} = X_{order}(G) \; }[/math];
• минимальный порядок диапазона для радиораскраски: находим минимальный диапазон, и затем среди всех присваиваний по минимальному диапазону [math]\displaystyle{ \Phi \; }[/math] находит минимальный порядок.
• минимальный диапазон порядка для радиораскраски: находим минимальный порядок, и затем среди всех присваиваний по минимальному порядку [math]\displaystyle{ \Phi \; }[/math] находит минимальный диапазон.
Родственная радиораскраске задача относится к квадрату графа G, который определяется следующим образом:
Определение 3. Пусть дан граф G(V, E). Квадрат графа G, [math]\displaystyle{ G^2 \; }[/math], представляет собой граф с тем же множеством вершин V и множеством ребер [math]\displaystyle{ E': \{ u, v \} \in E' \; }[/math] в том и только том случае, если [math]\displaystyle{ d(u, v) \le 2 \; }[/math] в G.
Родственная задача заключается в раскраске квадрата графа G, [math]\displaystyle{ G^2 \; }[/math], таким образом, чтобы никакие две соседние вершины в [math]\displaystyle{ G^2 \; }[/math] не были раскрашены в один цвет. Целью является использование минимального числа цветов, которое обозначается [math]\displaystyle{ \chi (G^2) \; }[/math] и называется хроматическим числом квадрата графа G. В [5, 6] было впервые замечено, что для любого графа G значение [math]\displaystyle{ X_{order}(G) \; }[/math] совпадает с (вершинным) хроматическим числом [math]\displaystyle{ G^2 \; }[/math], т.е.[math]\displaystyle{ X_{order}(G) = \chi (G^2) \; }[/math].
Основные результаты
В работах [5, 6] исследовались задачи нахождения минимального порядка диапазона, минимального диапазона и минимального порядка для радиораскраски в планарном графе G. Планарным называется граф, ребра которого могут быть уложены на плоскости без пересечений. Были получены следующие результаты:
• Вначале было показано, что количество цветов, используемое при нахождении минимального порядка диапазона для радиораскраски графа G, отличается от хроматического числа квадрата этого графа – [math]\displaystyle{ \chi (G^2) \; }[/math]. В частности, оно может быть больше [math]\displaystyle{ \chi (G^2) \; }[/math].
• Затем было доказано, что задача радиораскраски для графов общего вида с трудом поддается аппроксимации (за исключением случая NP = ZPP – класса задач с рандомизированными алгоритмами с нулевой ошибкой и полиномиальным временем выполнения) с коэффициентом [math]\displaystyle{ n^{1/2 - \epsilon} \; }[/math] (для любого [math]\displaystyle{ \epsilon \gt 0 \; }[/math]), где n – количество вершин графа. Однако при рассмотрении некоторых специальных разновидностей графов задача становится проще.
Было показано, что задачи нахождения минимального диапазона и минимального порядка диапазона для радиораскраски являются NP-полными для планарных графов. Заметим, что некоторые комбинаторные задачи остаются сложными и для планарных графов, притом доказать их сложность также непросто, поскольку при этом необходимо использовать «планарные приспособления», сложные для нахождения и понимания.
• Был представлен алгоритм с временем выполнения [math]\displaystyle{ O(n \Delta (G)) \; }[/math], аппроксимирующий минимальный порядок радиораскраски, [math]\displaystyle{ X_{order} \; }[/math], в планарном графе G с константным коэффициентом, который стремится к 2 по мере возрастания максимальной степени [math]\displaystyle{ \Delta(G) \; }[/math] графа G.
Представленный алгоритм вдохновлен теоремой Хёвела и Макгиннеса о конструктивной раскраске [9]. Построение из [9], как показано, может привести к получению алгоритма с временем [math]\displaystyle{ O(n^2) \; }[/math], предполагая, что планарное вложение графа G задано. В [5, 6] временная сложность аппроксимационного алгоритма была улучшена, также был представлен намного более простой алгоритм для проверки и внедрения, не требующий на входе планарного вложения.
• Наконец, была рассмотрена задача оценки количества различных радиораскрасок планарного графа G. Это NP-полная задача (что можно легко заметить в связи с представленным в данных работах способом редукции полноты, которая может быть выполнена консервативным образом). Авторы применяют здесь стандартную технику, сочетая цепи Маркова и новый способ формирования пар, чтобы получить доказательство быстрой сходимости (см., например, [10]) и представляют полностью полиномиальную рандомизированную аппроксимационную схему для оценки количества радиораскрасок с [math]\displaystyle{ \lambda \; }[/math] цветами для планарного графа G, когда [math]\displaystyle{ \lambda \ge 4 \Delta (G) + 50 \; }[/math].
В [8] и [7] было доказано, что задача нахождения минимального диапазона для радиораскраски является NP-полной даже для графов диаметра 2. При редукции активно используются непланарные графы. В [12] было доказано, что задача раскраски квадрата графа общего вида является NP-полной.
Другая вариация алгоритма радиораскраски для планарных графов под названием раскраска на расстоянии 2 была рассмотрена в [12]. Задача заключается в раскраске графа G минимальным количеством цветов таким образом, чтобы вершины на расстоянии не больше 2 были раскрашены в разные цвета. Отметим, что эта задача эквивалентна задаче раскраски квадрата графа [math]\displaystyle{ G \; (G^2) }[/math]. В [11] было доказано, что задача раскраски на расстоянии 2 для планарных графов является NP-полной. В [5, 6] было показано, что эта задача отличается от задачи поиска минимального порядка диапазона для радиораскраски графа. Таким образом, из доказательства NP-полноты в [12] не следует NP-полнота задачи поиска минимального порядка диапазона для радиораскраски графа, доказанная в [5, 6]. В [12] также был предложен аппроксимационный алгоритм с коэффициентом 9 для раскраски на расстоянии 2 для планарных графов.
Независимо и параллельно в своей работе [1] Агнарссон и Хальдорссон представили аппроксимационные алгоритмы для нахождения хроматического числа в квадратах графов и в графах более высоких степеней [math]\displaystyle{ (G^k) \; }[/math]. В частности, они предложили аппроксимационный алгоритм с коэффициентом 1,8 для раскраски квадрата планарного графа более высокой степени [math]\displaystyle{ (\Delta(G) \ge 749) \; }[/math]. Их метод использует понятие индуктивности квадрата планарного графа.
Бодлендер и коллеги [2], также независимо и параллельно, доказали, что задача нахождения минимального диапазона для радиораскраски, которой они дали название [math]\displaystyle{ \lambda }[/math]-разметки, является NP-полной для планарных графов, используя подход, близкий к описанному в [5, 6]. В той же работе авторы представили аппроксимационные алгоритмы для решения этой задачи для некоторых интересных семейств графов: внешнепланарных графов, графов с ограниченной древесной шириной, перестановочных и расщепляемых графов.
Применение
Интересная и хорошо изученная задача распределения частот (Frequency Assignment Problem, FAP) в радиосетях ставит целью распределение частот по передатчикам с возможностью повторного использования частоты с сохранением приемлемого уровня интерференции сигналов. Интерференцию между передатчиками моделирует граф интерференции G(V, E), где V (|V| = n) соответствует множеству передатчиков, а элементы E представляют ограничения по расстоянию (например, если две соседних вершины в G получают одну и ту же частоту или близкие частоты, это приводит к возникновению неприемлемого уровня интерференции). В большинстве реальных ситуаций топология образовавшейся сети обладает некоторыми специальными свойствами, к примеру, G может представлять собой решетчатую сеть или планарный граф. Планарным графам посвящено большинство исследований в работах [5, 6].
Задача FAP обычно моделируется каким-либо вариантом задачи раскраски графа, в которой множество цветов представляет доступные частоты. Кроме того, каждый цвет в конкретном эпизоде распределения частоты получает целочисленное значение, которое должно удовлетворять определенным неравенствам, связывающим его со значениями цветов ближайших соседей в графе G (ограничения по расстоянию между частотами). Дискретной версией FAP является задача k-раскраски графа, версия которой для k = 2 была изучена в [5, 6].
В реальных сетях выделяются полосы (диапазоны частот), а не отдельные частоты. В этом случае задача распределения частот стремится использовать минимально возможные диапазоны. Иногда желательно использовать минимально возможное количество отдельных частот заданного диапазона, поскольку неиспользованные частоты становятся доступными для других вариантов использования. Однако существуют случаи, когда первоочередной целью является минимизация количества используемых частот, а минимальный диапазон – только вторая цель, поскольку мы хотим избежать резервирования неоправданно большого диапазона. Эти реалистичные сценарии мотивировали исследователей к рассмотрению вариантов оптимизации задачи радиораскраски графа, которые в процессе распределения частот должны минимизировать диапазон (полосу частот) или порядок (отдельные используемые частоты). Такие задачи оптимизации исследовались в работах [5, 6].
См. также
Литература
1. Agnarsson, G., Halldorsson, M.M.: Coloring Powers of Planar Graphs. In: Proceedings of the 11th Annual ACM-SIAM symposium on Discrete algorithms, pp. 654-662 (2000)
2. Bodlaender, H.L., Kloks, T., Tan, R.B., van Leeuwen, J.: Approximations for A-Coloring of Graphs. In: Proceedings of the 17th Annual Symposium on Theoretical Aspects of Computer Science. Lecture Notes in Computer Science, vol. 1770, pp. 395-406. Springer (2000)
3. Hale, W.K.: Frequency Assignment: Theory and Applications. In: Proceedings of the IEEE, vol. 68, number 12, pp. 1497-1514 (1980)
4. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman and Co. (1979)
5. Fotakis, D., Nikoletseas, S., Papadopoulou, V., Spirakis, P.: NP-Completeness Results and Efficient Approximations for Radio-coloring in Planar Graphs. In: Proceedings of the 25th International Symposium on Mathematical Foundations of Computer Science, Lecture Notes of Computer Science, vol. 1893, pp. 363-372. Springer (2000)
6. Fotakis, D., Nikoletseas, S., Papadopoulou, V.G., Spirakis, P.G.: Radiocoloring in Planar Graphs: Complexity and Approximations. Theor. Comput. Sci. Elsevier 340, 514-538 (2005)
7. Fotakis, D., Pantziou, G., Pentaris, G., Spirakis, P.: Frequency Assignment in Mobile and Radio Networks. In: Networks in Distributed Computing, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 45, pp. 73-90 (1999)
8. Griggs, J., Liu, D.: Minimum Span Channel Assignments. In: Recent Advances in Radio Channel Assignments, Invited Minisymposium, Discrete Mathematics (1998)
9. van d. Heuvel, J., McGuiness, S.: Colouring the Square of a Planar Graph. CDAM Research Report Series, July 1999
10. Jerrum, M.: A very simple Algorithm for Estimating the Number of k-colourings of a Low Degree Graph. Random Struct. Algorithms 7,157-165 (1994)
11. Lin, Y.L., Skiena, S.: Algorithms for Square Roots of Graphs. SIAM J. Discret. Math. 8,99-118 (1995)
12. Ramanathan, S., Loyd, E.R.: The Complexity of Distance 2-Coloring. In: Proceedings of the 4th International Conference of Computing and Information, pp. 71-74 (1992)