Раскраска множества дуг - Расширение пределов разрешимости

Несколько лет назад, когда телекоммуникационные компании начали интенсивно заниматься технологией спектрального мультиплексирования, у исследователей в этих компаниях проявился глубокий интерес к алгоритмическому вопросу, который ранее почти не изучался: задаче о раскраске множества дуг.

Сначала мы объясним, как проявилась связь между этими темами, а потом разработаем алгоритм для этой задачи. Алгоритм представляет собой более сложную вариацию на тему раздела 10.2: вычислительно сложная задача решается методами динамического программирования, с построением решений на множестве подзадач, “взаимодействующих” друг с другом по очень малым фрагментам входных данных. Ограничение таких взаимодействий позволяет удержать под контролем сложность алгоритма.

Задача

Сначала в двух словах о том, как проблемы сетевой маршрутизации привели к вопросу раскраски дуг. Технология спектрального мультиплексирования позволяет нескольким коммуникационным потокам совместно использовать одну часть оптоволоконного кабеля при условии, что потоки передаются по кабелю на разных длинах волн. Смоделируем коммуникационную сеть в виде графа G = (V, E); каждый коммуникационный поток представляется путем P_i в G; считается, что данные передаются по потоку от одного конца P_i на другой конец. Если пути P_i и P_j имеют общее ребро в G, одновременная передача данных по этим потокам возможна только на разных длинах волн. Итак, наша цель заключается в следующем: для заданного множества из k длин волн (1, 2, ..., k) каждому потоку P_i требуется назначить длину волны так, чтобы каждой паре потоков, имеющих общее ребро в графе, были назначены разные длины волн. Назовем эту задачу экземпляром задачи о раскраске путей, а ее решение — действительное распределение длин волн между путями — k-раскраской.

Это вполне естественная задача, которую можно рассматривать прямо в таком виде; но с точки зрения контекста оптоволоконной маршрутизации будет полезно внести одно упрощение. На практике спектральное мультиплексирование часто работает в сетях G, имеющих чрезвычайно простую структуру, поэтому будет естественно ограничить экземпляры задачи о раскраске путей за счет некоторых предположений относительно структуры сети. Один из самых важных частных случаев на практике также оказывается одним из простейших: используемая сеть имеет кольцевидную структуру, то есть моделируется графом G, который представляет собой цикл из n узлов.

Именно этим случаем мы сейчас займемся: имеется граф G = (V, E), который представляет собой цикл из n узлов, и имеется множество путей P₁, ..., P_m в этом цикле. Целью, как и прежде, является назначение одной из k заданных длин волн каждому пути P_i так, чтобы перекрывающимся путям назначались разные длины волн. Мы будем называть такое назначение действительным распределением длин волн. На рис. 10.1 изображен примерный экземпляр такой задачи. В этом экземпляре существует действительное распределение с k = 3 длинами волн: длина волны 1 назначается путям а и е, длина волны 2 — путям b и f длина волны 3 — путям c и d. Из рисунка видно, что циклическая сеть может рассматриваться как круг, а пути — как дуги на этом круге; соответственно этот частный случай задачи о раскраске путей будет называться задачей о раскраске дуг.

Рис. 10.1. Экземпляр задачи о раскраске дуг с шестью дугами (a, b, c, d, e, f) для цикла из четырех узлов

Сложность задачи о раскраске дуг

Нетрудно заметить, что задача о раскраске дуг напрямую сводится к задаче о раскраске графа. Для заданного экземпляра задачи раскраски дуг мы определим граф, содержащий узел z_i для каждого пути P_i, и соединим узлы z_i и z_j в H, если у путей P_i и P_j существует общее ребро в G. Тогда маршрутизация всех потоков с использованием k длин волн представляет собой задачу о раскраске H с использованием не более k цветов. (На самом деле эта задача представляет собой очередное практическое применение раскраски графа, в которой абстрактные “цвета” действительно являются цветами, так как они представляют световые волны разной длины.)

