47
$\begingroup$

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.

$\endgroup$
12
  • $\begingroup$ There is a polynomial reduction from SAT to 3-coloring, I believe even for planar graphs (using gadget). So reduce a hard problem to SAT then to 3-color. $\endgroup$
    – joro
    May 30, 2014 at 14:00
  • $\begingroup$ @Joro Yes, I know coloring is hard. But does your procedure answer the question? We need one graph of each size. $\endgroup$ May 30, 2014 at 14:01
  • 3
    $\begingroup$ Isn't the answer to 1) "we don't know" for trivial reasons: if P = NP, then there is a polynomial time algorithm that computes the chromatic number of any graph, right? $\endgroup$ May 30, 2014 at 21:35
  • 1
    $\begingroup$ @SamHopkins You are right! There is a hidden $\text{P}\neq\text{NP}$ assumption in my question. I think Emil also alluded to this issue, since I might instead have asked for NP-completeness instead merely of the absence of polynomial time solutions. $\endgroup$ May 31, 2014 at 3:24
  • 1
    $\begingroup$ Another interesting question would be, whether humans generally also have more difficulty coloring instances, that are classified as being hard, than those, which are not (provided the size of the instances is amenable to humans). $\endgroup$ May 31, 2014 at 13:41

7 Answers 7

19
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I didn’t feel like explaining it in detail, but Q.2 can be answered in a similar way as Q.1. Let TFNE and FE be the exponential-time analogues of TFNP and FP. (I’ve never seen exponential search problems in the literature, so they are probably not very popular.) By usual arguments, $E\ne NE\cap coNE\to TFNE\ne FE\to TFNP\ne FP\to P\ne NP$. One can show that Q.2 is equivalent to $TFNE\ne FE$, using the fact that standard reductions of NP problems to 3-colourability also work as search problem reductions (one can recover a solution to the original problem from a colouring in polynomial time). $\endgroup$ May 31, 2014 at 22:47
28
$\begingroup$

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.

$\endgroup$
1
  • 10
    $\begingroup$ To be more specific, you can 4-color a planar graph in time quadratic in the number of vertices: Robertson, Neil, et al. "Efficiently four-coloring planar graphs." Proceedings 28th ACM Symposium on Theory of Computing. ACM, 1996. $\endgroup$ May 31, 2014 at 0:08
12
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ Thanks very much! Could you link to a source for the reduction of factoring to coloring? $\endgroup$ May 30, 2014 at 16:11
  • 3
    $\begingroup$ As far as I can see, this just begs the question with a different NP problem. How do you intend to generate hard instances of factoring by a polytime algorithm using only a length parameter as input? In fact, such an algorithm can never produce instances hard according to cryptographers’ standards, as any sparse language is trivially in P/poly. $\endgroup$ May 30, 2014 at 21:11
  • 6
    $\begingroup$ @EmilJeřábek: You're right; I have not answered the question of how to generate instances that are "hard" according to any asymptotic definition of hardness such as "NP" or "not polytime". I'm only showing how to create specific instances that are "hard" in the sense of "believed to require (say) 2^1024 bit operations in the absence of knowledge of the prime factors." This is not mathematically precise but it has the advantage of providing some practical confidence that the specific instance is "hard" rather than just being a member of an infinite family that is collectively hard. $\endgroup$ May 30, 2014 at 22:15
  • 2
    $\begingroup$ (continued) I believe this is closer to the intuition of "producing hard instances of a desired size." No asymptotic definition of hardness can ever say that a specific instance of a specific size is "hard" in isolation since such a thing is always solvable in constant time. $\endgroup$ May 30, 2014 at 22:18
  • 2
    $\begingroup$ @JoelDavidHamkins for reduction from factoring to SAT you can use the program Tough SAT (there is source too): toughsat.appspot.com $\endgroup$
    – joro
    May 31, 2014 at 5:09
5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
17
  • $\begingroup$ “It is possible to generate such instances in polynomial time” = there exists a sparse NP-complete set. This is not known. $\endgroup$ May 30, 2014 at 15:05
  • $\begingroup$ Actually, it even implies P = NP. sciencedirect.com/science/article/pii/0022000082900022 $\endgroup$ May 30, 2014 at 15:11
  • $\begingroup$ Thanks for your answer, but actually I'm not fully clear on your procedure. Are you ultimately reducing only some instances of 3-Sat to instances of graph-coloring? If so, could you explain why those instances have the hardness property I am requesting? (And @EmilJeřábek, could you explain your remarks a little more?) $\endgroup$ May 30, 2014 at 15:12
  • $\begingroup$ @JoelDavidHamkins it is evening here, will try to find references tomorrow. The SAT competition has challenge for RANDOM SAT and some solvers failed: satcompetition.org $\endgroup$
    – joro
    May 30, 2014 at 15:27
  • $\begingroup$ @EmilJeřábek it is evening here, will try to find references tomorrow. The SAT competition has challenge for RANDOM SAT and some solvers failed: satcompetition.org $\endgroup$
    – joro
    May 30, 2014 at 15:30
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ theory says 16th degrees are five colorable. but practically unsolvable. $\endgroup$ Sep 26, 2021 at 0:20

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.