Speaker
Description
Vaishali Surianarayanan, Daniel Lokshtanov and Saket Saurabh
Abstract: In the {\sc Min $k$-Cut} problem, the input is a graph $G$ and an integer $k$. The task is to find a partition of the vertex set of $G$ into $k$ parts, while minimizing the number of edges that go between different parts of the partition. The problem is NP-complete, and admits a simple $3^n \cdot n^{O(1)}$ time dynamic programming algorithm, which can be improved to a $2^n \cdot n^{O(1)}$ time algorithm using the fast subset convolution framework by Bj{\"{o}}rklund et al.~[STOC'07]. In this paper we give an algorithm for {\sc Min $k$-Cut} with running time $O((2-\varepsilon)^n)$, for $\varepsilon > 10^{-50}$. This is the first algorithm for {\sc Min $k$-Cut} with running time $O(c^n)$ for $c < 2$.