随机算法 (Fall 2011)/Graph Coloring

Graph Colorings

A proper coloring of a graph [math]\displaystyle{ G(V,E) }[/math] is a mapping [math]\displaystyle{ f:V\rightarrow[q] }[/math] for some integer [math]\displaystyle{ q }[/math], satisfying that [math]\displaystyle{ f(u)\neq f(v) }[/math] for all [math]\displaystyle{ uv\in E }[/math].

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 [math]\displaystyle{ G(V,E) }[/math], decide whether there exists a proper [math]\displaystyle{ q }[/math]-coloring of [math]\displaystyle{ G }[/math]. Denote by [math]\displaystyle{ \Delta }[/math] the maximum degree of [math]\displaystyle{ G }[/math].

• If [math]\displaystyle{ q\ge \Delta+1 }[/math], there always exists a proper coloring. Moreover, the proper coloring can be found by a simple greedy algorithm.
• If [math]\displaystyle{ q=\Delta }[/math], [math]\displaystyle{ G }[/math] has a proper coloring unless it contains a [math]\displaystyle{ (\Delta+1) }[/math]-clique or it is an odd cycle. (Brooks Theorem)
• If [math]\displaystyle{ q\lt \Delta }[/math], 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 [math]\displaystyle{ q\lt \Delta }[/math]. The decision problem for the case [math]\displaystyle{ q=\Delta }[/math] is also nontrivial. Thus people are interested only in the case when [math]\displaystyle{ q\ge \Delta+1 }[/math].

The following is a natural Markov chain for sampling proper colorings.

Markov Chain for Graph Coloring [math]\displaystyle{ \mathcal{M}_c }[/math]

Start with a proper coloring of [math]\displaystyle{ G(V,E) }[/math]. At each step: Pick a vertex [math]\displaystyle{ v\in V }[/math] and a color [math]\displaystyle{ c\in[q] }[/math] uniformly at random. Change the color of [math]\displaystyle{ v }[/math] to [math]\displaystyle{ c }[/math] if the resulting coloring is proper; do nothing if otherwise.

For a fixed graph [math]\displaystyle{ G(V,E) }[/math], the state space of the above Markov chain is the set of all proper colorings of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ q }[/math] colors.

Lemma

The followings hold for [math]\displaystyle{ \mathcal{M}_c }[/math]. Aperiodic. The transition matrix is symmetric. Irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math].

The followings are the two most important conjectures regarding the problem.

Conjecture

[math]\displaystyle{ \mathcal{M}_c }[/math] has mixing time [math]\displaystyle{ O(n\ln n) }[/math] whenever [math]\displaystyle{ q\ge\Delta+2 }[/math]. Random sampling of proper graph colorings can be done in polynomial time whenever [math]\displaystyle{ q\ge\Delta+1 }[/math].

These two conjectures are still open. People approach them by relax the requirement for the number of colors [math]\displaystyle{ q }[/math]. Intuitively, the larger the [math]\displaystyle{ q }[/math] is, the more freedom we have, the less dependency are there between non-adjacent vertices.

Coupling: [math]\displaystyle{ q\ge 4\Delta+1 }[/math]

We couple the two copies of [math]\displaystyle{ \mathcal{M}_c }[/math], [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math], by the following coupling rule:

• At each step, let [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math] choose the same vertex [math]\displaystyle{ v }[/math] and same color [math]\displaystyle{ c }[/math].

Note that by this coupling, it is possible that [math]\displaystyle{ v }[/math] is recolored to [math]\displaystyle{ c }[/math] 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 [math]\displaystyle{ d(X_t,Y_t) }[/math] be the number of vertices whose colors in [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math] disagree. For each step, for any choice of vertex [math]\displaystyle{ v }[/math] and color [math]\displaystyle{ c }[/math], there are three possible cases:

• "Good move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] decreases by 1): [math]\displaystyle{ X_t }[/math] disagree with [math]\displaystyle{ Y_t }[/math] at [math]\displaystyle{ v }[/math], and [math]\displaystyle{ c }[/math] is not used in the colors of [math]\displaystyle{ v }[/math] in both [math]\displaystyle{ X_t }[/math] and [math]\displaystyle{ Y_t }[/math].
• "Bad move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] increases by 1):
• "Neutral move" ([math]\displaystyle{ d(X_t,Y_t) }[/math] is unchanged):