  The $k$-cut problem asks, given a connected graph $G$ and a positive integer
$k$, to find a minimum-weight set of edges whose removal splits $G$ into $k$
connected components. We give the first polynomial-time algorithm with
approximation factor $2-\epsilon$ (with constant $\epsilon > 0$) for the
$k$-cut problem in planar and minor-free graphs. Applying more complex
techniques, we further improve our method and give a polynomial-time
approximation scheme for the $k$-cut problem in both planar and minor-free
graphs. Despite persistent effort, to the best of our knowledge, this is the
first improvement for the $k$-cut problem over standard approximation factor of
$2$ in any major class of graphs.
