# Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.

Input: Given a graph G with non-negative vertex weights and valid but not important to be optimal coloring of G.

Task: Find the Maximum weight Independent Set.

Note that this problem is NP-hard (for k>2 where k is the number of coloring) [see here]

in Hochbaum's paper in 1996 "Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and related problems" in Theorem 3.2 he give an (2/k)-approximation algorithm for this problem.

Now, my question is: Is there any new results regarding this problem? Is there any lower bound for this problem? Of course in general for simple graph without coloring to find Independent Set, there is no constant factor unless P=NP. Now, Is it true that we cannot have a constant factor for this coloring case? anything related to this problem, it would be nice to mention it here.

Thank you!

If you have a graph with maximum degree $\Delta$, then the greedy algorithm finds a coloring with $\Delta+1$ colors, so for $k = \Delta+1$ the assumption that you are given a proper $k$-coloring does not change the complexity of the problem. It is known that independent set is NP-hard to approximate within factor $\Delta^{1 - o(1)}$, and Unique Games-hard to approximate within factor $\frac{\Delta}{O(\log^2\Delta)}$, which, for $k=\Delta$ is within a $\log \Delta$ factor from the upper bound you cite. (I prefer to write approximation factors as bigger than 1, so I am thinking of the upper bound you cite as $\frac{k}{2}$.)
• I am saying that IS without any coloring, and IS when given a coloring using $\Delta+1$ colors have the same approximability. The reason is that in that case the coloring is efficiently computable anyways. By the same reasoning, vertex cover can be approximated to within a factor $2 - \frac{2}{\Delta+1}$. The UG hardness results build graphs with large $\Delta$. – Sasho Nikolov Mar 20 '18 at 21:22