Есть ли алгоритм раскраски графа, в котором можно установить ограничения на количество вершин для каждого цвета?

Я понимаю, что раскраска графа - это NP-полная проблема. Мне было интересно, упрощает ли задачу добавление ограничения на количество вершин, которые могут иметь данный цвет? Кажется, я не могу найти ни одного алгоритма, который бы это делал. Например, если у меня есть граф, я хотел бы сказать «какова наименьшая окраска этого графа, чтобы каждый цвет имел не более 3 вершин», или, если это упрощает задачу, «есть ли способ раскрасить этот граф с помощью 4 цвета, каждый из которых имеет не более 3 вершин »?

Спасибо!


colors graph algorithm graph-coloring np
person cs54321    schedule 12.04.2013    source источник
comment
Как кто-то борется с планированием r600g bank_swizzle, которое накладывает именно это ограничение, я бы не сказал, что это упрощает ситуацию, скорее, это еще одна проблема, которую мне нужно решить. Спасибо, что задали вопрос.   -  person Hi-Angel    schedule 07.07.2017

Ответы (2)


arrow_upward
2
arrow_downward

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

Надеюсь это поможет!

person templatetypedef    schedule 12.04.2013
comment
Вы имеете в виду np-complete, когда сказали, что проблема по-прежнему будет np-сложной? - person masotann; 12.04.2013
comment
@Calpis NP-hard должно быть правильным, потому что сокращение подразумевает, что это at least так же сложно, как и стандартная проблема раскраски графа. - person G. Bach; 12.04.2013

arrow_upward
1
arrow_downward

Я бы сказал, что поиск хроматического числа графа с учетом ограничения существования k-раскраски можно легко добавить к точному алгоритму на основе DSATUR [Randall-Brown 72] [San Segundo 11] и обрезать пространство поиска, когда одной вершине нужно назначить цвет k. В любом случае проблема остается в НП.

person chesslover    schedule 24.07.2014