An Overview of Techniques for Designing Parameterized Algorithms <s> Example: k-feedback vertex set <s> We consider a binary integer programming formulation (VP) for the weighted vertex packing problem in a simple graph. A sufficient “local” optimality condition for (VP) is given and this result is used to derive relations between (VP) and the linear program (VLP) obtained by deleting the integrality restrictions in (VP). Our most striking result is that those variables which assume binary values in an optimum (VLP) solution retain the same values in an optimum (VP) solution. This result is of interest because variables are (0, 1/2, 1). valued in basic feasible solutions to (VLP) and (VLP) can be solved by a “good” algorithm. This relationship and other optimality conditions are incorporated into an implicit enumeration algorithm for solving (VP). Some computational experience is reported. <s> BIB001 </s> An Overview of Techniques for Designing Parameterized Algorithms <s> Example: k-feedback vertex set <s> We present an O(mn) algorithm to determine whether a graph G with m edges and n vertices has an odd cycle transversal of order at most k, for any fixed k. We also obtain an algorithm that determines, in the same time, whether a graph has a half integral packing of odd cycles of weight k. <s> BIB002
We will give an algorithm for the problem k-feedback vertex set using the technique described in the previous section. Feedback vertex set (is there a k-set S such that G[V 2 S] is acyclic?) is a monotone problem as adding new vertices will never help to cover existing cycles. Consider the 'Feedback Vertex Set Algorithm' in Fig. 12. OBSERVATION 7. Algorithm 'FVS' is correct, and solves k-feedback vertex set in FPT time. Proof. We will first prove that the algorithm does not incorrectly decide the answer before running the treewidth subroutine. If the algorithm answers 'Yes' because jV (G)j k, it is correct as we can select V as our feedback vertex set. If the algorithm answers 'No' because (G 2 v, k) is a 'No'-instance, it is correct as k-feedback vertex set is a monotone problem. We assume the treewidth subroutine is correct so it remains to show that the algorithm computes a tree decomposition of the graph with bounded treewidth. The algorithm computes the graph T ¼ G 2 (S < v) which is a forest, and it is easy to construct a tree decomposition of width one from this forest, having one bag for each edge. The algorithm then adds S < v to each bag to obtain a correct tree decomposition of width k þ 2. It follows from results in  that k-feedback vertex set is solvable in FPT time if the treewidth is the parameter. This gives the desired result. A Two other papers that use this type of induction are  BIB002 . In BIB002 , Reed et al. managed to show that the problem k-odd cycle cover (is there a k-set S such that G[V 2 S] is bipartite?) is in If we have such a certificate S, we can conclude that S < fvg is a solution of size at most k þ 1 for G. The authors then show, by a fairly complicated argument which we will not explain here, that given a solution of size at most k þ 1 it is possible to determine in FPT time whether or not there exists a solution of size k. A very similar use of induction is seen in  where Dehne et al. give a 2k kernel for k-vertex cover without using the complicated Nemhauser-Trotter results BIB001 . By induction assume we can determine if (G 2 v) has a k-vertex cover, if no such cover exists we cannot find one for G either. On the other hand if (G 2 v) has a k-vertex cover S then S < fvg is a k þ 1-vertex cover for G and by implication has a n 2 (k þ 1)-independent set. As long as jV(G)j . 2k þ 2 we know by Lemma 1 that G has a crown decomposition, which in turn leads to a reduction in G as seen in Lemma 2. This reduction continues until the graph has size at most 2k þ 2, at which point we can test for k-vertex cover using a brute force algorithm.