6
$\begingroup$

In paper Approximation Algorithms for the Chromatic Sum, page 18, authors state that based on the fact that the Graph Coloring problem is hard to approximate with a ratio less than 2 (under the assumption of $P \neq NP$), it's easy to show that for any constant $k$, there is no approximate algorithm $A$ to Graph Coloring such that $\chi(G) \leq A(G) \leq \chi(G) + k$.

But i can't see how to show/prove this.

As i see, it isn't so direct, because for any $k$, there are graphs such that $\chi(G) \leq k$, so for them $\chi(G) + k \geq 2 \cdot \chi(G)$ and it would be $(2 + \epsilon)$-approximative, for some $\epsilon \geq 0$, for these graphs.

So i'm asking for some help/advice on how to show/prove this.

$\endgroup$
  • 1
    $\begingroup$ I regularly ask this problem on exams. You don't even need hadness of approximation; there is a simple argument directly from the exact problem's NP-hardness. Given a graph G, consider a graph H consisting of 2k distinct copies of G, with edges between any two vertices in distinct copies. If $\chi(H)\le x \le \chi(H)+ k$, then $\chi(G) = \lfloor x/k \rfloor$. $\endgroup$ – Jeffε Apr 26 '11 at 1:26
11
$\begingroup$

Let $G$, with $\chi(G) \geq 3$ (otherwise you have an exact algorithm).

Now construct a graph $H$ consisting of $k$ copies $G_1,\ldots,G_k$ of $G$, with all possible edges between $u$ and $v$ for $u \in G_i$, $v \in G_j$, $i\not=j$.

Now use the additive constant algorithm for the graph $H$, which will find a coloring of, at most, $k\cdot\chi(G) + k$ colors. Since the colors in each copy of $G$ will be distinct, by the Pigeonhole principle, you have one of the copies with at most $\chi(G)+1$ distinct colors, which is better than a 2-approximation.

$\endgroup$
2
$\begingroup$

It is easy to show hardness of additive approximation based on nonconstant multiplicative inapproximability bounds, which are known.

My guess is that they were thinking of the following construction: starting from a graph G that is hard to color, replace every vertex by a k-clique. If it were true that this replacement multiplies the chromatic number by k, then it would be hard to find an additive approximation to the coloring of the larger graph. But, it's not true; e.g. C5 requires three colors but 2xC5 requires only five, not six.

$\endgroup$
  • 2
    $\begingroup$ This actually approaches $k$ times the fractional chromatic number as $k$ grows. You want to join together $k$ copies of the graph, instead. The strong product of $K_2$ and $C_5$, for example, is 5, which two joined copies of $C_5$ have chromatic number 6. $\endgroup$ – Andrew D. King Apr 25 '11 at 22:35

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.