随机算法 (Fall 2011)/Graph Coloring

From TCS Wiki
Revision as of 13:42, 10 August 2011 by imported>WikiSysop (Created page with '=Graph Colorings= A '''proper coloring''' of a graph <math>G(V,E)</math> is a mapping <math>f:V\rightarrow[q]</math> for some integer <math>q</math>, satisfying that <math>f(u)\n…')
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to navigation Jump to search

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
Start with a proper coloring of [math]\displaystyle{ G(V,E) }[/math]. At each step:
  1. Pick a vertex [math]\displaystyle{ v\in V }[/math] and a color [math]\displaystyle{ c\in[q] }[/math] uniformly at random.
  2. 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 the above Markov chain.

  1. Aperiodic.
  2. The transition matrix is symmetric.
  3. Irreducible if [math]\displaystyle{ q\ge \Delta+2 }[/math].

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

Conjecture
  1. The simple Markov chain defined above has mixing time [math]\displaystyle{ O(n\ln n) }[/math] whenever [math]\displaystyle{ q\ge\Delta+2 }[/math].
  2. 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]

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