随机算法 \ 高级算法 (Fall 2016)/Problem Set 1

Problem 1

For any [math]\displaystyle{ \alpha\ge 1 }[/math], a cut [math]\displaystyle{ C }[/math] in an undirected (multi)graph [math]\displaystyle{ G(V,E) }[/math]is called an [math]\displaystyle{ \alpha }[/math]-min-cut if [math]\displaystyle{ |C|\le\alpha|C^*| }[/math] where [math]\displaystyle{ C^* }[/math] is a min-cut in [math]\displaystyle{ G }[/math].

1. Give a lower bound to the probability that Karger's Random Contraction algorithm returns an [math]\displaystyle{ \alpha }[/math]-min-cut in a graph [math]\displaystyle{ G(V,E) }[/math] of [math]\displaystyle{ n }[/math] vertices.
2. Use the above bound to estimate the number of distinct [math]\displaystyle{ \alpha }[/math]-min cuts in [math]\displaystyle{ G }[/math].

Problem 2

Let [math]\displaystyle{ G(V,E) }[/math] be an undirected graph with positive edge weights [math]\displaystyle{ w:E\to\mathbb{Z}^+ }[/math]. Given a partition of [math]\displaystyle{ V }[/math] into [math]\displaystyle{ k }[/math] disjoint subsets [math]\displaystyle{ S_1,S_2,\ldots,S_k }[/math], we define

[math]\displaystyle{ w(S_1,S_2,\ldots,S_k)=\sum_{uv\in E\atop \exists i\neq j: u\in S_i,v\in S_j}w(uv) }[/math]

as the cost of the [math]\displaystyle{ k }[/math]-cut [math]\displaystyle{ \{S_1,S_2,\ldots,S_k\} }[/math]. Our goal is to find a [math]\displaystyle{ k }[/math]-cut with maximum cost.

1. Give a greedy algorithm for finding the weighted max [math]\displaystyle{ k }[/math]-cut. Prove that the approximation ratio is [math]\displaystyle{ (1-1/k) }[/math].
2. Consider the following local search algorithm for the weighted max cut (max 2-cut).

start with an arbitrary bipartition of [math]\displaystyle{ V }[/math] into disjoint [math]\displaystyle{ S_0,S_1 }[/math];
while (true) do
   if [math]\displaystyle{ \exists i\in\{0,1\} }[/math] and [math]\displaystyle{ v\in S_i }[/math] such that (______________)
      then [math]\displaystyle{ v }[/math] leaves [math]\displaystyle{ S_i }[/math] and joins [math]\displaystyle{ S_{1-i} }[/math];
      continue;
   end if
   break;
end

Fill in the blank parenthesis. Give an analysis of the running time of the algorithm. And prove that the approximation ratio is 0.5.

Problem 2

A matching of an undirected graph [math]\displaystyle{ G(V,E) }[/math] is a set [math]\displaystyle{ M\subseteq E }[/math] of edges such that [math]\displaystyle{ \forall e_1,e_2\in M, e_1\cap e_2=\emptyset }[/math]. A matching [math]\displaystyle{ M\subseteq E }[/math] is maximal if [math]\displaystyle{ \forall e\in E\setminus M }[/math], [math]\displaystyle{ M\cup\{e\} }[/math] is not a matching. A maximal matching [math]\displaystyle{ M\subseteq E }[/math] is minimum if [math]\displaystyle{ |M| }[/math] is smallest among all maximal matchings in [math]\displaystyle{ G(V,E) }[/math]. A minimum maximal matching must also be a minimum edge dominating set. Finding a minimum maximal matching is NP-hard.