PROBLEM LINKS
DIFFICULTY
CHALLENGE
EXPLANATION
Basically, the problem is asking you to come up with a proper coloring of a graph using the fewest number of colors possible. The only other trick is that you are guaranteed the graph can be colored with 3 colors. The existence of a polynomial-time algorithm that is
guaranteed to three color such graphs would still imply P = NP. Oddly enough, the existence of a polynomial time algorithm that is guaranteed to color a 3 colorable graph using only 4 colors would also imply P = NP as well [1].
A heuristic many people employ when coloring graphs is to color the nodes greedily (i.e. use the first available color when considering a
node) in decreasing order of degree. The idea is that high-degree nodes are ``harder’’ to color if we color many other nodes before them, so we should color them first. In the case of 3 colorable graphs, another very interesting heuristic can be exploited. For a node v, let N(v) denote the graph consisting of only nodes that are adjacent to v plus all of the edges between these nodes. Then for any node v in a three colorable graph, N(v) is bipartite. The nice thing about bipartite graphs is that we can properly color them with 2 colors in linear time. So, a stronger heuristic would be to pick a high degree node v, color ALL neighbors of v using only two colors (you have to be careful that the colors used are not already used on neighbors of nodes in N(v)), and then color v with one additional new color.
For worst-case approximation guarantees, there is the following algorithm. Phase 1: while there is a node v with at least sqrt(n) uncolored neighbors in N(v), color the remaining nodes in N(v) with 2 new colors and color v with yet another color. Phase 2: now all nodes v have no more than sqrt(n) uncolored neighbors. Greedily color them with the heuristic mentioned at the start of the previous paragraph. Some thought reveals that this heuristic uses only O(sqrt n) colors so it is at least asymptotically better than the trivial algorithm that assigns a unique color to each node. There are obvious practical improvements to this heuristic, but it’s a neat starting idea. This seems like a weak bound, but the best known is not much better. In polynomial time, the best known algorithm only guarantees that at most O(n^0.2072) colors are used when coloring a 3 colorable graph [2]. A more in-depth (but quite technical) survey of the theoretical results concerning coloring 3 colorable graphs can be found in [3].
[1] V. Guruswami and S. Khanna. On the hardness of 4-coloring a 3-colorable graph. In IEEE Conference on Computational Complexity, pages 188–197, 2000.
[2] E. Chlamtac. Approximation algorithms using hierarchies of semidefinite programming relaxations. In FOCS ’07: Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 691–701,Washington, DC, USA, 2007. IEEE Computer Society.
[3] http://www.cs.cmu.edu/~anupamg/adv-approx/lecture15.pdf 30
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.