# 191014K02 | Day 1 Lecture 1

## 191014K02: Day 2 Tutorial

## Definitions

## Problems

Show that the number of inclusion minimal vertex covers of size at most k is at most 2^k. (Use the algorithm from class.)

Generalize the Vertex Cover algorithm that we saw today to Set Cover in which every element appears in at most d sets.

Feedback Vertex Set as Hitting Set. Why don’t we get a O(\log n) approximation for FVS via the O(\log n) approximation for Set Cover

^{1}?Use Markov inequality to show that: \operatorname{Pr}[{\color{indianred}|S| \leqslant 2 \cdot |\text{OPT}|}] \geqslant \Omega(1 /|\text{OPT}|)

Come up with an algorithm to solve an instance of subgraph isomorphism (G, H) in time 2^{d k} k ! n^{\mathcal{O}(1)} and in time 2^{d k} k^{\mathcal{O}(d \log d)} n^{\mathcal{O}(1)}. Here, |V(G)|=n,|V(H)|=k, and the maximum degree of G is bounded by d.

Generalize the color coding approach for Longest Path to: (a) k-Cycle where H is a cycle on k vertices, (b) Tree Subgraph Isomorphism, where H is restricted to being a tree on k vertices.

Design a randomized algorithm running in time 2^{O\left(\sqrt{k} \log ^2 k\right)}+n^{O(1)} for the problem of finding a feedback arc set of size at most k in a tournament on n vertices.

## Footnotes

Note that Set Cover and Hitting Set are equivalent problems.↩︎