Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
