[edit]
Graph Partitioning with a Move Budget
Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, PMLR 238:568-576, 2024.
Abstract
In many real world networks, there already exists a (not necessarily optimal) k-partitioning of the network. Oftentimes, for such networks, one aims to find a k-partitioning with a smaller cut value by moving only a few nodes across partitions. The number of nodes that can be moved across partitions is often a constraint forced by budgetary limitations. Motivated by such real-world applications, we introduce and study the r-move k-partitioning problem, a natural variant of the Multiway cut problem. Given a graph, a set of k terminals and an initial partitioning of the graph, the r-move k-partitioning problem aims to find a k-partitioning with the minimum-weighted cut among all the k-partitionings that can be obtained by moving at most r non-terminal nodes to partitions different from their initial ones. Our main result is a polynomial time 3(r+1) approximation algorithm for this problem. We further show that this problem is W[1]-hard, and give an FPTAS for when r is a small constant.