Neeldhara
  • About
  • Research
    • Overview
    • People
    • Publications
    • Surveys
  • Teaching
    • Courses
    • Materials
  • Lists
    • Puzzles
    • Bookmarks
  • Exposition
    • Talks
    • Videos
  • Events
  • Blog

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


© 2022 • Neeldhara Misra • Credits •

 

Corrections? Please leave a comment here or a PR in this repository, thanks!

I’d rather be a failure at something I love than a success at something I hate.

George Burns

You live and you learn — at any rate, you live.

Douglas Adams

A problem worthy of attack proves its worth by fighting back.

Paul Erdos

×