Georgia Institute of Technology College of Sciences

We consider a the minimum k-way cut problem for unweighted graphs with a 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 result solves some open problems and contrasts W[1] hardness (no FPT unless P=NP) of related formulations of the k-way cut problem. 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. 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 FPT status with edge cuts, which is what we resolve here. We also survey approximation results for the minimum k-way cut problem, and conclude some open problems. Joint work with Mikkel Thorup (AT&T Research).