随机算法 (Fall 2011)/Graph Coloring
Graph Colorings
A proper coloring of a graph is a mapping for some integer , satisfying that for all .
We consider the problem of sampling a uniformly random proper coloring of a given graph. We will later see that this is useful for counting the number of proper colorings of a given graph, which is a fundamental combinatorial problem, having important applications in statistic physics.
Let's first consider the decision version of the problem. That is, given as input a graph , decide whether there exists a proper -coloring of . Denote by the maximum degree of .
- If , there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
- If , has a proper coloring unless it contains a -clique or it is an odd cycle. (Brooks Theorem)
- If , the problem is NP-hard.
Sampling a random coloring is at least as hard as deciding its existence, so we don't expect to solve the sampling problem when . The decision problem for the case is also nontrivial. Thus people are interested only in the case when .
The following is a natural Markov chain for sampling proper colorings.
Markov Chain for Graph Coloring - Start with a proper coloring of . At each step:
- Pick a vertex and a color uniformly at random.
- Change the color of to if the resulting coloring is proper; do nothing if otherwise.
For a fixed graph , the state space of the above Markov chain is the set of all proper colorings of with colors.
Lemma The followings hold for .
- Aperiodic.
- The transition matrix is symmetric.
- Irreducible if .
The followings are the two most important conjectures regarding the problem.
Conjecture - has mixing time whenever .
- Random sampling of proper graph colorings can be done in polynomial time whenever .
These two conjectures are still open. People approach them by relax the requirement for the number of colors . Intuitively, the larger the is, the more freedom we have, the less dependency are there between non-adjacent vertices.
Coupling:
We couple the two copies of , and , by the following coupling rule:
- At each step, let and choose the same vertex and same color .
Note that by this coupling, it is possible that is recolored to in both chains, in one of the two chains, or in no chain. We may separate these cases by looking at the Hamming distance between two colorings.
Let be the number of vertices whose colors in and disagree. For each step, for any choice of vertex and color , there are three possible cases:
- "Good move" ( decreases by 1): disagree with at , and is not used in the colors of in both and .
- "Bad move" ( increases by 1):
- "Neutral move" ( is unchanged):