Graph Partitioning with a Move Budget

Mina Dalirrooyfard, Elaheh Fata, Majid Behbahani, Yuriy Nevmyvaka
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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v238-dalirrooyfard24a, title = {Graph Partitioning with a Move Budget}, author = {Dalirrooyfard, Mina and Fata, Elaheh and Behbahani, Majid and Nevmyvaka, Yuriy}, booktitle = {Proceedings of The 27th International Conference on Artificial Intelligence and Statistics}, pages = {568--576}, year = {2024}, editor = {Dasgupta, Sanjoy and Mandt, Stephan and Li, Yingzhen}, volume = {238}, series = {Proceedings of Machine Learning Research}, month = {02--04 May}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v238/dalirrooyfard24a/dalirrooyfard24a.pdf}, url = {https://proceedings.mlr.press/v238/dalirrooyfard24a.html}, 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.} }
Endnote
%0 Conference Paper %T Graph Partitioning with a Move Budget %A Mina Dalirrooyfard %A Elaheh Fata %A Majid Behbahani %A Yuriy Nevmyvaka %B Proceedings of The 27th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2024 %E Sanjoy Dasgupta %E Stephan Mandt %E Yingzhen Li %F pmlr-v238-dalirrooyfard24a %I PMLR %P 568--576 %U https://proceedings.mlr.press/v238/dalirrooyfard24a.html %V 238 %X 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.
APA
Dalirrooyfard, M., Fata, E., Behbahani, M. & Nevmyvaka, Y.. (2024). Graph Partitioning with a Move Budget. Proceedings of The 27th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 238:568-576 Available from https://proceedings.mlr.press/v238/dalirrooyfard24a.html.

Related Material