An improved local search based algorithm for $k^-$-star partition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911103518244864 |
|---|---|
| author | Gong, Mingyang Lin, Guohui Mumey, Brendan |
| author_facet | Gong, Mingyang Lin, Guohui Mumey, Brendan |
| contents | We study the $k^-$-star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most $k$ vertices to cover all vertices in a simple undirected graph $G = (V, E)$. Our main contribution is an improved $O(|V|^3)$-time $(\frac k2 - \frac {k-2}{8k-14})$-approximation algorithm.
Our algorithm starts with a $k^-$-star partition with the least $1$-stars and a key idea is to distinguish critical vertices, each of which is either in a $2$-star or is the center of a $3$-star in the current solution. Our algorithm iteratively updates the solution by three local search operations so that the vertices in each star in the final solution produced cannot be adjacent to too many critical vertices. We present an amortization scheme to prove the approximation ratio in which the critical vertices are allowed to receive more tokens from the optimal solution. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_09361 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An improved local search based algorithm for $k^-$-star partition Gong, Mingyang Lin, Guohui Mumey, Brendan Data Structures and Algorithms F.2.2 We study the $k^-$-star partition problem that aims to find a minimum collection of vertex-disjoint stars, each having at most $k$ vertices to cover all vertices in a simple undirected graph $G = (V, E)$. Our main contribution is an improved $O(|V|^3)$-time $(\frac k2 - \frac {k-2}{8k-14})$-approximation algorithm. Our algorithm starts with a $k^-$-star partition with the least $1$-stars and a key idea is to distinguish critical vertices, each of which is either in a $2$-star or is the center of a $3$-star in the current solution. Our algorithm iteratively updates the solution by three local search operations so that the vertices in each star in the final solution produced cannot be adjacent to too many critical vertices. We present an amortization scheme to prove the approximation ratio in which the critical vertices are allowed to receive more tokens from the optimal solution. |
| title | An improved local search based algorithm for $k^-$-star partition |
| topic | Data Structures and Algorithms F.2.2 |
| url | https://arxiv.org/abs/2508.09361 |