On this page

FVS Iterative Compression

In Feedback Vertex Set, we ask whether deleting at most $$k$$ vertices makes the graph acyclic. These questions focus on iterative compression and the disjoint forest subproblem, especially the degree-two reduction rule.

FVS Iterative Compression Example

Part A

How many times will the degree two rule be invoked, resulting in the removal of a vertex from the graph without including it in the solution?

Part B

How many times will the degree two rule be invoked, resulting in the inclusion of the vertex involved in the solution?

Part C

Assuming we process lower-indexed leaves first, which vertex is included in the final solution output by the algorithm?

Part D

Does the algorithm encounter any branching in its run on this instance?