Courses
  • IITGN
  • Online
  • Short Courses
  • Other

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

Made with Quarto and 🩶

 

Content by Neeldhara Misra