Город: Санкт-Петербург Новосибирск Казань Язык: Русский English

Cluster Editing and subexponential algorithms (Фёдор Фомин)
Семинар по параметризованным алгоритмам


Что: Лекция
Когда: Среда, 12 марта 2014, 18:00–19:35
Где: ПОМИ РАН

Описание

We discuss (a bit unusual) behavior of certain NP-complete problems admitting subexponential algorithms. For example, the \( p \)-Clustering problem is to decide for a given \( n \)-vertex graph \( G \) and integers \( k \) and \( p \), if \( G \) can be turned into a \( p \)-cluster (disjoint union of \( p \) cliques) by at most \( k \) edge modifications (adding/deleteling edges). We give a subexponential algorithm solving this problem in time \( O(exp((\sqrt{qp}) +n +m) \). On the other hand, there are strong arguments showing that most of NP-complete problems cannot be solved in subexponential time. While existence of subexponential time algorithms does not resolve P vs NP question, it shows an interesting diversity of the world of intractable problems.