, Assume |N (w 2 ) ? V (P )| ? 2. Then Rule 13 or Rule 14 applies. We will show that V (Q) ? S = {w 1 }; then clearly S = S \ {w 1 } is a solution of (G , k ? 1). Build a subgraph R of Q as follows. Start with R = P . For each x ? N (w 2 ) ? V (P ), add a single edge xw 2 to R. Next, for each, Since |N (w 1 ) ? V (P )| ? 3, we see that Q contains cycles and hence |V (Q) ? S| > 0, for otherwise S is not a feedback vertex set. First we consider the case |V (Q) ? S| = 1. Assume |N (w 2 ) ? V (P )| ? 3

}. ?-s-=-{w-1 and . For-otherwise-r-?-s, has 6 vertices and at least 6 edges. This finishes the proof of the |V (Q) ? S| = 1 case. From now on we assume |V (Q) ? S| ? 2. By Lemma 19 we can assume that |V (Q) ? S| = 2

?. S-?-v-(p-), For the remaining rules we will show that G has a feedback vertex S set of size at most k . Consider Rule 14. If |N (w 2 ) ? V (P )| = 0, then by Rule 3, V (P ) ? N (w 1 ) and Rule 7 applies, a contradiction. If |N (w 2 )?V (P )| = 1, then S 1 = (S \V (Q))?{w 1 }?(N (w 2 )?V (P )) is another feedback vertex set of size at most k in G and we can apply Lemma 19. Hence |N (w 2 ) ? V (P )| = 2, particular V (Q) ? S satisfies none of

?. V-(p-), When N (w 2 ) ? V (P ) = {x 2 , v}, then {u, x 1 , x 3 } ? N (w 1 ) ? V (P ) by Rule 3. It follows that there are at most five possible feedback vertex sets of Q ? S, namely {u, x 2 }, {u, x 3 }, {x 1 , x 2 }, {x 1 , x 3 } and {x 1 , v}. In the first, second, third and fourth case w 2 is reachable from v in Q ? S. In the last case w 2 is reachable from u in Q ? S. When N (w 2 ) ? V (P ) = {x 1 , x 3 }, then {u, x 2 , v} ? N (w 1 ) ? V (P ) by Rule 3. It follows that there are at most six possible feedback vertex sets of Q ? S, namely {u, x 2 }, {u, x 3 }, {x 1 , x 2 }, {x 1 , x 3 }, {x 1 , v} and {x 2 , v}. In the first and second case w 2 is reachable from v in Q ? S. In the third and fourth case there is a (u, v)-path. In the fifth and sixth case w 2 is reachable from u in Q ? S. If d = 3, then N (w 2 ) ? V (P ) equals {u, x 3 } or {x 1 , v}. By symmetry assume the former. Then {x 1 , x 2 , v} ? N (w 1 ) ? V (P ) by Rule 3. It follows that there are at most six possible feedback vertex sets of Q ? S, namely {u, The prior two cases are excluded because then Q ? S contains a (u, v)-path, and in the latter two cases w 2 is reachable from u in Q ? S as required, vol.3

, (Q) ? {y 1 , y 2 }, respectively. Note that the equivalence classes of both

F. N. Abu-khzam and M. B. Khuzam, An improved kernel for the undirected planar feedback vertex set problem, Proc. IPEC'12, vol.7535, pp.264-273, 2012.

J. Alber, M. R. Fellows, and R. Niedermeier, Polynomial-time data reduction for dominating set, J. ACM, vol.51, issue.3, pp.363-384, 2004.

H. L. Bodlaender, A cubic kernel for feedback vertex set, Proc. STACS'08, pp.320-331, 2007.

H. L. Bodlaender and E. Penninkx, A linear kernel for planar feedback vertex set, Proc. IWPEC'08, vol.5018, pp.160-171, 2008.

K. Burrage, V. Estivill-castro, M. Fellows, M. Langston, S. Mac et al., The undirected feedback vertex set problem has a poly(k) kernel, Proc. IWPEC'06, pp.192-202, 2006.

J. Chen, H. Fernau, I. A. Kanj, and G. Xia, Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, SIAM J. Comput, vol.37, issue.4, pp.1077-1106, 2007.

H. Dell and D. Van-melkebeek, Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, J. ACM, vol.61, issue.4, p.23, 2014.

P. Festa, P. Pardalos, and M. Resende, Feedback set problems, Encyclopedia of optimization, pp.1005-1016, 2009.

F. V. Fomin, D. Lokshtanov, S. Saurabh, and D. M. Thilikos, Bidimensionality and kernels, SODA, pp.503-510, 2010.

J. Guo and R. Niedermeier, Linear problem kernels for np-hard problems on planar graphs, Automata, Languages and Programming, 34th International Colloquium, vol.4596, pp.375-386, 2007.

R. Karp, Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972.

L. Kowalik, Nonblocker in H-minor free graphs: Kernelization meets discharging, Parameterized and Exact Computation -7th International Symposium, IPEC 2012, Ljubljana, vol.7535, pp.61-72, 2012.

L. Kowalik, M. Pilipczuk, and K. Suchan, Towards optimal kernel for connected vertex cover in planar graphs, Discrete Applied Mathematics, vol.161, issue.7-8, pp.1154-1161, 2013.

W. Luo, J. Wang, Q. Feng, J. Guo, and J. Chen, Improved linear problem kernel for planar connected dominating set, Theor. Comput. Sci, vol.511, pp.2-12, 2013.

A. Silberschatz, P. B. Galvin, and G. Gagne, Operating System Concepts, 2008.

S. Thomassé, A 4k 2 kernel for feedback vertex set, ACM Transactions on Algorithms, vol.6, issue.2, 2010.

J. Wang, Y. Yang, J. Guo, and J. Chen, Planar graph vertex partition for linear problem kernels, J. Comput. Syst. Sci, vol.79, issue.5, pp.609-621, 2013.

M. Xiao, A new linear kernel for undirected planar feedback vertex set: Smaller and simpler, Proc. AAIM, vol.8546, pp.288-298, 2014.