Graph Partitioning With Limited Moves
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913241621331968 |
|---|---|
| author | Behbahani, Majid Dalirrooyfard, Mina Fata, Elaheh Nevmyvaka, Yuriy |
| author_facet | Behbahani, Majid Dalirrooyfard, Mina Fata, Elaheh Nevmyvaka, Yuriy |
| contents | In many real world networks, there already exists a (not necessarily optimal) $k$-partitioning of the network. Oftentimes, one aims to find a $k$-partitioning with a smaller cut value for such networks 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_15485 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Graph Partitioning With Limited Moves Behbahani, Majid Dalirrooyfard, Mina Fata, Elaheh Nevmyvaka, Yuriy Data Structures and Algorithms In many real world networks, there already exists a (not necessarily optimal) $k$-partitioning of the network. Oftentimes, one aims to find a $k$-partitioning with a smaller cut value for such networks 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. |
| title | Graph Partitioning With Limited Moves |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2402.15485 |