Распределенный алгоритм раскраски вершин
Ключевые слова и синонимы
Раскраска вершин; распределенные вычисления
Постановка задачи
Задача раскраски вершин принимает на вход неориентированный граф G := (V, E) и вычисляет раскраску вершин, т.е функцию [math]\displaystyle{ c: V \to [k] }[/math] от некоторого целого положительного значения k, такую, что смежным вершинам присваиваются разные цвета (иначе говоря, [math]\displaystyle{ c(u) \ne c(v) }[/math] для всех [math]\displaystyle{ (u, v) \in E }[/math]). В задаче [math]\displaystyle{ (\Delta + 1) }[/math]-раскраски вершин значение k равно [math]\displaystyle{ (\Delta + 1) }[/math], где [math]\displaystyle{ \Delta }[/math] – максимальная степень входного графа G. В общем случае [math]\displaystyle{ (\Delta + 1) }[/math] цветов должно быть достаточно, как показывает случай с кликой. Однако, если граф удовлетворяет определенным свойствам, возможна его раскраска при помощи намного меньшего числа цветов. Нахождение минимально возможного количества цветов представляет собой вычислительно сложную задачу, соответствующие проблемы разрешимости являются NP-полными [5]. В задаче раскраски Брукса-Визинга цель заключается в нахождении раскрасок, близких к оптимальной.
В данной статье рассматривается модель вычислений в виде синхронной структуры передачи сообщений, используемой в стандартных распределенных вычислениях [11]. Далее будут описаны самые простые алгоритмы, которые могут быть легко реализованы на базе этой распределенной модели и при этом являются эффективными с точки зрения количества необходимых раундов выполнения и качественными – с точки зрения количества используемых цветов. Для достижения достаточной эффективности количество раундов должно быть полилогарифмическим относительно числа вершин графа n, а для достижения достаточного качества количество использованных цветов должно быть близким к оптимальному.
Основные результаты
Основные теоретические результаты, связанные с распределенным [math]\displaystyle{ (\Delta + 1) }[/math]-раскрашиванием вершин, вывели Лаби [9] и Джоханссон [7]. Оба показали, как вычислить [math]\displaystyle{ (\Delta + 1) }[/math]-раскраску за O(log n) раундов с высокой вероятностью. Для раскраски Брукса-Визинга Ким [8] показал, что если в графе нет квадратов или треугольников, то его можно раскрасить при помощи [math]\displaystyle{ O(\Delta / log \; \Delta) }[/math] цветов. Если при этом граф является регулярным с достаточно высокой степенью [math]\displaystyle{ (\Delta \gg lg \; n) }[/math], для такого случая Грэбл и Панконези [6] показали, как раскрасить его с помощью [math]\displaystyle{ O(\Delta / log \; \Delta) }[/math] цветов за O (log n) раундов. Исчерпывающее обсуждение вероятностных техник достижения подобного раскрашивания см. в работе [10].
Финокки, Панконези и Сильвестри провели комплексный экспериментальный анализ распределенных алгоритмов раскрашивания вершин, аналогичных упомянутым в этих работах, на разных классах графов. Результаты представлены в разделе «Экспериментальные результаты», а использованные наборы данных – в разделе «Наборы данных».
Применение
Раскраска вершин является базовым примитивом многих приложений; классическим примером являются задачи планирования в присутствии множества попарных ограничений на одновременное выполнение заданий. Например, при составлении расписания занятий в университете два курса, которые ведет один и тот же преподаватель, нельзя поставить на один и тот же временной интервал. Аналогичным образом два курса, предназначенные для одной и той же группы студентов, также не должны конфликтовать друг с другом. Задача определения минимального количества требуемых временных интервалов с учетом этих ограничений может рассматриваться как задача раскраски вершин. Еще одним распространенным приложением является распределение регистров. Задача распределения регистров заключается в присвоении переменных ограниченному числу аппаратных регистров в процессе выполнения программы. Доступ к переменным в регистрах осуществляется намного быстрее, чем к переменным, не хранящимся в регистрах. Однако в большинстве случаев регистров намного меньше, чем переменных, так что приходится одному регистру назначать несколько переменных. Переменные конфликтуют друг с другом, если одна из них используется одновременно перед и после второй в течение короткого периода времени (например, при выполнении подпрограммы). Задача заключается в присвоении переменных, не конфликтующих друг с другом, с целью минимизации использования других видов памяти. Простой подход к ее решению состоит в создании графа, вершины которого представляют переменные, а ребра – конфликты между ними. Раскраска в этом случае представляет бесконфликтное присваивание. Если количество использованных цветов меньше количества регистров, то бесконфликтное присваивание оказывается возможным. Среди современных вариантов применения можно упомянуть присвоение частот мобильным радиостанциям и другим пользователям электромагнитного спектра. В самом простом случае двум клиентам, находящимся достаточно близко друг от друга, необходимо назначить разные частоты, тогда как далекие друг от друга клиенты могут использовать одну частоту. Задача минимизации количества частот также сводится к задаче раскраски вершин. Другие примеры приложений и ссылки см. на странице Майкла Трика, посвященной раскраске [12].
Открытые вопросы
Экспериментальный анализ убедительно и несколько неожиданно показывает, что самая простая и тривиальная версия алгоритма на деле оказывается и самой эффективной! В частности, она значительно превосходит эффективностью другие тщательно проанализированные алгоритмы. Финокки, Панконези и Сильвестри предложили эвристические рекуррентности, объясняющие высокую эффективность тривиального алгоритма. Строгое обоснование этих рекуррентностей остается сложным и интересным открытым вопросом. Могут быть полезны альтернативные и менее привлекательные строгие аргументы, доказывающие, что тривиальный алгоритм превосходит эффективностью алгоритмы, проанализированные Лаби и Джоханссоном. Другие вопросы касательно того, как локальная структура графа влияет на эффективность таких алгоритмов (отчасти затронутые выше), заслуживают дальнейшего экспериментального и теоретического анализа.
Экспериментальные результаты
Все проанализированные алгоритмы начинают работу с присвоения исходной палитры цветов каждой вершине и последующего повторения простого раунда итерации:
1. Проснись!: каждая вершина независимо от остальных просыпается с определенной вероятностью участия в раскраске на этом раунде.
2. Попытайся!: каждая вершина независимо от остальных выбирает предварительный цвет из палитры, доступной на этом раунде.
3. Устрани конфликты!: если ни одна из соседних вершин не выбрала тот же предварительный цвет, то он становится окончательным. Такая вершина более не рассматривается алгоритмом, остальные вершины соответствующим образом корректируют свои палитры. Если возникает конфликт, он разрешается одним из двух способов: либо все конфликтующие вершины признаются неуспешными и переходят на следующий раунд, либо с помощью так называемой венгерской эвристики среди всех вершин, выбравших один и тот же цвет, вычисляется независимое множество. Вершины независимого множества получают окончательные цвета и выбывают из рассмотрения. Венгерская эвристика для независимого множества рассматривает вершины в произвольном порядке, удаляя всех соседей встретившейся вершины, которая, в свою очередь, добавляется к независимому множеству. См. в [1, p. 91] подробный анализ этой эвристики для доказательства теоремы Турана.
4. Накорми голодных!: если в палитре вершины заканчиваются цвета, ей присваиваются новые свежие цвета.
В этой базовой схеме могут варьироваться несколько параметров, самыми значимыми из которых являются вероятность пробуждения, способы разрешения конфликтов и размер исходной палитры.
В алгоритме [math]\displaystyle{ (\Delta + 1) }[/math]-раскраски исходная палитра для вершины v задается множеством [math]\displaystyle{ [\Delta] := \{ 1, ..., \Delta + 1 \} }[/math] (глобальная настройка) или [d(v) + 1], где d(v) – степень вершины v (локальная настройка). Экспериментальные результаты свидетельствуют о том, что (1) наилучшая вероятность пробуждения равна 1, (2) во время выполнения локальная версия палитры оказывается не хуже глобальной, но может обеспечить значительную экономию цветов, (3) венгерская эвристика, применяемая не к случайным числам, а к идентификаторам вершин, дает хорошие результаты.
В раскраске Брукса-Визинга исходная палитра задается значением [d(v)/s], где s – коэффициент стягивания. Экспериментальные результаты свидетельствуют о том, что оптимальную равномерную эффективность демонстрирует алгоритм, у которого вероятность пробуждения равна 1, а конфликты разрешаются при помощи венгерской эвристики. Это касается как времени выполнения, так и числа использованных цветов. Реалистически полезные значения s относятся к диапазону от 4 до 6, что приводит к [math]\displaystyle{ \Delta / s }[/math]-раскраске. Эффективность согласно критерию времени выполнения превосходна; даже графы с тысячами вершин удается раскрасить за 20-30 раундов. По сравнению с последовательными алгоритмами такие алгоритмы используют в 2-3 раза больше цветов, но работают намного быстрее.
Наборы данных
При тестировании использовались как синтетически сгенерированные при помощи различных моделей случайных графов данные, так и эталонные тестовые множества реальных данных из второго конкурса DIMACS по реализации алгоритмов [3] и с сайта Джо Калберсона [2].
См. также
Литература
1. Alon, N., Spencer, J.: The Probabilistic Method. Wiley (2000)
2. Culberson, J.C.: http://web.cs.ualberta.ca/~joe/Coloring/index.html
3. Ftp site of DIMACS implementation challenges, ftp://dimacs.rutgers.edu/pub/challenge/
4. Finocchi, I., Panconesi, A., Silvestri, R.: An experimental Analysis of Simple Distributed Vertex Coloring Algorithms. Algorithmica 41,1-23 (2004)
5. Garey, M., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-completeness. W.H. Freeman (1979)
6. Grable, D.A., Panconesi, A.: Fast distributed algorithms for Brooks-Vizing colorings. J. Algorithms 37,85-120 (2000)
7. Johansson, O.: Simple distributed {A + 1)-coloring of graphs. Inf. Process. Lett. 70,229-232 (1999)
8. Kim, J.-H.: On Brook's Theorem for sparse graphs. Combin. Probab. Comput. 4,97-132 (1995)
9. Luby, M.: Removing randomness in parallel without processor penalty. J. Comput. Syst. Sci. 47(2), 250-286 (1993)
10. Molly, M., Reed, B.: Graph Coloring and the Probabilistic method. Springer (2002)
11. Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. In: SIAM Monographs on Discrete Mathematics and Applications 5 (2000)
12. Trick, M.: Michael Trick's coloring page: http://mat.gsia.cmu.ed u/COLOR/color.htm l
