Maximum $k$- vs. $\ell$-colourings of graphs

Abstract

We present polynomial-time SDP-based algorithms for the following problem: For fixed $k\le \ell$, given a real number $\hat{I}\mu >0$ and a graph $G$ that admits a $k$-colouring with a $\ddot{I}$-fraction of the edges coloured properly, it returns an $\ell$-colouring of $G$ with an $(\hat{I}\pm \ddot{I}-\hat{I}\mu )$-fraction of the edges coloured properly in polynomial time in $G$ and $1/\hat{I}\mu$. Our algorithms are based on the algorithms of Frieze and Jerrum [Algorithmica'97] and of Karger, Motwani and Sudan [JACM'98]. When $k$ is fixed and $\ell$ grows large, our algorithm achieves an approximation ratio of $\hat{I}\pm =1-o(1/\ell )$. When $k,\ell$ are both large, our algorithm achieves an approximation ratio of $\hat{I}\pm =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 $\hat{I}\pm =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 Khot's Unique Games Conjecture (\UGC), it is \NP-hard to achieve an approximation ratio $\hat{I}\pm$ 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 )$. Furthermore, by extending the results of Guruswami and Sinop [ToC'13] to the promise setting, we prove that it is \NP-hard to achieve an approximation ratio greater than $1-1/\ell +8\ln \ell /k\ell +o(\ln \ell /k\ell )$, provided again that $\ell$ is bounded as before (but this time without assuming the \UGC).