Из этого не следует, что задача о раскраске дуг является NP-полной, — мы всего лишь свели ее к известной NP-полной задаче, что ничего не говорит о ее сложности. Для задачи о раскраске путей на обобщенных графах легко выполнить сведение задачи о раскраске графа к раскраске путей, тем самым устанавливая NP-полноту задачи о раскраске путей. Однако это прямолинейное сведение не работает, когда используемый граф представляет собой простой цикл. Итак, что же можно сказать о сложности задачи о раскраске дуг?

Как выясняется, NР-полнота задачи о раскраске дуг доказывается с использованием очень сложного сведения. Это огорчит людей, работающих с оптоволоконными сетями, потому что означает, что задача оптимального распределения длин волн вряд ли имеет эффективное решение. Однако все известные сведения, демонстрирующие NР-полноту задачи о раскраске дуг, обладают одним интересным свойством: сложные экземпляры задачи о раскраске дуг, создаваемые ими, всегда имеют достаточно большое множество длин волн. Итак, эти сведения не доказывают, что задача о раскраске дуг сложна при малом количестве длин волн; они оставляют возможность того, что для любого фиксированного, постоянного количества длин волн k задача распределения длин волн может быть решена за время, полиномиальное по n (размер цикла) и m (количество путей). Другими словами, мы можем надеяться на время выполнения в форме, приведенной для задачи о вершинном покрытии в разделе 10.1: O(f(k) ∙ p(n, m)), где f(∙) может быть быстрорастущей функцией, но p(∙,∙) имеет полиномиальную скорость роста.

Такое время выполнения выглядит заманчиво (если f(∙) не растет с совсем запредельной скоростью), так как оно делает распределение длин волн потенциально приемлемым при малом их количестве. Чтобы понять, насколько непросто добиться такого времени выполнения, приведем аналогию: общая задача о раскраске графа сложна уже для трех цветов. Если бы задача о раскраске дуг была разрешима для любого фиксированного количества длин волн (то есть цветов) k, это означало бы, что она является частным случаем раскраски графа с качественно иной сложностью.

В этом разделе мы постараемся создать алгоритм с временем выполнения такого типа, O(f(k) ∙ p(n, m)). Как упоминается в начале раздела, сам алгоритм строится на принципах, приводившихся в разделе 10.2 при решении задачи о независимом множестве с максимальным весом для деревьев. Сложность поиска, присущая поиску независимого множества с максимальным весом, была сокращена тем фактом, что для каждого узла v в дереве T задачи в компонентах T - {v} становились полностью изолированными, когда мы принимали решение о включении (или невключении) v в независимое множество. Это конкретный пример общего принципа фиксирования малого множества решений, а следовательно, разделения задачи на меньшие подзадачи, которые могут решаться независимо.

В данном случае аналогичная идея заключается в выборе конкретной точки цикла и решении о том, как раскрашивать дуги, проходящие через эту точку; закрепление этих степеней свободы позволяет определять серии меньших подзадач для оставшихся дуг.

Разработка алгоритма

Для начала определимся с обозначениями. Имеется граф G, который представляет собой цикл из n узлов; узлы обозначаются v₁, v₂, ..., v_n, для каждого i существует ребро (v_i, v_i+1), а также существует ребро (v_n, v₁). Существует множество путей P₁, P₂, ..., P_m в графе G и множество из k доступных цветов; пути нужно раскрасить так, чтобы путям P_i и P_j, имеющим общее ребро, назначались разные цвета.

Простой частный случай: раскраска интервалов

Чтобы построить алгоритм для раскраски дуг, мы сначала рассмотрим более простую задачу о раскраске интервалов на линии. Ее можно рассматривать как частный случай задачи о раскраске дуг, в котором дуги лежат только в одном полушарии; стоит избавиться от сложностей, обусловленных “возвратом к началу”, как задача намного упрощается. Итак, в этом частном случае имеется множество интервалов, которые необходимо пометить так, чтобы каждые два перекрывающихся интервала получали разные метки.

Именно такая задача уже встречалась ранее: это задача интервального планирования, оптимальный жадный алгоритм для которой приводился в разделе 4.1. Анализ в этом разделе не только показывает, что для раскраски интервалов существует эффективный оптимальный алгоритм, но и дает много полезной информации о структуре задачи. А именно: если определить глубину множества интервалов как максимальное число интервалов, проходящих через одну точку, то жадный алгоритм из главы 4 показал бы, что минимальное количество необходимых цветов всегда равно глубине. Обратите внимание: количество необходимых цветов очевидно не менее глубины, потому что интервалы, содержащие общую точку, должны быть окрашены в разные цвета; здесь принципиально то, что необходимое количество цветов не может быть больше глубины.

