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}.