On three-way graph partitioning

Given an undirected graph G with n vertices, m edges and positive edge weights and k terminals {s₁, s₂, …, s _k} on G, the problem of computing a minimum k-way cut of G is to find a minimum (cost) k-way cut C that disconnects each terminal from all the others. The minimum k-way cut problem is known as NP-hard even if all vertex degrees are three or less and k is equal to 3. The minimum k-way cut problem for a planar graph and fixed integer k can be solved in polynomial time. This paper presents an algorithm for computing a minimum three-way cut of a graph in a larger class than planar graphs