Our applications consist of three case studies centered around some of the most fundamental problems considered in [1]}, feedback vertex sets and hitting sets. For the first case study, we considered the Feedback Vertex Set problem: given a graph \(G\)  and an integer \(k\) , does \(G\)  have a feedback vertex set of size at most \(k\) ?
For this problem, we re-analyze the running time of the algorithm from [2]}. In [2]}, [4]}, the algorithm was analyzed using Measure and Conquer: using a measure that is upper bounded by \(\alpha n\)  and aiming for a running time of \(2^{\alpha n} n^{O(1)}\)  the analysis of the branching cases led to constraints lower bounding the measure and the objective was to minimize \(\alpha \)  subject to these constraints. In our new analysis, we add an additive term \(w_k\cdot k\)  to the measure and adapt the constraints accordingly. If all constraints are satisfied, we obtain a running time of \(2^{\alpha n+w_k k} n^{O(1)}\) . Our framework naturally leads us to minimize \(2^\alpha -2^{-w_k}\) . This approach leads to a \(O(1.5422^n \cdot 1.2041^k)\)  time algorithm, which, combined with our framework gives a deterministic \(O(1.7117^n)\)  time algorithm for Feedback Vertex Set. This improves on previous results giving \(O(1.8899^n)\)  [5]}, \(O(1.7548^n)\)  [2]}, \(O(1.7356^n)\)  [7]}, \(O(1.7347^n)\)  [8]}, and \(O(1.7216^n)\)  [1]} time algorithms for the problem. We note that adapting the analysis of other existing exact and parameterized algorithms did not give faster running times. Also, if we allow randomization, the \(O(1.6667^n)\)  time algorithm by [1]} (which can also be achieved using our framework) remains fastest.
