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