Fedor Fomin: Cluster Editing and subexponential algorithms

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.

Based on a joint work with Stefan Kratsch, Marcin and Michal Pilipczuks, and Yngve Villanger.