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

Рассматривается задача о связной раскраске вершин графа в предписанные цвета (СПР). Приводится подробный анализ сложности задачи в зависимости от значений четырех параметров: тип графа, максимальная степень графа, максимальная мощность предписания и максимальная частота вхождения цвета в предписания вершин. Для классов входов задачи СПР, определяемых значением четырехмерного характеристического вектора, находится система из восьми базисных классов, три из которых являются минимальными NP-полными, а остальные пять классов – максимальными полиномиально разрешимыми. Доказывается полнота представленной системы, т. е. сводимость любого класса входов к одному из восьми базисных классов. Показывается связь между задачей СПР и задачами дискретной оптимизации: задачей нахождения связных областей обслуживания, задачами построения расписаний на параллельных машинах, задачей нахождения максимального паросочетания в двудольном гиперграфе, задачей нахождения подсемейств векторов с суммой из заданной области. Табл. 1, ил. 1, библиогр. 7.