<p>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 <a href="https://www.nada.kth.se/~austrin/papers/sparse_vc_cc09.pdf" rel="nofollow noreferrer">Unique Games-hard</a> 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}$.) </p>

<p>However, it's still interesting to close these logarithmic gaps. This <a href="https://epubs.siam.org/doi/10.1137/1.9781611973730.1" rel="nofollow noreferrer">paper by Bansal</a> may contain useful ideas.</p>

CC BY-SA 3.0
2018-03-20T20:09:24.157Z
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.
YOUSEFY
CC BY-SA 3.0
2018-03-20T21:22:01.690Z
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
CC BY-SA 3.0
2018-03-20T18:06:19.310Z
2018-03-20T18:06:19.310Z
Sasho Nikolov
<p>I would like to know any results in terms of approximation algorithm about Maximum weight Independent Set problem in coloring graph.</p>
<blockquote>
<p>Input: Given a graph G with non-negative vertex weights and valid but not important to be optimal coloring of G.</p>
<p>Task: Find the Maximum weight Independent Set.</p>
</blockquote>
<p>Note that this problem is NP-hard (for k&gt;2 where k is the number of coloring) [see <a href="https://cstheory.stackexchange.com/a/10987/29303">here]
</a></p>
<p>in <a href="https://dl.acm.org/citation.cfm?id=241941" rel="nofollow noreferrer">Hochbaum's paper</a> in 1996 &quot;Approximating Covering and Packing Problems: Set Cover, Vertex Cover, Independent Set, and related problems&quot; in Theorem 3.2 he give an (2/k)-approximation algorithm for this problem.</p>
<p>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.</p>
<p>Thank you!</p>

<graph-theory><approximation-algorithms><approximation-hardness>
Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?
YOUSEFY
# Is there any better than (2/k)-approximation algorithm for Independent Set in Coloring graph?

(Asked by: username_0 on 2018-03-20)

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]](https://cstheory.stackexchange.com/a/10987/29303)

in [Hochbaum's paper](https://dl.acm.org/citation.cfm?id=241941) 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!

**Tags:** graph-theory, approximation-algorithms, approximation-hardness


---

## 1 answers

### Answer by username_1 on 2018-03-20. Score: 1 | Accepted answer

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](https://www.nada.kth.se/~austrin/papers/sparse_vc_cc09.pdf) 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](https://epubs.siam.org/doi/10.1137/1.9781611973730.1) may contain useful ideas.

> **Comments:**
> **username_0**: 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.  
> **username_1**: 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$.  

---

