Почему раскраска вершин NP-трудна?

Я читаю алгоритм раскраски вершин. Я вижу документы, объясняющие, как проблема может быть решена с помощью BFS (подразумевается, что проблема может быть решена за O(|V|+|E|). Но я также вижу упоминание о том, что это NP-сложная задача.

Как эти двое сочетаются? Не могли бы вы пролить немного света?

Вот алгоритм, с которым я столкнулся, который мне показался полиномиальным решением общего случая:

Идентифицируйте каждый цвет цифрой. Начните с узла и назначьте ему цвет с наименьшим номером. Посетите каждого своего соседа с помощью BFS. При посещении узла проверьте цвет каждого из его соседей и назначьте цвет с наименьшим номером, который не назначен ни одному из его соседей.

Сказано, что подход BFS работает только для 2-х цветов. Я могу понять, почему описанная выше техника не работает для более чем двух цветов.


algorithm graph-algorithm np-hard
person Aadith Ramia    schedule 15.02.2014    source источник

Ответы (3)


arrow_upward
1
arrow_downward

Обычно, когда я думаю о поиске хлеба в первую очередь (BFS), я думаю о нем как о применении к деревьям, но раскраска вершин — это проблема графа, а не проблема дерева. Я полагаю, вы могли бы применить BFS к графу, приняв правило, согласно которому все узлы, смежные с текущим, помечаются перед переходом к другому узлу.

Во-первых, взгляните на базовый пример того, как простая маркировка с использованием упорядочения по наименьшему числу (так называемое последовательное упорядочение) не работает:

введите здесь описание изображения

Если мы пометим узлы по часовой стрелке (от A до J), мы получим 4-раскраску, хотя на самом деле этот граф имеет 2-раскраску. Теперь ваше правило приоритетной маркировки смежных узлов будет работать, потому что это двухцветная раскраска. Но есть 3-раскраски, для которых ваше правило не будет работать, например:

введите здесь описание изображения

В этом примере мы выбираем A в качестве корня «дерева» и сначала делаем его дочерние элементы, B и C. Затем мы выбираем дочерний элемент B, потому что он ниже в алфавитном порядке, чем C, и выполнять все дочерние элементы B. Мы получаем 4-раскраску, хотя на самом деле граф может быть 3-цветным.

person Tyler Durden    schedule 16.02.2014

arrow_upward
0
arrow_downward

Частный случай Vertex Coloring или аппроксимация может быть достигнута с помощью BFS. Общая проблема — NP-Complete, и BFS не может решить все ее случаи. Я хотел бы попытаться привести контрпример, но ваше описание алгоритма отсутствует - стратегия раскраски не ясна.

Например, простая раскраска, достижимая с помощью BFS, равна c(v) = d(source,v) (здесь c(v) — это цвет, d(source,v) — это расстояние от источника до вершины, полученное с помощью BFS)).
Легко видеть, что это не оптимально для A--B--C--D, где вы можете раскрасить его двумя цветами, но это решение использует 4 цвета.

person amit    schedule 15.02.2014
comment
Особым случаем для BFS является раскраска в 2 цвета согласно Википедии (но, предположительно, это также работают как приближение для общего случая). - person Bernhard Barker; 15.02.2014
comment
@amit Вот алгоритм, с которым я столкнулся, который показался мне решением полиномиального времени общего случая: каждый цвет идентифицируется числом. Начните с узла и назначьте ему цвет с наименьшим номером. Посетите каждого своего соседа с помощью BFS. При посещении узла проверьте цвет каждого из его соседей и назначьте цвет с наименьшим номером, который не назначен ни одному из его соседей. Я не могу понять, почему это не работает для более чем двух цветов. - person Aadith Ramia; 15.02.2014
comment
@Aadith это жадный алгоритм и неоптимальный в том смысле, что на большинстве графиков ему нужно больше цветов, чем необходимо. - person Niklas B.; 15.02.2014

arrow_upward
0
arrow_downward

Алгоритм, использующий BFS, решает упрощенный случай задачи раскраски вершин, когда количество цветов не фиксировано, и иногда он может работать как приближенное решение общей NP-полной задачи, заключающейся в раскраске графа с использованием k цветов или поиске минимального набора цветов, который можно использовать для раскрашивания графика

person Vikram Bhat    schedule 15.02.2014