Использование оптимизации раскраски или раскраски для решения поиска раскраски

Question

Как можно показать, что Поиск раскраски может быть решено, сделав полиномиальное количество вызовов в решение для Оптимизация раскраски или же раскраска решения? (Поиск раскраски Является ли алгоритм окрашивать вершины графика, так что соседние вершины имеют другой цвет.)

Я не был уверен, как это решить, но вот что я пытался (я решил использовать Оптимизация раскраски):

Поиск раскраски может быть решено, позвонив Оптимизация раскраски и найти стоимость $ m $, которая представляет собой количество цветов, необходимые для того, чтобы не было двух соседних вершин одинаково. Как только $ m $ найден, Поиск раскраски может окрасить вершины графика, вращаясь через $ M $ разные цвета для каждой вершины.

Я на правильном пути?

Answer 1

Учитывая график $ g $, мы хотим сделать две вещи:

1. Найдите наименьшее $ k $ так, что $ g $-это $ k $-colorrable,
2. Учитывая такой $ k $, найдите окраску $ g $ с цветами $ k $.

Если у нас есть оракул для версии решения проблемы раскраски, мы можем сделать оба.

Для первой части мы можем выполнить поиск, чтобы найти оптимальный $ k $. Даже наивный подход здесь в порядке, мы можем просто последовательно спросить, является ли $ g $ $ k $-colorrable для $ k = 1,2, ldots, n $. Затем мы делаем не более $ n $ звонки в Oracle. Конечно, мы можем выполнить бинарный поиск и сократить это до вызовов $ log n $. (Обратите внимание, что это также то, как мы решаем версию оптимизации с версией решения).

Затем, учитывая, что мы выяснили, что $ K $ оптимально, мы можем найти $ k $-colouring $ g $, используя решение Oracle. Единственное морщин заключается в том, что Oracle не принимает частичные раскраски, поэтому нам нужен способ кодирования на графике, чтобы определенная вершина была окрашена определенным цветом.

Для этого мы на самом деле используем Oracle на вспомогательном графике, который мы позвоним $ g^{+} $, то есть $ g $ плюс $ k_ {k} $ с некоторыми дополнительными ребрами. Конечно, $ k_ {k} $ требует ровно $ k $ colors, поэтому мы можем использовать его вершины, чтобы указать, какие цвета доступны для вершины. Пусть вершины $ {k_ {1}, ldots, k_ {k} } $ из $ k_ {k} $ соответствуют цветам $ {c_ {1}, ldots, c_ {k} } $. Тогда мы укажем, что вершина $ v $ in $ g $ не может быть окрашенным цветом $ c_ {i} $, сделав его рядом с $ k_ {i} $. Кроме того каждый $ k_ {i} $ с $ i neq J $ (и нет рядом с $ k_ {j} $).

Затем мы неоднократно делаем следующее:

1. Выберите «непредубеленную» вершину $ v in v (g) $.
2. Для каждой вершины $ u in n (v) $, если $ u $ была окрашена, то есть один $ k_ {i} $ такой, что $ uk_ {i} notin e (g) $. Добавьте Edge $ vk_ {i} $ to $ e $.
3. Для оставшихся вершин $ k_ {j} $ так, что $ vk_ {j} $ еще не в $ e $, мы добавляем все Другой Ряд между $ V $ и $ K_ {k} $ и спросите Oracle, если новый график $ k $ -colourable. Если это так, мы сохраняем этот график и переходим к следующей вершине, если ответ нет, мы отменим шаг 3 и попробуем со следующей $ k_ {j} $.

Обратите внимание, что как $ g $-это $ k $ -colourable, есть $ K_ {j} $, с чем будет работать третий шаг. Затем, когда мы обрабатывали каждую вершину, каждая вершина в $ g $ - это нет Примыкает к ровному вершине в $ k_ {k} $, это указывает на то, какой цвет вершина может быть окрашена для получения окраски. С шага 2 мы видим, что это не может быть таким же цветом, как и любой из его соседей.

На третьем этапе мы делаем максимум $ K $ вызовы в Oracle, и мы делаем это для каждой вершины в $ G $, поэтому в общей сложности мы делаем не более $ (K+1) n $ вызовы в Oracle (включая поиск за $ k $).