<<
>>

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

Нетрудно заметить, что задача о раскраске дуг напрямую сводится к задаче о рас- краске графа. Для заданного экземпляра задачи раскраски дуг мы определим граф, содержащий узел z для каждого пути P , и соединим узлы z и z в H, если у путей P и P существует общее ребро в G.
Тогда маршрутизация всех потоков с использо- ванием к длин волн представляет собой задачу о раскраске H с использованием не более к цветов. (На самом деле эта задача представляет собой очередное практиче- ское применение раскраски графа, в которой абстрактные «цвета» действительно являются цветами, так как они представляют световые волны разной длины.)

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

Итак, что же можно сказать о сложности задачи о раскраске дуг?

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

четырех узлов

Как выясняется, ЖР-полнота задачи о раскраске дуг доказывается с использо- ванием очень сложного сведения. Это огорчит людей, работающих с оптоволо- конными сетями, потому что означает, что задача оптимального распределения длин волн вряд ли имеет эффективное решение. Однако все известные сведения, демонстрирующие ЖР-полноту задачи о раскраске дуг, обладают одним интерес- ным свойством: сложные экземпляры задачи о раскраске дуг, создаваемые ими, всегда имеют достаточно большое множество длин волн.

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

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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Сложность задачи о раскраске дуг:

  1. СЛОЖНОСТЬ КОГНИТИВНАЯ
  2. 5.6.3. Сложность - первое условие прозренний
  3. Классификация по сложности и оперативности
  4. СЛОЖНОСТЬ
  5. Сложность структуры организации.
  6. Сложность интровертного поведения
  7. Сложность вредоносного агента (предмета, средства)
  8. Сложность вредоносного агента (предмета, средства)
  9. 3. Сложность метода не служит гарантией его эффективности.
  10. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  11. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  12. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  13. ЗАДАЧА