|
| | | | |
| | | |
| Stat |
Members: 3669
Articles: 2'599'751
Articles rated: 2609
16 March 2025 |
|
| | | | |
|
Article overview
| |
|
|
Maximum $k$- vs. $ell$-colourings of graphs | | Tamio-Vesa Nakajima
; Stanislav Živný
; | | Date: |
1 Nov 2023 | | Abstract: | We present polynomial-time SDP-based algorithms for the following problem: For fixed $k leq ell$, given a real number $epsilon>0$ and a graph $G$ that admits a $k$-colouring with a $
ho$-fraction of the edges coloured properly, it returns an $ell$-colouring of $G$ with an $(alpha
ho - epsilon)$-fraction of the edges coloured properly in polynomial time in $G$ and $1 / epsilon$. Our algorithms are based on the algorithms of Frieze and Jerrum [Algorithmica'97] and of Karger, Motwani and Sudan [JACM'98].
For $k = 2, ell = 3$, our algorithm achieves an approximation ratio $alpha = 1$, which is the best possible. When $k$ is fixed and $ell$ grows large, our algorithm achieves an approximation ratio of $alpha = 1 - o(1 / ell)$. When $k, ell$ are both large, our algorithm achieves an approximation ratio of $alpha = 1 - 1 / ell + 2 ln ell / k ell - o(ln ell / k ell) - O(1 / k^2)$; if we fix $d = ell - k$ and allow $k, ell$ to grow large, this is $alpha = 1 - 1 / ell + 2 ln ell / k ell - o(ln ell / k ell)$.
By extending the results of Khot, Kindler, Mossel and O'Donnell [SICOMP'07] to the promise setting, we show that for large $k$ and $ell$, assuming the Unique Games Conjecture, it is NP-hard to achieve an approximation ratio $alpha$ greater than $1 - 1 / ell + 2 ln ell / k ell + o(ln ell / k ell)$, provided that $ell$ is bounded by a function that is $o(exp(sqrt[3]{k}))$. For the case where $d = ell - k$ is fixed, this bound matches the performance of our algorithm up to $o(ln ell / k ell)$. | | Source: | arXiv, 2311.00440 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
|
| |
|
|
|
REGISTER