Интересно, что точное отношение между количеством цветов и глубиной не выполняется для наборов дуг в круге. На рис. 10.2, например, изображен набор дуг с глубиной 2, для которого необходимы три цвета. Это происходит из-за того, что при попытке раскраски набора дуг возникают “отдаленные” препятствия, которые существенно усложняют задачу по сравнению с раскраской интервалов на линии. Несмотря на это, анализ упрощенной задачи раскраски интервалов будет полезен для разработки алгоритма раскраски дуг.

Рис. 10.2. Набор дуг, для раскраски которого необходимы три цвета, хотя через любую точку окружности проходят не более двух дуг

А теперь вернемся к задаче о раскраске дуг. Для начала рассмотрим частный случай, при котором для каждого ребра е в цикле существуют ровно к путей, содержащих е. Назовем эту задачу частным случаем с постоянной глубиной. Этот частный случай может показаться ограниченным, но, по сути, в нем отражена вся сложность задачи; и когда мы получим алгоритм для случая с постоянной глубиной, он легко преобразуется в алгоритм решения обобщенной задачи.

Разработка алгоритма начинается с преобразования экземпляра задачи в измененную форму задачи раскраски интервалов: цикл “разрезается” по ребру (v_n, v₁) и “разворачивается” в путь G'. Этот процесс изображен на рис. 10.3. “Разрезанный и развернутый” граф G' содержит те же узлы, что и G, а также два лишних узла в точке разреза: узел v₀, смежный с v₁ (и никакими другими узлами), и узел v_n+1, смежный с v_n (и никакими другими узлами). Кроме того, множество путей также немного изменилось. Допустим, P₁, P₂, ..., P_k — пути, содержащие ребро (v_n, v₁) в G. Каждый из этих путей P_i разделяется на два: P'_i (от v₀) и P"_i (до v_n+1).

Перед нами экземпляр задачи о раскраске интервалов с глубиной k. Следовательно, из приведенного выше упоминания связи между глубиной и цветами видно, что интервалы

могут быть окрашены с использованием k цветов. И что же, работа закончена? Можно ли преобразовать это решение в решение для путей графа G?

Оказывается, это не так просто; проблема в том, что при раскраске интервалов путям P'_i и P"_i могут быть назначены разные цвета. Так как это два фрагмента одного пути P_i в G, непонятно, как взять разные цвета P'_i и P"_i и определить по ним цвет P_i в G. Например, при разрезании цикла на рис. 10.3, а будет получено множество интервалов, изображенное на рис. 10.3, b. Предположим, была вычислена такая раскраска, что интервалам в первой строке присваивается цвет 1, интервалам во второй строке — цвет 2, а интервалам в третьей строке — цвет 3. Тогда очевидного способа определить цвет для а и c не существует.

Рис. 10.3. Разрезание цикла (а) в экземпляре раскраски дуг и его преобразование в (b) набор интервалов на линии

Это подсказывает способ формализации отношений между экземпляром раскраски дуг в G и экземпляром раскраски интервалов в G'.

(10.9) Пути в G имеют k-раскраску в том, и только в том случае, если пути в G' имеют k-раскраску c тем дополнительным ограничением, что Р'_i и Р"_i назначается одинаковый цвет для всех i = 1, 2, ..., k.

Доказательство. Если пути в G могут быть раскрашены в к цветов, то мы просто используем k-раскраску как цвета G', назначая каждому из путей Р'_i и Р"_i цвет Р_i. В полученной раскраске никакие два пути не имеют общего ребра.

И наоборот, предположим, пути в G' могут иметь k-раскраску с тем дополнительным ограничением, что Р'_i и Р"_i назначается один цвет для всех i = 1, 2, ..., k. Тогда пути Р_i (для i ≤ k) назначается общий цвет Р'_i и Р"_i, а пути Р_j (для j > k) назначается цвет, который Р_j получает в G'. И снова при такой раскраске никакие два пути, имеющие общий цвет, не имеют общих ребер. ■

