CS614. Advanced Algorithms. L14 Quiz.

CS614. Advanced Algorithms.

L14 Quiz

Back to the course page

Problem 2. High-Degree Branching for FVS

Apply the same preprocessing steps as in the previous problem.

Let $\left(v_1, v_2, \ldots, v_n\right)$ be a descending ordering of $V(G)$ according to vertex degrees, i.e., $d\left(v_1\right) \geq d\left(v_2\right) \geq \ldots \geq d\left(v_n\right)$. Let $V_{3 k}=\left\{v_1, \ldots, v_{3 k}\right\}$.

Recall that the minimum vertex degree of $G$ is at least 3. Show that every feedback vertex set in $G$ of size at most $k$ contains at least one vertex of $V_{3 k}$.