# 191014K02 | Day 5 Tutorial

## 191014K02: Day 5 Tutorial

## Problems

Start the local search algorithm discussed in class and suppose that initially d(\gamma, \beta) \leqslant d. Consider a random walk from d with down-probability 1/k. Show that \forall s \geqslant 0 and j \geqslant 0: \operatorname{Pr}[{\color{indianred}d(\gamma, \beta) \leqslant j \text { in step } s}] \geqslant \operatorname{Pr}\left[P_s \leqslant j\right].

We saw in class that the probability that the walk

*eventually*visits 0 is q_d=\left(\frac{1}{k-1}\right)^d. We want to now show that the probability that this happens in “not too many” i.e, (O(d)) steps, is \geqslant q_d/2. To this end:Show that starting at position d+3 the probability of reaching 0 is \leqslant q_d/8.

Show that \forall k, \exists c such that \forall d

^{1}, after cd steps, the probability of being at position \leqslant d+3 is \leqslant q_d/8.Show that the probability of reaching 0 from d after at least cd steps is at most q_d/2.

Show that the probability of reaching 0 from d after at most cd steps is at least q_d/2.

Show that a tournament has a directed cycle if and only if it has a directed triangle.

Demonstrate a 3-approximation algorithm for the Tournament Feedback Vertex Set problem.

## Footnotes

(d sufficiently large as function of k)↩︎