191014K02 | Day 5 Tutorial

191014K02: Day 5 Tutorial

Back to the Course Page

Problems

1. 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].$$

2. 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:

   1. Show that starting at position $d+3$ the probability of reaching $0$ is $\leqslant q_d/8$.

   2. Show that $\forall k$, $\exists c$ such that $\forall d$¹, after $cd$ steps, the probability of being at position $\leqslant d+3$ is $\leqslant q_d/8$.

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

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

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

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

Footnotes

1. ($d$ sufficiently large as function of $k$)