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.