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)