Parameterized Local Search for Max $c$-Cut
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866916402953191424 |
|---|---|
| author | Garvardt, Jaroslav Grüttemeier, Niels Komusiewicz, Christian Morawietz, Nils |
| author_facet | Garvardt, Jaroslav Grüttemeier, Niels Komusiewicz, Christian Morawietz, Nils |
| contents | In the NP-hard Max $c$-Cut problem, one is given an undirected edge-weighted graph $G$ and aims to color the vertices of $G$ with $c$ colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $c=2$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max $c$-Cut where we are also given a vertex coloring and an integer $k$ and the task is to find a better coloring that changes the color of at most $k$ vertices, if such a coloring exists; otherwise, the given coloring is $k$-optimal. We show that, for all $c\ge 2$, LS Max $c$-Cut presumably cannot be solved in $f(k)\cdot n^{\mathcal{O}(1)}$ time even on bipartite graphs. We then present an algorithm for LS Max $c$-Cut with running time $\mathcal{O}((3eΔ)^k\cdot c\cdot k^3\cdotΔ\cdot n)$, where $Δ$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max $c$-Cut. We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_13380 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Local Search for Max $c$-Cut Garvardt, Jaroslav Grüttemeier, Niels Komusiewicz, Christian Morawietz, Nils Computational Complexity In the NP-hard Max $c$-Cut problem, one is given an undirected edge-weighted graph $G$ and aims to color the vertices of $G$ with $c$ colors such that the total weight of edges with distinctly colored endpoints is maximal. The case with $c=2$ is the famous Max Cut problem. To deal with the NP-hardness of this problem, we study parameterized local search algorithms. More precisely, we study LS Max $c$-Cut where we are also given a vertex coloring and an integer $k$ and the task is to find a better coloring that changes the color of at most $k$ vertices, if such a coloring exists; otherwise, the given coloring is $k$-optimal. We show that, for all $c\ge 2$, LS Max $c$-Cut presumably cannot be solved in $f(k)\cdot n^{\mathcal{O}(1)}$ time even on bipartite graphs. We then present an algorithm for LS Max $c$-Cut with running time $\mathcal{O}((3eΔ)^k\cdot c\cdot k^3\cdotΔ\cdot n)$, where $Δ$ is the maximum degree of the input graph. Finally, we evaluate the practical performance of this algorithm in a hill-climbing approach as a post-processing for a state-of-the-art heuristic for Max $c$-Cut. We show that using parameterized local search, the results of this state-of-the-art heuristic can be further improved on a set of standard benchmark instances. |
| title | Parameterized Local Search for Max $c$-Cut |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2409.13380 |