1
$\begingroup$

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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

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}$.)

However, it's still interesting to close these logarithmic gaps. This paper by Bansal may contain useful ideas.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are you saying that finding IS with/without color graph have the same inapproximability? I asked this question; because Theorem 3.2 says that given a color graph, we can find vertex cover in 2-(2/k) while in simple graph, it is unique games hard to approximate better than 2. So, clearly coloring graph is easier than no-coloring graph to approximate. $\endgroup$
    – YOUSEFY
    Mar 20, 2018 at 20:09
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Sasho Nikolov
    Mar 20, 2018 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.