# Hardness of Maximum Independent Set in 3-Colorable Graphs

Let $$G = (V,E)$$ be an undirected graph such that there is a proper coloring of the vertices of $$G$$ in three colors.

Question: In such graphs, are there known results for the hardness of finding a maximum independent set? e.g., can one find an Independent set of cardinality at least $$\varepsilon \cdot |V|$$ in polynomial time for some constant $$\varepsilon>0$$?

As detailed below, the problem of finding an independent set of size $$\Omega(n^{1-\delta})$$ in 3-colorable graphs is essentially equivalent to $$O(n^\delta)$$-approximating 3-COLOR. Currently, the best poly-time approximation ratio known to be achievable for 3-COLOR is $$O(n^\delta)$$ for $$\delta>0.19$$. If you could find independent sets of size $$\Omega(n^{0.81})$$ in 3-colorable graphs in polynomial time, you could achieve a poly-time approximation ratio of $$O(n^{0.19})$$ for 3-COLOR, beating the best current ratio.

(Here, by $$f(n)$$-approximating 3-COLOR, I mean the following problem: given a 3-colorable graph with $$n$$ vertices, find a coloring of size at most $$3f(n)$$.

Lemma 1. Fix any constant $$\delta>0$$. There is a poly-time $$O(n^\delta)$$-approximation algorithm for 3-COLOR if and only if there is a poly-time algorithm for finding an independent set of size $$\Omega(n^{1-\delta})$$ in any given 3-colorable graph.

Proof. The "only if" direction is easy. Just compute a coloring that uses at most $$O(n^\delta)$$ colors and return the largest color class. This is necessarily an independent set of size at least $$\Omega(n/n^{\delta}) = \Omega(n^{1-\delta})$$.

The "if" direction is not much harder. Suppose that algorithm $$A$$ finds an independent set of size $$\Omega(n^{1-\delta})$$ in any given 3-colorable graph in polynomial time. Given a graph $$G=(V, E)$$, define algorithm $$B$$ to find a coloring for $$G$$ as follows: use $$A$$ to find a large independent set $$S$$ in $$G$$, recurse on the graph $$G'$$ obtained by deleting the vertices in $$S$$ from $$G$$ to find a coloring of $$G'$$, then add $$S$$ as a new color to this coloring to produce a coloring of $$G$$. (Of course the base case is when the graph has no vertices.) Note that $$G'$$ is 3-colorable, so the algorithm is well-defined.

Let $$C(n)$$ be the maximum number of colors $$B$$ uses to color any 3-colorable $$n$$-vertex graph. Then $$C(0) = 0$$ and for $$n\ge 1$$ we have $$C(n) \le 1 + C(\lfloor n - \Omega(n^{1-\delta})\rfloor).$$ Expanding the recurrence $$O((n/2)^\delta)$$ times until the argument has size at most $$n/2$$ we have $$C(n) \le O((n/2)^\delta) + C(n/2).$$ Expanding this in turn gives the bound $$C(n) \le O\big(\sum_{i\ge 1} (n/2^i)^\delta\big) = O(n^\delta/\delta) = O(n^\delta).~~~~~\Box$$

The best poly-time approximation algorithms known for 3-COLOR are apparently $$O(n^{\delta})$$-approximation algorithms for $$\delta > 0.19$$. (For a good survey of these results see the introduction of this paper.) If you could find independent sets of size $$\Omega(n^{0.81})$$ in 3-colorable graphs in polynomial time, this would directly yield an $$O(n^{0.19})$$-approximation algorithm for 3-COLOR, better than these currently known results.

For graph coloring in general, Lund and Yannakakis showed that, unless P=NP, for some constant $$\delta > 0$$, there is no polynomial-time $$O(n^\delta)$$-approximation algorithm for coloring. This may hold for 3-COLOR as well, but as far as I know this has not yet been shown. A quick search turns up a couple of recent hardness results: this and this.

• Thank you very much for answering my question and for the detailed survey. A follow-up question if I may: Would the problem remains as hard (or, at least without a known algorithm) if each vertex $v \in V$ has a degree at least $d(v) \geq \Omega(\delta \cdot n)$?
– John
Nov 28, 2022 at 10:44
• Not as hard, I think. For example, you could do something like the following. Given a 3-colorable graph $G$, let $d$ be the maximum degree of any vertex in $G$ and let $v$ be a vertex of degree $d$. Find a 2-coloring $C$ of the neighbor set of $v$ (this must exist and can be found in linear time). Return the larger of the two color classes in $C$. Then each color class in $C$ is an independent set, and the largest one has size at least $d/2$, so this linear-time algorithm returns an independent set of size at least $d/2$. In your case this is $\Omega(\delta n)$. Probably can do better. Nov 28, 2022 at 15:17
• Thank you!, this was helpful:)
– John
Nov 28, 2022 at 18:06