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

CS614. Advanced Algorithms. L13 Quiz.

CS614. Advanced Algorithms.

L13 Quiz

Back to the course page

Problem 1. FVS: is this FPT?

Recall the following branching algorithm for Feedback Vertex Set (FVS) discussed in class:

  • Preprocess to eliminate vertices of degree at most two, resulting in an equivlaent multigraph.
  • Preprocess to force vertices with self-loops in the solution and adjust the budget as appropriate.
  • If a pair of vertices have more than two edges between them, delete all but two of these edges.
  • STOP if the graph is a forest or if we are out of budget.
  • Find a shortest cycle and branch on all its vertices.

Since a graph of minimum degree three that is not acyclic always has a cycle of length O(\lg n), this algorithm has a running time of O^\star((\lg n)^k). Argue that this running time in fact shows that FVS is FPT in 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

×