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

What: | Lecture |

When: | Wednesday, 12 March 2014, 18:00–19:35 |

Where: | ПОМИ РАН |

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.