2
$\begingroup$

I am not sure I understand correctly the following assertion (source):

For all $\epsilon > 0$, approximating the chromatic number within $n^{1−\epsilon}$ is NP-hard.

Does this mean that, for any given graph G, it is NP-hard to decide whether G is $k$-colorable with $k<n$ given colors?

Otherwise, could you explain it in layman terms? Thanks!

$\endgroup$
7
  • 1
    $\begingroup$ No. The statement doesn't say anything about $k = \frac{n}{\log n}$. In fact, If you follow the links, you'll find the original paper theoryofcomputing.org/articles/v003a006/v003a006.pdf, which says "The best approximation algorithms for these problems [MAX CLIQUE and CHROMATIC NUMBER] give approximation ratios of the form $n/polylog(n)$" $\endgroup$
    – Dmitry
    Commented Nov 29, 2021 at 11:57
  • $\begingroup$ For any fixed $\epsilon$, there exists $n_0$ such that for all $n \ge n_0$ you have $n^{1-\epsilon} < \frac{n}{\log n}$. I.e. for $n \ge n_0$, it may be possible to approximate within factor $\frac{n}{\log n}$, but not within factor $n^{1-\epsilon}$. $\endgroup$
    – Dmitry
    Commented Nov 29, 2021 at 12:03
  • $\begingroup$ Sorry, I guess I don't understand "approximate within". Does this mean that the optimal solution is guaranteed to be less than a multiplicative factor of the returned solution? $\endgroup$
    – Aristide
    Commented Nov 29, 2021 at 12:41
  • $\begingroup$ For minimization problems, If the approximation factor of your algorithm is $\alpha$, and your algorithm returns $x$, then it's guaranteed that the optimal solution $OPT \ge \frac{x}{\alpha}$ $\endgroup$
    – Dmitry
    Commented Nov 29, 2021 at 12:56
  • 1
    $\begingroup$ For a $n^{1-\epsilon}$-approximation algorithm (which, as the paper says, probably doesn't exist), yes. Yes, $32 > 10$, which means that in this case, you don't get anything nontrivial. But e.g. for $n = 1000,\chi=1,\epsilon=0.1$, you get a nontrivial $k=500$. I also suspect that the paper actually meant $O(n^{1-\epsilon})$, so talking about specific (and especially small) values is a bit meaningless. $\endgroup$
    – Dmitry
    Commented Nov 29, 2021 at 13:36

1 Answer 1

5
$\begingroup$

It is unfortunate that papers in hardness of approximation use this kind of phrasing, since it is rather inaccurate. Here is what the paper actually proves (see the proof of Theorem 1.2 on page 118):

For every $\epsilon > 0$ and any language $L$ in NP there is a polytime reduction $f$, whose output is a graph on $n$ vertices, such that:

  • If $x \in L$ then $f(x)$ has chromatic number at most $n^\epsilon$.
  • If $x \notin L$ then $f(x)$ has chromatic number at least $n^{1-\epsilon}$.

(This actually corresponds to a factor of $n^{1-2\epsilon}$, but since $\epsilon$ is arbitrary, it makes no difference.)


A different way to express this is using promise problems. A promise problem $L = (L_+,L_-)$ consists of two disjoint sets $L_+,L_-$, which we think of as Yes instances and No instances. Every language $L$ naturally corresponds to the promise problem $(L,\overline{L})$.

A promise problem $L = (L_+,L_-)$ is in NP if there exists a nondeterministic polytime algorithm $f$ such that if $x \in L_+$ then $f(x) = 1$, and if $x \notin L_-$ then $f(x) = 0$. Equivalently, there is a polytime algorithm $f$ and a polynomial bound $p$ such that:

  • If $x \in L_+$ then there exists $y$ of length at most $p(|x|)$ such that $f(x,y) = 1$.
  • If $x \in L_-$ then for all $y$ of length at most $p(|x|)$, we have $f(x,y) = 0$.

A promise problem $L = (L_+,L_-)$ is NP-hard if for any promise problem $L' = (L'_+,L'_-)$ in NP there is a polytime reduction $f$ such that:

  • If $x \in L'_+$ then $f(x) \in L_+$.
  • If $x \in L'_-$ then $f(x) \in L_-$.

A promise problem is NP-complete if it is both in NP and NP-hard. What the paper shows is that for every $\epsilon > 0$, the following promise problem $L_\epsilon = (L_{\epsilon,+},L_{\epsilon,-})$ is NP-hard, and so NP-complete:

  • $L_{\epsilon,+}$ consists of all graphs on $n$ vertices whose chromatic number is at most $n^\epsilon$.
  • $L_{\epsilon,-}$ consists of all graphs on $n$ vertices whose chromatic number is at least $n^{1-\epsilon}$.

There is one more way to formulate the inapproximability result, more vaguely:

If there exists $\epsilon > 0$ and a polynomial time algorithm for computing the chromatic number whose approximation ratio is at most $n^{1-\epsilon}$ then P=NP.

Here an algorithm for computing the chromatic number has approximation ratio $\rho(n)$ if for graphs on $n$ vertices, it outputs a number which is between $\chi$ and $\rho(n) \cdot \chi$, where $\chi$ is the chromatic number.

This statement can be derived from the statements above, but not vice versa.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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