Minimum k-way cut of bounded size is fixed-parameter tractable

Ken-ichi Kawarabayashi, Mikkel Thorup

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 s…