8

Similar question was asked before, but there was an error in it so it was left unanswered Graph class with easy chromatic number, but NP-hard coloring

Is there any infinite set of graphs $C$ such as:

  1. There is a polynomial algorithm recognizing for every graph $G$ whether $G$ belongs to $C$

  2. There is a polynomial time algorithm computing chromatic number $\chi(g)$ for every $g \in C$

  3. Humankind does not know a polynomial time algorithm for computing proper colouring for $C$, or (which is better) there is a proof that such an algorithm (under reasonable assumptions) does not exist.

Marzio De Biasi
  • 22,915
  • 2
  • 58
  • 127
Janczar Knurek
  • 81
  • 2
  • Here is also a somewhat related question; some of the answers might give some ideas: https://cstheory.stackexchange.com/questions/1848/easy-decision-problem-hard-search-problem – Jukka Suomela Sep 05 '18 at 21:05
  • Yeah, part about P_5 free graphs is interesting and useful for me, but it's not exactly what I'm talking about. – Janczar Knurek Sep 05 '18 at 21:25
  • Maybe a simpler (and weaker) question: Do you know of any result that computes a chromatic number in a purely existential way? That is, the algorithm to computer $\chi(g)$ does not explicitly (or implicitly) generate an actual colouring? I would assume probabilistic existence (existence whp) is not in the scope of this question – JimN Sep 11 '18 at 20:18

1 Answers1

4

Yes. Since 3-COLORING is FNP-complete, for any problem in FNP we can construct a graph G that is 3-colorable if and only if the problem has a solution. So you can pick your favorite problem from TFNP\FP (if it's not empty!), like finding a factor of a composite number, or a second Hamiltonian-cycle in a 3-regular graph, and convert it into a graph.

In more detail with the example of finding a factor. We will fix an algorithm that converts a composite number $N$ into a graph $G(N)$ such that from $G(N)$ you can decode the value of $N$. Compositeness of $N$ is a necessary for $G(N)$ to be in our class. Moreover, any proper $3$-coloring of $G(N)$ can be converted into a proper divisor $d$ of $N$. This can be done, e.g., by writing up a CNF that describes whether a given $d$ encoded in binary as $x_1\ldots x_{n}$ divides a fixed $N$ (that also has $n$ digits in binary, but these are not variables). From satisfiability of a CNF there is a standard reduction to 3-COLORABILITY such that you can easily convert a proper $3$-coloring back to an $x_i$ satisfying assignment. Thus solving the coloring problem, you would find a divisor $d$. Moreover, by adding some simple extra gadgets, you can also decide whether a graph is of this form or not. Our class is formed by graphs created this way, which are thus all $3$-colorable.

domotorp
  • 13,931
  • 37
  • 93
  • To be honest, I don't get your point at all... Could you please say it again, but with a little bit more formalism?

    I mean, for example I don't see how condition 1. holds in your answer...

     – Janczar Knurek Sep 06 '18 at 17:04
  • I've updated my answer. – domotorp Sep 06 '18 at 19:08
  • The property you are using is, essentially, the FNP-completeness of the search-problem variant of 3-COLORING. This does not follow just from the NP-completeness of 3-COLORING, hence the first sentence is misleading. – Emil Jeřábek Sep 06 '18 at 21:18
  • Ok, but still, there remains a problem to decide whether a graph is of this form. I understand that there are some standard tools, but I assume you did not check, but you only think they can work?

    Anyway, thanks, for an answer.

     – Janczar Knurek Sep 06 '18 at 22:52
  • @Emil Oops, I thought that it did follow! Thanks for the correction. – domotorp Sep 07 '18 at 05:33
  • @Janczar Since there are just polynomially many gadgets/vertices in G(n), we can just mark each by connecting each to some (differently sized) huge clique. – domotorp Sep 07 '18 at 05:35