Laboratory of Mathematical Logic at PDMI

Пятница, 5 октября, 106. Начало в 14:00.

Докладчик: Д. Сагунов (АУ).

Тема: Параметризованная сложность задач о счастливой раскраске графов.

Abstract

В задаче Maximum Happy Vertices (MHV) входом является граф, некоторые вершины которого изначально покрашены в несколько цветов. Вершина в графе называется счастливой, если она и все ее соседи имеют один и тот же цвет. Ответом на задачу является такая раскраска оставшихся вершин, что количество счастливых вершин в такой раскраске максимально возможно.

Во второй задаче о счастливой раскраске --- Maximum Happy Edges (MHE) --- требуется максимизировать количество счастливых ребер --- ребро считается счастливым, если его концы имеют один и тот же цвет. Эта задача очень тесно связана с задачей Multiway Cut, где требуется удалить минимальное число ребер в графе, чтобы выделенные вершины оказались в разных компонентах связности.

Известно, что обе задачи являются NP-трудными, если в раскраске используются хотя бы три различных цвета, даже на некоторых простых классах графов. Задача MHE находится в FPT, если в качестве параметра рассматривать количество счастливых ребер. Задача MHV, напротив, является W[1]-трудной, если в качестве параметра рассматривать требуемое количество счастливых вершин.

В трудах последних лет рассматриваются эти и другие параметры для задач MHE и MHV, многие из них --- структурные параметры графа. Для большинства из них получены верхние оценки, однако во многих из этих результатов необходимо фиксировать количество используемых в раскраске цветов. Для нескольких из них в работах оставлены открытые вопросы о существовании FPT-алгоритмов или полиномиальных ядер для задач MHV или MHE.

Мы отвечаем на многие из этих вопросов. Вот основные из этих результатов:
1) MHE NP-трудна уже на пороговых графах, а для MHV существует полиномиальный алгоритм на интервальных графах;
2) И MHV, и MHE W[1]-трудны для многих структурных параметров графа;
3) MHE W[1]-трудна для параметра "расстояние до кластерного графа", а для MHV существует FPT-алгоритм;
4) Для MHE и MHV не существует полиномиальных ядер относительно размера вершинного покрытия, если полиномиальная иерархия не схлопывается на третьем уровне.

Кроме того, мы устанавливаем важную связь между задачей MHV и задачей Node Multiway Cut, в которой требуется удалить наименьшее количество вершин, чтобы разрушить все пути между различными терминальными вершинами.

Мы постараемся рассмотреть и доказать вышеперечисленные результаты.