随机算法 (Fall 2011)/Graph Coloring: Difference between revisions
imported>WikiSysop m (Protected "随机算法 (Fall 2011)/Graph Coloring" ([edit=sysop] (indefinite) [move=sysop] (indefinite))) |
imported>WikiSysop No edit summary |
||
Line 13: | Line 13: | ||
The following is a natural Markov chain for sampling proper colorings. | The following is a natural Markov chain for sampling proper colorings. | ||
{{Theorem|Markov Chain for Graph Coloring| | {{Theorem|Markov Chain for Graph Coloring <math>\mathcal{M}_c</math>| | ||
:Start with a proper coloring of <math>G(V,E)</math>. At each step: | :Start with a proper coloring of <math>G(V,E)</math>. At each step: | ||
# Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random. | # Pick a vertex <math>v\in V</math> and a color <math>c\in[q]</math> uniformly at random. | ||
Line 22: | Line 22: | ||
{{Theorem|Lemma| | {{Theorem|Lemma| | ||
The followings hold for | The followings hold for <math>\mathcal{M}_c</math>. | ||
# Aperiodic. | # Aperiodic. | ||
# The transition matrix is symmetric. | # The transition matrix is symmetric. | ||
Line 30: | Line 30: | ||
The followings are the two most important conjectures regarding the problem. | The followings are the two most important conjectures regarding the problem. | ||
{{Theorem|Conjecture| | {{Theorem|Conjecture| | ||
# | #<math>\mathcal{M}_c</math> has mixing time <math>O(n\ln n)</math> whenever <math>q\ge\Delta+2</math>. | ||
# Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>. | # Random sampling of proper graph colorings can be done in polynomial time whenever <math>q\ge\Delta+1</math>. | ||
}} | }} | ||
Line 37: | Line 37: | ||
=Coupling: <math>q\ge 4\Delta+1</math>= | =Coupling: <math>q\ge 4\Delta+1</math>= | ||
We couple the two copies of <math>\mathcal{M}_c</math>, <math>X_t</math> and <math>Y_t</math>, by the following coupling rule: | |||
* At each step, let <math>X_t</math> and <math>Y_t</math> choose the same vertex <math>v</math> and same color <math>c</math>. | |||
Note that by this coupling, it is possible that <math>v</math> is recolored to <math>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>d(X_t,Y_t)</math> be the number of vertices whose colors in <math>X_t</math> and <math>Y_t</math> disagree. For each step, for any choice of vertex <math>v</math> and color <math>c</math>, there are three possible cases: | |||
* '''"Good move"''' (<math>d(X_t,Y_t)</math> decreases by 1): <math>X_t</math> disagree with <math>Y_t</math> at <math>v</math>, and <math>c</math> is not used in the colors of <math>v</math> in both <math>X_t</math> and <math>Y_t</math>. | |||
* '''"Bad move"''' (<math>d(X_t,Y_t)</math> increases by 1): | |||
* '''"Neutral move"''' (<math>d(X_t,Y_t)</math> is unchanged): | |||
=Path Coupling: <math>q\ge 2\Delta+1</math> = | =Path Coupling: <math>q\ge 2\Delta+1</math> = |
Revision as of 06:20, 27 August 2011
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):