Min-$k$-cut is the problem of partitioning vertices of a given graph or hypergraph into $k$ subsets such that the total weight of edges or hyperedges crossing different subsets is minimized. For the capacitated min-$k$-cut problem, each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that minimizes the sum of edge weights on all pairs of vertices that lie in different subsets. The min-$k$-cut problem is NP-hard for $k \geq 3$, and the capacitated min-$k$-cut problem is also NP-hard for $k \geq 2$. Min-$k$-cut has numerous applications, for example, VLSI circuit partitioning, which is a key step in VLSI CAD. Although many heuristics have been proposed for min-$k$-cut problems, there are few approximation results of min-$k$-cut problems. We study the equivalent complement problem of the min-$k$-cut problem and extend the method proposed in \cite{gauer} to present deterministic local search approximation algorithms for the complement problem of the min-$k$-cut problem, and the complement problem of the capacitated min-$k$-cut problem on graph with performance ratio $\frac{1}{k}$.
Citation
Research Report, Fuzhou University, CHINA. 2010.6.30