, 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
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 ,
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 ,
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
An improved kernel for the undirected planar feedback vertex set problem, Proc. IPEC'12, vol.7535, pp.264-273, 2012. ,
Polynomial-time data reduction for dominating set, J. ACM, vol.51, issue.3, pp.363-384, 2004. ,
A cubic kernel for feedback vertex set, Proc. STACS'08, pp.320-331, 2007. ,
A linear kernel for planar feedback vertex set, Proc. IWPEC'08, vol.5018, pp.160-171, 2008. ,
The undirected feedback vertex set problem has a poly(k) kernel, Proc. IWPEC'06, pp.192-202, 2006. ,
Parametric duality and kernelization: Lower bounds and upper bounds on kernel size, SIAM J. Comput, vol.37, issue.4, pp.1077-1106, 2007. ,
Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses, J. ACM, vol.61, issue.4, p.23, 2014. ,
Feedback set problems, Encyclopedia of optimization, pp.1005-1016, 2009. ,
Bidimensionality and kernels, SODA, pp.503-510, 2010. ,
Linear problem kernels for np-hard problems on planar graphs, Automata, Languages and Programming, 34th International Colloquium, vol.4596, pp.375-386, 2007. ,
Reducibility among combinatorial problems, Complexity of Computer Computations, pp.85-103, 1972. ,
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. ,
Towards optimal kernel for connected vertex cover in planar graphs, Discrete Applied Mathematics, vol.161, issue.7-8, pp.1154-1161, 2013. ,
Improved linear problem kernel for planar connected dominating set, Theor. Comput. Sci, vol.511, pp.2-12, 2013. ,
Operating System Concepts, 2008. ,
A 4k 2 kernel for feedback vertex set, ACM Transactions on Algorithms, vol.6, issue.2, 2010. ,
Planar graph vertex partition for linear problem kernels, J. Comput. Syst. Sci, vol.79, issue.5, pp.609-621, 2013. ,
A new linear kernel for undirected planar feedback vertex set: Smaller and simpler, Proc. AAIM, vol.8546, pp.288-298, 2014. ,