17.05.2018 Алгоритмы и нижние оценки для задачи Target Set Selection (Даниил Сагунов)

Название: Алгоритмы и нижние оценки для задачи Target Set Selection

Время: 17 мая, 18:30

Место: Академический университет, аудитория 431

Докладчик: Данил Сагунов

 

Мы рассмотрим задачу Target Set Selection. Входом задачи является неориентированный граф,

в котором каждой вершине сопоставлено некоторое неотрицательное число - пороговое значение,

и числа k, l. Требуется ответить на вопрос, можно ли заразить вершин графа изначально так,

что в конце концов хотя бы вершин графа станут зараженными. Вершина становится зараженной,

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

 

Мы рассмотрим два точных экспоненциальных алгоритма, которые решают задачу быстрее, чем

за 2^n в случае, если все пороговые значения равны двум или трем, и требуется заразить все

вершины графа, т.е. l=n.

 

Кроме того, мы покажем, что Target Set Selection является W[1]-трудной относительно параметра l

даже если пороговые значения всех вершин равны двум, или если пороговое значение любой 

вершины совпадает с ее степенью.

 

Ivan Bliznets, Danil Sagunov 

​​​​​​​Solving Target Set Selection with Bounded Thresholds Faster than 2n