The problem
The Vertex Coloring problem can be described like this:
If \(n\) is minimal for \(G\), it is called the chromatic number \(\chi(G)\).
What does that mean?
You have a graph. Then you take pencils and color the vertices such all vertices that are connected are not of the same color.
Example
All of the following graphs show valid thee colorings:
[caption id="attachment_69831" align="aligncenter" width="500"]
Valid thee colorings of one graph
Source: Wikipedia[/caption]
Interesting facts
- $1 \leq \chi(G) \leq |V|$: You need at least one color and you could color all vertices with a different color
- $\chi(K_n) = n$: All complete graphs with $n$ vertices need exactly $n$ colors. One color for each vertex.
- Every planar graph can be colored with 4 colors (see four color theorem).
- Determining if a graph can be colored with 2 colors is equivalent to determining whether or not the graph is bipartite. This can be checked in polynomial time. You simply start with one vertex, give it color 1 and all adjacent vertices color 2. Then all adjacent vertices of color 2 have to have color 1, ...
- Vertex Coloring is in $\mathcal{NPC}$.
- All triangle-free planar graphs can be 3-colored. You can get this coloring in linear time (source).
Algorithms
I think learning from errors is important. This is the reason why I share the following algorithm that do not work.
First WRONG try: Fix adjacent vertices
[caption id="attachment_69891" align="aligncenter" width="512"]
A vertex coloring algorithm that does not work[/caption]
The time complexity of this algorithm is in \(\mathcal{O}(|V|^2)\). This should make you suspicious, as Vertex Coloring is in \(\mathcal{NPC}\). So if it was correct, it would solve the P vs. NP problem which is worth a million dollars.
But an example why it doesn't work is better. Just try it for the following graph:
[caption id="attachment_69921" align="aligncenter" width="512"]
Example that does not work with the provided algorithm[/caption]
Second WRONG try: Fix current vertex
[caption id="attachment_69971" align="aligncenter" width="512"]
Another vertex coloring algorithm[/caption]
This algorithm gives a valid coloring, but the coloring is not minimal.
Example:
When you apply the algorithm the the graph below, you will get a coloring with four colors. But obviously, it is possible to color it with three colors.
[caption id="attachment_69951" align="aligncenter" width="512"]
Graph that can be vertex-colored with 3 colors[/caption]
Brute force
It's always a good idea to think about brute force algorithms. On the one hand, they are simple. So you can intuitively understand why they are correct and see their time / space complexity. On the other hand, you can use them for sanity checks of better algorithms for small problem instances.
Here is a brute force algorithm for the vertex coloring problem
[caption id="attachment_70001" align="aligncenter" width="512"]
Brute force a minimal vertex coloring[/caption]
You need \(\sum_{i=2}^n i^n\) steps at maximum. Wow. This is MUCH. Even when you only want to check if \(i\) colors are enough, you need \(i^n\).
You could use the second algorithm to get a better upper bound and try the next smaller ones. As soon as you don't get valid colorings, you know that the number of colors you've used in the last valid coloring was the minimum number.
Zero-knowledge protocol
Vertex coloring is relevant for so called "zero-knowledge protocols". This is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any additional information apart from the fact that the statement is indeed true.
A zero-knowledge proof must satisfy three properties:
- Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
- Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
- Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some ''simulator'' that, given only the statement to be proven (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier.
Source: Wikipedia
Another great example is the following:
Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green. Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls. By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than $\frac{1}{2}$. If you and your friend repeat this "proof" $t$ times (for large $t$), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most $2^{-t}$. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.
Source: mathoverflow.net
Lets make this more concrete. Say you want to authenticate somebody. This person is identified as the "only" person who knows a three-coloring of a big graph. This makes him/her special. If you simply asked him "what's the three coloring for your graph?" he would no longer be the only person who knows the three coloring.
So you want to get sure that he knows a three coloring without getting it.