191014K02 | Day 4 Tutorial

191014K02: Day 4 Tutorial

Back to the Course Page

Problems

1. The statement of the isolation lemma discussed in class was the following:

   Let $U$ be a universe with $|U|=n$ and let $\cal F$ be a family of sets over $U$. Pick a random weight function $w: U \rightarrow\{1, \cdots ,W\}$. Then:

   $$\operatorname{Pr}[{\color{indianred}\cal F \text{ has a \textbf{unique} min weight set}}] \geqslant 1-\frac{n}{W}$$

   Recall that we called an element $u$ critical if:

   1. $u$ is in some minimum weight set, and
   2. if $w(u)$ is increased by 1 then $u$ is no longer in any minimum weight set.

   Argue that $\cal F$ has a unique set of the minimum weight if and only if there are no critical elements.

   :::{.callout-tip} Foo Bar. :::

Tip

Foo Bar.

2. Design a dynamic programming algorithm for Steiner Tree on graphs of bandwidth $k$ with running time $k^{O(k)} n^{O(1)}$.

3. Demonstrate (via a direct argument) that the greedy algorithm for the maxcut problem discussed in class outputs a cut that cuts at least half the edges in the graph.

4. Recall the greedy algorithm for Set Cover discussed in class. In each round, show that at least one set $S_i \in F$ covers at least 1/OPT fraction of uncovered elements.

5. Why did we need to define $U$ to have edges in the $k$-path algorithm?

6. Design an algorithm for solving the Steiner Tree problem on graphs of bounded FVS.

7. Design an algorithm for the Hamiltonian Path problem on graphs of bounded bandwidth.