  We consider a the minimum k-way cut problem for unweighted graphs with a size
bound s on the number of cut edges allowed. Thus we seek to remove as few edges
as possible so as to split a graph into k components, or report that this
requires cutting more than s edges. We show that this problem is
fixed-parameter tractable (FPT) in s. More precisely, for s=O(1), our algorithm
runs in quadratic time while we have a different linear time algorithm for
planar graphs and bounded genus graphs. Our tractability result stands in
contrast to known W[1] hardness of related problems. Without the size bound,
Downey et al.[2003] proved that the minimum k-way cut problem is W[1] hard in k
even for simple unweighted graphs. Downey et al. asked about the status for
planar graphs. Our result implies tractability in k for the planar graphs since
the minimum k-way cut of a planar graph is of size at most 6k (more generally,
we get tractability in k for any graph class with k-way cuts of size limited by
is a function of k, e.g., bounded degree graphs, or simple graphs with an
excluded minor). A simple reduction shows that vertex cuts are at least as hard
as edge cuts, so the minimum k-way vertex cut is also W[1] hard in terms of k.
Marx [2004] proved that finding a minimum k-way vertex cut of size s is also
W[1] hard in s. Marx asked about the FPT status with edge cuts, which we prove
tractable here. We are not aware of any other cut problem where the vertex
version is W[1] hard but the edge version is FPT.
