6

Is there a graph class for which the chromatic number can be computed in polynomial time, but finding an actual $k$-coloring with $k=\chi(G)$ is NP-hard?

Without any further restriction the answer would be yes. For example, it is known that in the class of 3-chromatic graphs it is still NP-hard to find a 3-coloring, while the chromatic number is trivial: it is 3, by definition.

The above example, however, could be called "cheating" in a sense, because it makes the chromatic number easy by shifting the hardness to the definition of the graph class. Therefore, I think, the right question is this:

Is there a graph class that can be recognized in polynomial time, and the chromatic number of any graph $G$ in this class can also be computed in polynomial time, yet finding an actual $k=\chi(G)$-coloring for $G$ is NP-hard?

Andras Farago
  • 11,396
  • 37
  • 70
  • The definition of NP-hard is murky here, but it's not hard to argue that the existence of a (weakly) parsimonious Levin reduction from SAT to k-coloring implies that it's at least PPAD-hard. Proof sketch: Take a Nash Equilibrium instance and use a weakly parsimonious Levin reduction to SAT and then to k-coloring. Instances are recognizable because you can test if applying the two inverse mappings gives a valid NE instance. I don't know that the premise is true, however, although there at least do exist such weak parsimonious reductions. (Weakly here meaning "up to permutation of the colors") – Yonatan N Feb 07 '16 at 07:54

1 Answers1

5

I think you need to specify more carefully what you mean by "NP-hard" for a problem like this with a known solution but an unknown witness.

The most natural definition, to me, would be something like a many-one reduction, where there exist two polynomial time functions $p$ and $q$, where $p$ maps SAT instances to graphs with a known chromatic number and $q$ maps colorings of these graphs to truth values, such that $q(\chi)$ equals the correct truth value for SAT instance $X$ whenever $\chi$ is a valid optimal coloring of $p(X)$. However, this is not possible unless $\mathsf{NP}=\mathsf{coNP}$. For, if such $p$ and $q$ existed, then every unsatisfiable SAT instance $X$ would have a witness to its unsatisfiability, namely a coloring of $p(X)$.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278