3
$\begingroup$

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$?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
3
  • 1
    $\begingroup$ 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)$? $\endgroup$
    – John
    Nov 28, 2022 at 10:44
  • 2
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Nov 28, 2022 at 15:17
  • 1
    $\begingroup$ Thank you!, this was helpful:) $\endgroup$
    – John
    Nov 28, 2022 at 18:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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