# 191014K02 | Day 4 Tutorial

## 191014K02: Day 4 Tutorial

## Problems

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:- u is in
*some*minimum weight set, and - 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. :::

- u is in

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

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.

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.Why did we need to define U to have edges in the k-path algorithm?

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

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