Cluster Editing and subexponential algorithms

Graphs, Hypergraphs, and Computing

27 February 14:00 - 15:00

Fedor Fomin - University of Bergen

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.
Magnus M. Halldorsson
Reykjavik University
Klas Markström
Umeå University
Andrzej Rucinski
Adam Mickiewicz University
Carsten Thomassen
Technical University of Denmark, DTU


Klas Markström


For practical matters at the Institute, send an e-mail to