О новых алгоритмических приемах для задачи о взвешенной вершинной раскраске

Классическая NP-трудная задача о взвешенной вершинной раскраске состоит в минимизации количества цветов в раскрасках вершин задаваемого графа так, что для каждой вершины назначаются цвета, количество которых равно задаваемому весу вершины, причем смежным вершинам назначаются различные цвета. Соответствующее наименьшее количество цветов называется взвешенным хроматическим числом графа. Известно несколько полиномиальных алгоритмических приемов для построения эффективных алгоритмов для задачи о взвешенной вершинной раскраске. Например, стандартными приемами такого рода являются модульное разложение графов и разложение графов посредством разделяющих клик. В данной статье предлагаются новые полиномиальные способы редукции графов в форме удаления избыточных вершин и пересчета весов остальных вершин так, что взвешенное хроматическое число изменяется контролируемым образом. Приводится способ сведения задачи о взвешенной вершинной раскраске к ее невзвешенному варианту и его приложение. Эта работа вносит вклад в алгоритмическую теорию графов.