Теперь мы успешно преобразовали задачу в поиск раскраски путей G', подчиняющейся условию из (10.9): путям Р'_i и Р"_i (1 ≤ i ≤ k) назначается один цвет.

Прежде чем двигаться дальше, мы введем дополнительную терминологию, которая упрощает обсуждение алгоритмов в этой задаче. Во-первых, так как названия цветов выбираются произвольно, можно считать, что пути Р'_i назначен цвет i для каждого i = 1, 2, ..., k. Теперь для каждого ребра e_i = (v_i, v_i+1) мы обозначаем S_i множество путей, содержащих это ребро. K-раскраска только для путей S_i имеет очень простую структуру: это просто способ назначения ровно одного из цветов {1, 2, ..., k} каждому из k путей в S_i. Мы будем рассматривать такую k-раскраску как взаимно однозначную функцию f: S_i → {1, 2, ..., k}.

А теперь важное определение: k-раскраска f для S_i и k-раскраска g для S_j называются согласованными, если существует одна k-раскраска всех путей, которая равна f для S_i, а также равна gдля S_j. Иначе говоря, k-раскраски f и g для ограниченных частей экземпляра могут быть получены из одной k-раскраски всего экземпляра. В контексте согласованности наша задача формулируется следующим образом: если обозначить f'k-раскраску S₀, которая назначает цвет i пути Р'_i, а f" — k-раскраску S_n, которая назначает цвет i пути Р"_i, требуется решить, являются ли согласованными f' и f".

Поиск допустимой раскраски интервалов

Неясно, как принять решение о согласованности f' и f" напрямую. Вместо этого мы воспользуемся методом динамического программирования и построим решение на основе серии подзадач.

Подзадачи выглядят так: для каждого множества S_i, последовательно обрабатывая i = 0, 1, 2, ..., n, мы вычисляем множество F_i для всех k-раскрасок S_i, согласованных с f'. После вычисления множества F_n остается только проверить, содержит ли оно f", чтобы ответить на общий вопрос о согласованности f' и f".

В начале выполнения алгоритма F₀ = {f'}: так как f' определяет цвет для каждого интервала в S₀, очевидно, что никакая k-раскраска S₀ не может быть согласована с ней. Теперь допустим, что мы вычислили F₀, F₁, ..., F_i, и покажем, как вычислить F_i+1 по F_i.

Вспомните, что S_i состоит из путей, содержащих ребро e_i = (v_i, v_i+1), а S_i+1 состоит из путей, содержащих следующее последовательное ребро e_i+1 = (v_i+1, v_i+2). Пути в S_i и S_i+1 можно разделить на три типа:

♦ содержащие e_i и e_i+1, лежат в S_i и S_i+1,

♦ заканчивающиеся в узле v_i+1; лежат в S_i, но не в S_i+1;

♦ начинающиеся в узле v_i+1; лежат в S_i+1, но не в S_i.

Для любой раскраски f ∈ F_i раскраска g множества S_i+1 называется расширением f, если все пути в S_i ∩ S_i+1 имеют одни и те же цвета в отношении f и g. Легко проверить, что если g является расширением f, а раскраска f согласована с f', то согласована и раскраска g. С другой стороны, предположим, некоторая раскраска g множества S_i+1 согласована с f'; иначе говоря, существует раскраска h всех путей, равная f' для S₀, и равная g для S_i+1. Тогда, если рассмотреть цвета, назначаемые h путям в S_i, мы получаем раскраску f ∈ F_i и g является расширением f.

Это доказывает следующий факт.

(10.10) Множество F_i+1 равно множеству всех расширений k-раскрасок в F_i.

Итак, чтобы вычислить F_i+1, достаточно просто составить список всех расширений всех раскрасок в F_i. Для всех f ∈ F_i это означает, что нам нужен список всех раскрасок g для S_i+1, согласующихся с f для S_i ∩ S_i+1. Для этого мы перечисляем все возможные способы назначения цветов S_i - S_i+1 (в отношении f) путям S_i+1 - S_i. Слияние этих списков для всех f ∈ F_i дает F_i+1.

Итак, общий алгоритм выглядит так:

На рис. 10.4 представлены результаты выполнения этого алгоритма для примера на рис. 10.3. Как и во всех алгоритмах динамического программирования, которые встречались в этой книге, сама раскраска вычисляется обратным отслеживанием по этапам построения множеств F₁, F₂, ..., F_n.

Вскоре мы проанализируем время выполнения этого алгоритма. Но сначала посмотрим, как снять предположение о том, что входной экземпляр имеет постоянную глубину.

Вспомните, что только что разработанный нами алгоритм предполагает, что каждое ребро e содержится ровно в k путях. В общем случае каждое ребро может быть задействовано в разном количестве путей, вплоть до максимума k. (Если бы было ребро, содержащееся в k+1 путях, то все эти пути должны были быть окрашены в разные цвета, поэтому нам пришлось бы немедленно заключить, что входной экземпляр не окрашивается в к цветов.)

Рис. 10.4. Выполнение алгоритма раскрашивания. Исходная раскраска f' присваивает цвет 1 интервалу а', цвет 2 — интервалу b' и цвет 3 — интервалу с'. Над каждым ребром e_i (для i > 0) расположена таблица, представляющая множество всех согласованных раскрасок в F_i: каждая раскраска представляется одним из столбцов таблицы. Так как раскраска f"(а") = 1, f"(b") = 2 и f"(c") = 3 присутствует в последней таблице, у экземпляра существует решение

