Is it easy to produce hard-to-color graphs?

Question

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each child drew a graph as a challenge, to be colored by her partner, using the fewest possible number of colors. In another activity, the children produced maps to be 4-colored by their partners.

My question here concerns the actual computational difficulty of these tasks.

Question. Is it easy to come up with hard-to-color graphs? More precisely:

1. Is there a polynomial-time algorithm (in the desired number of vertices) that produces graphs $\Gamma_n$ with $n$ vertices on input $n$, such that there is no polynomial-time algorithm that computes the chromatic numbers of those graphs?

2. Is there a polynomial-time algorithm producing graphs $\Delta_n$ with $n$ vertices and stating the chromatic number $c_n$ of $\Delta_n$, such that there is no polynomial-time algorithm producing a $c_n$-coloring of $\Delta_n$?

3. Is there a polynomial-time algorithm (in the desired number of countries) that produces maps (planar graphs) of a desired size, such that there is no polynomial-time algorithm that computes 4-colorings of those maps?

Evidently, graph-coloring is hard in general. But is it easy to produce hard instances of a desired size?

If there are affirmative answers, then one could impose further requirements, such as insisting that there is no infinite subsets of the graphs that admit a polynomial-time algorithm computing the chromatic numbers or the colorings. This would be a sense in which nearly every instance is hard.

Answer 1

If $n\mapsto\Gamma_n$ is a function that on input $n$ produces a graph of size $n$ in time polynomial in $n$, its range is a sparse polynomial-time set, meaning that it contains only polynomially many (actually, at most $1$ in this case) elements of any given size. Thus, if $n$ is given in unary, the set $X$ of pairs $(n,c)$ such that $\Gamma_n$ is $c$-colourable is a sparse NP set. If we instead give $n$ in binary, it becomes an NE set, and $X$ is computable in time polynomial in $n$ iff its binary version is in E.

Thus, a positive answer to question 1 implies $\mathrm E \ne \mathrm{NE}$, which is a stronger assumption than $\mathrm P \ne \mathrm{NP}$.

Conversely, if $\mathrm E \ne \mathrm{NE}$, let us fix a language $L$ in $\mathrm{NE}\smallsetminus\mathrm E$ consisting of binary integers. Then the set of unary encodings of elements of $L$ is in $\mathrm{NP}\smallsetminus\mathrm P$, and by the NP-completeness of 3-colourability, we can find a polynomial-time function $1^m\mapsto\Gamma'_m$ (that is, a function $m\mapsto\Gamma'_m$ computable in time polynomial in $m$) such that $m\in L$ iff $\Gamma'_m$ is 3-colourable. The size of $\Gamma'_m$ is polynomial in $m$; we can easily arrange that it is at least $m$, and a strictly increasing function of $m$. Define $\Gamma_n$ as $\Gamma'_m$ if $m\le n$ is such that $|\Gamma'_m|=n$, and (say) the empty graph if there is no such $m$. Then $\Gamma_n$ is computable in time $n^{O(1)}$, but it's 3-colourability cannot be determined by a poly-time algorithm.

Answer 2

Since nobody seems to have addressed question 3, I will. The proofs of the 4-colour theorem are effective in the sense that they can be turned into polynomial-time algorithms. So there are no planar graphs for which 4-colouring is hard.

Answer 3

In practice, if you want to make sure that every instance is hard, then you should look to cryptography. For example, take two large primes, making sure to consult your cryptography textbook to avoid all the known pitfalls, and ask for a factorization of the product. Convert this to a graph-coloring problem using the usual reductions. If the graph doesn't have the correct number of vertices, then add a bunch of isolated vertices to pad it out.

This procedure has the advantage that every instance will actually be difficult in practice, not just that your family of instances will be asymptotically hard in the worst case. However, the theory of non-asymptotic complexity theory is currently very underdeveloped, so we don't have any good way of stating the theoretical assumptions needed to prove that every such instance is hard.

