随机算法 (Fall 2011)/Randomized Quicksort and 随机算法 (Fall 2011)/Graph Coloring: Difference between pages

From TCS Wiki
(Difference between pages)
Jump to navigation Jump to search
VisualWikitext
No edit summary
 
imported>Etone
 
Line 1: Line 1:
The following is the pseudocode of the famous [http://en.wikipedia.org/wiki/Quicksort Quicksort] algorithm, whose input is a set <math>S</math> of numbers.
=Graph Colorings=
* if <math>|S|>1</math> do:
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)\neq f(v)</math> for all <math>uv\in E</math>.
** pick an element <math>x</math> from  <math>S</math> as the ''pivot'';
** partition <math>S</math> into <math>S_1</math>, <math>\{x\}</math>, and <math>S_2</math>, where all elements in <math>S_1</math> are smaller than <math>x</math> and all elements in <math>S_2</math> are  larger than <math>x</math>;
** recursively sort <math>S_1</math> and <math>S_2</math>;


The time complexity of this sorting algorithm is measured by the '''number of comparisons'''.
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.


For the '''deterministic''' quicksort algorithm, the pivot element is usually the element in a fixed position (e.g. the first one) of the <math>S</math>. This will make the worst-case time complexity <math>\Omega(n^2)</math>, which means there exists a bad case <math>S</math>, sorting which will cost us <math>\Omega(n^2)</math> comparisons, ''every time''!
Let's first consider the decision version of the problem. That is, given as input a graph <math>G(V,E)</math>, decide whether there exists a proper <math>q</math>-coloring of <math>G</math>. Denote by <math>\Delta</math> the maximum degree of <math>G</math>.
* If <math>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>q=\Delta</math>, <math>G</math> has a proper coloring unless it contains a <math>(\Delta+1)</math>-clique or it is an odd cycle. ([http://en.wikipedia.org/wiki/Brooks'_theorem Brooks Theorem])
* If <math>q<\Delta</math>, the problem is NP-hard.


It is just so unfair to have an unbeatable input for this brilliant algorithm. So we tweak the algorithm a little bit:
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>q<\Delta</math>. The decision problem for the case <math>q=\Delta</math> is also nontrivial. Thus people are interested only in the case when <math>q\ge \Delta+1</math>.
== Algorithm: RandQSort ==
* if <math>|S|>1</math> do:
** ''uniformly'' pick a ''random'' element <math>x</math> from  <math>S</math> as the pivot;
** partition <math>S</math> into <math>S_1</math>, <math>\{x\}</math>, and <math>S_2</math>, where all elements in <math>S_1</math> are smaller than <math>x</math> and all elements in <math>S_2</math> are  larger than <math>x</math>;
** recursively sort <math>S_1</math> and <math>S_2</math>;


== Analysis ==
The following is a natural Markov chain for sampling proper colorings.
Our goal is to analyze the expected number of comparisons during an execution of RandQSort with an arbitrary input <math>S</math>. We achieve this by measuring the chance that each pair of elements are compared, and summing all of them up due to [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of Expectation].


Let <math>a_i</math> denote the <math>i</math>th smallest element in <math>S</math>.
{{Theorem|Markov Chain for Graph Coloring <math>\mathcal{M}_c</math>|
Let <math>X_{ij}\in\{0,1\}</math> be the random variable which indicates whether <math>a_i</math> and <math>a_j</math> are compared during the execution of RandQSort. That is:
: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.
# Change the color of <math>v</math> to <math>c</math> if the resulting coloring is proper; do nothing if otherwise.
}}


:<math>
For a fixed graph <math>G(V,E)</math>, the state space of the above Markov chain is the set of all proper colorings of <math>G</math> with <math>q</math> colors.
\begin{align}
X_{ij} &=
\begin{cases}
1 & a_i\mbox{ and }a_j\mbox{ are compared}\\
0 & \mbox{otherwise}
\end{cases}.
\end{align}
</math>


Elements <math>a_i</math> and <math>a_j</math> are compared only if one of them is chosen as pivot. After comparison they are separated (thus are never compared again). So we have the following observation:
{{Theorem|Lemma|
The followings hold for <math>\mathcal{M}_c</math>.
# Aperiodic.
# The transition matrix is symmetric.
# Irreducible if <math>q\ge \Delta+2</math>.
}}


'''Claim 1:  Every pair of <math>a_i</math> and <math>a_j</math> are compared at most once.'''
The followings are the two most important conjectures regarding the problem.
{{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>.
}}


Therefore the sum of <math>X_{ij}</math> for all pair <math>\{i, j\}</math> gives the total number of comparisons. The expected number of comparisons is <math>\mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right]</math>. Due to [http://en.wikipedia.org/wiki/Expected_value#Linearity Linearity of Expectation], <math>\mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right] = \sum_{i=1}^n\sum_{j>i}\mathbf{E}\left[X_{ij}\right]</math>.
These two conjectures are still open. People approach them by relax the requirement for the number of colors <math>q</math>. Intuitively, the larger the <math>q</math> is, the more freedom we have, the less dependency are there between non-adjacent vertices.
Our next step is to analyze <math>\mathbf{E}\left[X_{ij}\right]</math> for each <math>\{i, j\}</math>.


By the definition of expectation and <math>X_{ij}</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>.


:<math>\begin{align}
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.
\mathbf{E}\left[X_{ij}\right]
&= 1\cdot \Pr[a_i\mbox{ and }a_j\mbox{ are compared}] + 0\cdot \Pr[a_i\mbox{ and }a_j\mbox{ are not compared}]\\
&= \Pr[a_i\mbox{ and }a_j\mbox{ are compared}].
\end{align}</math>


We are going to bound this probability.
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>.
'''Claim 2: <math>a_i</math> and <math>a_j</math> are compared if and only if one of them is chosen as pivot when they are still in the same subset.'''
* '''"Bad move"''' (<math>d(X_t,Y_t)</math> increases by 1):
 
* '''"Neutral move"''' (<math>d(X_t,Y_t)</math> is unchanged):
This is easy to verify: just check the algorithm. The next one is a bit complicated.
 
'''Claim 3: If <math>a_i</math> and <math>a_j</math> are still in the same subset then all <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> are in the same subset.'''
 
We can verify this by induction. Initially, <math>S</math> itself has the property described above; and partitioning any <math>S</math> with the property into <math>S_1</math> and <math>S_2</math> will preserve the property for both <math>S_1</math> and <math>S_2</math>. Therefore Claim 3 holds.
 
Combining Claim 2 and 3, we have:
 
'''Claim 4: <math>a_i</math> and <math>a_j</math> are compared only if one of <math>\{a_i, a_j\}</math> is chosen from <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math>.'''
 
And apparently,
 
'''Claim 5: Every one of <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> is chosen equal-probably.'''
 
This is because our RandQSort chooses the pivot ''uniformly at random''.
 
Claim 4 and Claim 5 together imply:
 
:<math>\begin{align}
\Pr[a_i\mbox{ and }a_j\mbox{ are compared}]
&\le \frac{2}{j-i+1}.
\end{align}</math>
 
{|border="1"
|'''Remark:''' Perhaps you feel confused about the above argument. You may ask: "''The algorithm chooses pivots for many times during the execution. Why in the above argument, it looks like the pivot is chosen only once?''" Good question! Let's see what really happens by looking closely.
 
For any pair <math>a_i</math> and <math>a_j</math>, initially <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> are all in the same set <math>S</math> (obviously!). During the execution of the algorithm, the set which containing <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> are shrinking (due to the pivoting), until one of <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> is chosen, and the set is partitioned into different subsets. We ask for the probability that the chosen one is among <math>\{a_i, a_j\}</math>. So we really care about "the last" pivoting before <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> is split.
 
Formally, let <math>Y</math> be the random variable denoting the pivot element. We know that for each <math>a_k\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math>, <math>Y=a_k</math> with the same probability, and <math>Y\not\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math> with an unknown probability (remember that there might be other elements in the same subset with <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math>). The probability we are looking for is actually
<math>\Pr[Y\in \{a_i, a_j\}\mid Y\in\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}]</math>, which is always <math>\frac{2}{j-i+1}</math>, provided that <math>Y</math> is uniform over <math>\{a_i, a_{i+1}, \ldots, a_{j-1}, a_{j}\}</math>.
 
The '''conditional probability''' rules out the ''irrelevant'' events in a probabilistic argument.
|}
 
Summing all up:
 
:<math>\begin{align}
\mathbf{E}\left[\sum_{i=1}^n\sum_{j>i}X_{ij}\right]
&=
\sum_{i=1}^n\sum_{j>i}\mathbf{E}\left[X_{ij}\right]\\
&\le \sum_{i=1}^n\sum_{j>i}\frac{2}{j-i+1}\\
&= \sum_{i=1}^n\sum_{k=2}^{n-i+1}\frac{2}{k} & & (\mbox{Let }k=j-i+1)\\
&\le \sum_{i=1}^n\sum_{k=1}^{n}\frac{2}{k}\\
&= 2n\sum_{k=1}^{n}\frac{1}{k}\\
&= 2n H(n).
\end{align}</math>
 
<math>H(n)</math> is the <math>n</math>th [http://en.wikipedia.org/wiki/Harmonic_number Harmonic number]. It holds that
 
:<math>\begin{align}H(n) = \ln n+O(1)\end{align}</math>.
 
Therefore, for an arbitrary input <math>S</math> of <math>n</math> numbers, the expected number of comparisons taken by RandQSort to sort <math>S</math> is <math>\mathrm{O}(n\log n)</math>.

Latest revision as of 06:48, 11 December 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:
  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 [math]\displaystyle{ \mathcal{M}_c }[/math].

  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. [math]\displaystyle{ \mathcal{M}_c }[/math] 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]

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):
Retrieved from "https://tcs.nju.edu.cn/wiki/index.php?title=随机算法_(Fall_2011)/Randomized_Quicksort&oldid=4704"