Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

For an edge-weighted connected undirected graph, the minimum $k$-way cut problem is to find a subset of edges of minimum total weight whose removal separates the graph into $k$ connected components. The problem is NP-hard when $k$ is part of the input and W[1]-hard when $k$ is taken as a parameter. A simple algorithm for approximating a minimum $k$-way cut is to iteratively increase the number of components of the graph by $h-1$, where $2\le h\le k$, until the graph has $k$ components. The approximation ratio of this algorithm is known for $h\le 3$ but is open for $h\ge 4$. In this paper, we consider a general algorithm that iteratively increases the number of components of the graph by $h_i-1$, where $h_1 \le h_2 \le … \le h_q$and$\sum_{i=1}^q (h_i-1) = k-1$. We prove that the approximation ratio of this general algorithm is $2-({\sum }_{i=1}^q\left(\genfrac{}{}{0px}{}{h_i}{2}\right))\mathrm{/}\left(\genfrac{}{}{0px}{}{k}{2}\right)$, which is tight. Our result implies that the approximation ratio of the simple algorithm is $2-h\mathrm{/}k+O(h^2\mathrm{/}{k}^2)$ in general and $2-h\mathrm{/}k$ if $k-1$ is a multiple of $h-1$.