ND16 M INIMUM K -C UT

     
• I NSTANCE : Graph , a weight function , and an integer .
• S OLUTION : A partition of V into k disjoint sets .
• M EASURE : The sum of the weight of the edges between the disjoint sets, i.e.,
  
  

• Good News: Approximable within [ 315 ].
• Comment: Solvable in polynomial time for fixed k [ 138 ]. If the sets in the partition are restricted to be of equal size, the problem is approximable within [ 315 ]. The unweighted problem admits a PTAS if every vertex has degree [ 24 ].