City: Test Saint Petersburg Novosibirsk Kazan Language: Русский English

Cluster Editing and subexponential algorithms (Фёдор Фомин)
Seminar on parameterized algorithms

What: Lecture
When: Wednesday, 12 March 2014, 18:00–19:35
Where: ПОМИ РАН

Description

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.