Алгоритм нетрудно изменить напрямую для общего случая, но так же просто свести общий случай к случаю с постоянной глубиной. Для каждого ребра e_i, несущего только k_i < k путей, добавляются k - k_i путей, состоящих из единственного ребра е_i. Теперь мы имеем экземпляр с постоянной глубиной и можем доказать следующее утверждение:

(10.11) Исходный экземпляр может быть раскрашен k цветами в том, и только в том случае, если измененный экземпляр (полученный добавлением однореберных путей) может быть раскрашен k цветами.

Доказательство. Очевидно, если измененный экземпляр имеет k-раскраску, то эта же k-раскраска может быть применена к исходному экземпляру (цвета, назначенные только что добавленным однореберным путям, просто игнорируются). И наоборот, предположим, что исходный экземпляр имеет k-раскраску f. Тогда мы можем построить k-раскраску измененного экземпляра, начиная с f и последовательно рассматривая дополнительные однореберные пути, назначая любой свободный цвет каждому из этих путей при их рассмотрении. ■

Анализ алгоритма

Наконец, найдем границу для времени выполнения алгоритма. В нем доминирует время вычисления множеств F₁, F₂, ..., F_n. Чтобы построить одно из таких множеств F_i+1, нам понадобится рассмотреть каждую раскраску f ∈ F_i и перечислить все перестановки цветов, которые f присваивает путям в S_i - S_i+1. Так как S_i содержит k путей, то количество раскрасок в F_i не превышает k!. Перечисление всех перестановок цветов, которые f назначает S_i - S_i+1, также включает перебор по множеству размера l!, где l ≤ k — размер S_i - S_i+1.

Следовательно, общее время вычисления F_i+1 от F_i записывается в форме O(f(k)) для функции f(∙), зависящей только от k. По n итерациям внешнего цикла для вычисления F₁, F₂, ..., F_nполучаем общее время выполнения O(f(k) ∙ n), как и требовалось.

На этом завершается описание и анализ алгоритма. Основные его свойства перечислены в следующем утверждении.

(10.12) Алгоритм, описанный в этом разделе, правильно определяет возможность раскраски набора путей в n-узловом в k цветов, а его время выполнения составляет O(f(k) ∙ n) для функции f(∙), зависящей только от k.

Оглядываясь назад, мы видим, что время выполнения алгоритма обусловлено фактом, упомянутым в начале раздела: для всех i подзадачи, основанные на вычислении F_i и F_i+1, совместно “проходят” через “узкий интерфейс”, состоящий из путей в S_i и S_i+1, размер каждого из которых не превышает k. Таким образом, мы можем сделать так, чтобы время, необходимое для перехода между ними, зависело только от k, а не от размера цикла G или от количества путей.