Answer 4

See the following papers:

1) IF NP LANGUAGES ARE HARD ON THE WORST-CASE, THEN IT IS EASY TO FIND THEIR HARD INSTANCES, Dan Gutfreund, Ronen Shaltiel, and Amnon Ta-Shma, Journal of Computational Complexity, 2007.

2) Finding hard instances of the satisfiability problem: a survey, Cook and Mitchell, 1996-7.

Also there are some other papers that use "randomness" to generate hard instances.

Answer 5

in general to prove that it is really "hard" to color any set of graphs (even those that could take long to generate!) is equivalent to the P=?NP question and usually/often these problems stay nearly as hard even with additional information like the known chromatic number although that is a more specialized case maybe not studied as much. here are some more experimentally-derived observations that cross much research and many papers.

• there are "apparently hard instance generators" that run in P-time. one of the simplest to implement is factoring. eg a factoring algorithm can be built usually in the SATisfiability problem most easily, and those instances can be converted to graph coloring via standard transformations (P-time). if the instances are proven hard or easy, either way is a theoretical breakthrough, and factoring is conjectured to be outside of P (and various cryptographic security systems like RSA depend on that fact). there are a few papers studying this. see eg reducing integer factoring to NP complete problem cs.se

• there is a concept of a "transition point" that seems to be applicable to all NP-complete problems, an "easy-hard-easy" transition as a parameter of the problem varies proportionally and instances are chosen ("uniformly") at random at the particular dimensions. for SAT it occurs at a clause/variable ratio. for coloring it occurs for something like edge density; SAT transition point has been studied much more however coloring transition point has been studied in a few papers. unf have not found a great survey but this PPT / Phase transition behavior by Walsh is excellent.

Answer 6

I believe for all sufficiently large $n$ it is possible to produce graphs on $n$ vertices for which determining if the chromatic number is $3$ is hard via reduction from 3-SAT.

For all $m$ sufficiently large, 3-SAT with $m$ variables and $[cm]$ clauses (for some explicit $c$) is hard and it is possible to generate such instances in polynomial time. There is polynomial reduction from 3-SAT to 3-COLOR where the number of vertices $n$ is $n=f(c,m)$ where $f$ is polynomial in $m$ (IIRC quadratic).

So given $n$, choose the largest $m$, s.t. $f(c,m) \le n$, generate hard 3-SAT with $m$ variables and $[cm]$ clauses and encode to 3-COLOR. Add a disjoint copy of bipartite graph of order $ n - f(c,m) $ to make the order $n$.

---

On the other hand, I believe for randomly generated graphs and naively generated 3-SAT, both coloring and satisfiability would be efficient for state of the art solvers.

---

Added

Joel David Hamkins asked about the proof of hardness the SAT instances.

Maybe this can be made rigorous.

From this paper Hard Instance Generation for SAT

define a reduction that produces, from $n$ bit FACTORING instances, SAT instances in the conjunctive normal form with $O(n^{1+\epsilon})$ variables, where $\epsilon > 0$ is any fixed constant.

This gives instances of graphs of order $poly(n)$ and by adding bipartite graphs one covers all orders $n$ sufficiently large.

Consider this game: Joel picks integer $n$. I find the largest $m$ such that the encoding to coloring of factoring $m$ bit integer is on less than $n$ vertices. $n$ is polynomial in $m$. I pick two random $m/2$ bit primes, multiply them, encode to SAT then to COLOR and add a bipartite graph to match $n$. Finding coloring in the graph of order $n$ will factor $m$ bit integer.

Probably something similar can be done with crypto hash functions.

From the SAT competition I have the impression that RANDOM SAT with the right threshold or RANDOM SAT with forced unique solution is hard for current state of the art solvers.

Answer 7

Random Ninth degree graphs get incredibly hard but solvable, four colorable, as N grows. Random Fifth degree graphs get incredibly hard but solvable, three coloring, as N grows.