The minimum k-way cut problem

Graph Theory Seminar
Friday, June 11, 2010 - 15:05
1 hour (actually 50 minutes)
Skiles 254
National Institute of Informatics, Tokyo
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).