Pierre Renaud
email: renaud@ifma.fr

Nicolas Andreff
email: andreff@ifma.fr

Frédéric Marquet
email: marquet@lirmm.fr

Philippe Martinet
email: martinet@lasmea.univ-bpclermont.fr

Vision-based kinematic calibration of a H4 parallel mechanism

In this article, we present the kinematic calibration of a H4 parallel robot using a vision-based measuring device. Calibration is performed according to the inverse kinematic model method, using first the design model then a model developed for calibration purpose. With a precision of the order of magnitude of 0.2mm and 0.03 • , our vision system allowed us to obtain a final positioning accuracy of the end-effector lower than 0.5mm. Conclusions are given on the use of a vision-based measuring device for the calibration of this class of mechanisms.

I. INTRODUCTION

Compared to serial mechanisms, parallel structures may exhibit a much better repeatability [START_REF] Merlet | Les Robots Parallèles[END_REF], but their large number of links and passive joints often limits their performance in terms of accuracy [START_REF] Wang | On the accuracy of a Stewart platform -Part I : The effect of manufacturing tolerances[END_REF]. A kinematic calibration is thus needed. The algorithms proposed to conduct calibration for parallel structures can be classified in three classes: methods based on the direct use of a kinematic model, on the use of kinematic constraints on mechanism parts, and methods relying on the use of redundant proprioceptive sensors. The use of additional proprioceptive sensors on the passive joints of the mechanism enables one to have a unique solution to the direct kinematic model [START_REF] Tancredi | Forward kinematics of a parallel manipulator with additional rotary sensors measuring the position of platform joints[END_REF], and to perform the kinematic calibration [START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF][START_REF] Zhuang | Self-calibration of parallel mechanisms with a case study on Stewart platforms[END_REF][START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF], or to improve their accuracy [START_REF] Marquet | Enhancing parallel robots accuracy with redundant sensors[END_REF]. Practically speaking, the mechanism design has to take into account the use of such extra sensors. Nevertheless, not all kinds of mechanisms can be equipped with additional sensors. Methods based on kinematic constraints of the endeffector [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF] or the legs [START_REF] Geng | An effective kinematics calibration method for Stewart platform[END_REF][START_REF] Zhuang | Method for kinematic calibration of Stewart platforms[END_REF][START_REF] Khalil | Self calibration of Stewart-Gough parallel robots without extra sensors[END_REF][START_REF] Daney | Self calibration of Gough platform using leg mobility constraints[END_REF] solve this problem. However, the former methods are not numerically efficient [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF], and kinematic constraints of the legs of the mechanism in position or orientation seem difficult to achieve in practice on large structures. The forward kinematic model of parallel structures can rarely be expressed analytically [START_REF] Merlet | Les Robots Parallèles[END_REF]. The use of this model to achieve kinematic calibration may consequently lead to numerical instability [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF]. On the other hand, the inverse kinematic model can usually easily be derived. Calibration can then be performed by comparing the measured joint variables and their corresponding values estimated from the measured end-effector pose and the inverse kinematic model. Each leg can furthermore be calibrated independently [START_REF] Zhuang | Calibration of Stewart platforms and other parallel manipulators by minimizing inverse kinematic residuals[END_REF]. Up to now, the inverse kinematic model method seems the most efficient method [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF]. Its main limitation is the need for accurate measurement of the full end-effector pose (i.e. both its position and its orientation). Among the proposed measuring devices [START_REF] Curtino | Threedimensional metrology frame for precision applications[END_REF][START_REF] Vincze | A laser tracking system to measure position and orientation of robot end-effectors under motion[END_REF][START_REF] Masory | Measurement of pose repeatability of Stewart platform[END_REF][START_REF] Schmitz | A new sensor for the micrometre-level measurement of three-dimensional, dynamic contours[END_REF], only a few have been used to conduct kinematic identification of a parallel structure [START_REF] Zhuang | Calibration of Stewart platforms and other parallel manipulators by minimizing inverse kinematic residuals[END_REF][START_REF] Geng | A "3-2-1" kinematic configuration of a Stewart platform and its application to six degrees of freedom pose measurements[END_REF][START_REF] Fried | A 3-d sensor for parallel robot calibration. a parameter perturbation analysis[END_REF][START_REF] Vischer | Kinematic calibration of the parallel delta robot[END_REF]. Indeed, the systems are either very expensive, tedious to use or with low working volume. On the opposite, a visionbased measuring system enables one to perform the pose measurement accurately [START_REF] Renaud | Experimental evaluation of a vision-based measuring device for parallel machine-tool calibration[END_REF], is low-cost and easy to use. Using this device and the inverse kinematic method may therefore be an efficient way to conduct kinematic calibration.

In this article, we present the kinematic calibration of a H4 robot [START_REF] Pierrot | H4 parallel robot : Modeling, design and preliminary experiments[END_REF] using a vision-based measuring device. In the first part, two different kinematic models are detailed. The first one (Model 12) corresponds to the initial design of the mechanism, and the second one (Model 31) is developed for calibration purpose. The use of a visionbased measuring system for kinematic calibration is then analyzed. The identifiability conditions bound to the use of such an exteroceptive sensor are underlined. Experimental results on a H4 prototype are then presented with validation experiments, showing a final positioning accuracy of the end-effector of less than 0.5mm. The calibration gain induced by the use of the calibration model is discussed. Finally conclusions are given on the use of a vision-based measuring device for the calibration of this class of mechanisms.

II. KINEMATIC MODELLING

A. H4 Description

The H4 mechanism (Fig. 1) is a parallel mechanism composed of four chains, actuated by four angular motors located between the base and the arms. The forearms linking the arms and the nacelle are composed of two rods. The end-effector has four degrees of freedom (three translations and one rotation) if the closed loops constituted by these four pairs of rods correspond to spatial parallelograms [START_REF] Pierrot | H4 parallel robot : Modeling, design and preliminary experiments[END_REF]. The end-effector is linked to the nacelle with a mechanical amplification system to achieve a higher rotation capability.

B. Model 12

Hypotheses. In the following, the end-effector will be assumed to have only four degrees of freedom. The hypothesis validity will be discussed in paragraph IV. Each forearm parallelogram is assumed perfect and is thus equivalent to a link ensuring a circular translation of the nacelle with respect to the arm. In this part, we assume furthermore that the rotary joint centers P i , i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF] between the base and the arms are located in the same plane, at equal distance R from the corresponding joint centers A i on the nacelle when this latter is considered to be in the base plane (Fig. 2). The four arms are supposed to be of equal length L, and the forearms of length l. Considering the nacelle dimensions h and d (Fig. 3), the mechanism geometry is therefore defined by nine parameters : R, l, L, h, d, α i with i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF]. With such a model, parameter d has however no influence on the kinematics [START_REF] Pierrot | H4 parallel robot : Modeling, design and preliminary experiments[END_REF]. Taking into account the joint offsets q i0 , i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF], twelve parameters finally define the mechanism kinematics.

Inverse Kinematic

Model. An implicit model can be readily written between end-effector pose (X, Y, Z, θ) (Fig. 3) and joint variables by expressing the i-th forearm length, i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF] as a function of the parameters [START_REF] Pierrot | H4 parallel robot : Modeling, design and preliminary experiments[END_REF]: The inverse kinematic model can then be derived from this implicit model [START_REF] Pierrot | H4 parallel robot : Modeling, design and preliminary experiments[END_REF]:

L 2 -l 2 - --→ P i A i 2 = -2 ---→ PiAi x .l.cos(αi).cos(qi) + ---→ PiAi y .l.sin(αi).cos(qi) - ---→ PiAi z .l.sin(qi) (1)
¡ ¢ ¡¢ £ ¤ ¥ ¡¥ ¦ ¡¦ § © α4 α1 P3 P4 A4 A1 F orearm R α2 A3 α3 P1 A2 h -→ yB -→ xB O P2 M otor d
q i = 2.Atan N + i √ N 2 +M 2 -G 2 G+M , i ∈ [1, 4] (2)
with

G = L 2 -l 2 - --→ P i A i 2 , N = 2.l. --→ P i A iz M = -2.l.( --→ P i A ix .cos(α i ) + --→ P i A iy .sin(α i )
) and i = ±1 depending on the assembly Calibration method. To identify the parameter vector ξ, an error function is minimized, which compares the estimated joint variables and the measured ones q for N different end-effector poses (X j , Y j , Z j , θ j ):

min ξ N j=1 4 i=1 q i (ξ, X j , Y j , Z j , θ j ) -qij 2 (3)

C. Model 31

Hypotheses. The former geometry corresponds to the mechanism design. Due to the manufacturing tolerances, assembly errors, the previous assumptions about the geometry may be questionable. In this part, the mechanism is still considered as a four degrees of freedom mechanism and the nacelle is assumed to be planar with dimensions h et d. On the other hand, no assumption is now made about the position and orientation of the revolute joints Rotary joint positions ψ i , β i , i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF] Rotary joint orientations q i0 , i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF] Joint offsets l i , L i , i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF] Arm and forearm lengths h, d Nacelle dimensions 3 3 3 3 4 4 5 5 5 5 6 6 7 7 8 8 between the base and the arms, nor on the arm and forearm lengths.

9 9 @ @ A A A A A A B B B B B B C C D D E E E E E E F F F F F F ψ 3 θ3 -→ x B P1 -→ zB P2 -→ zB x4 y4 P4 - → z3 P3 -→ yB -→ xB
The base frame is attached to the first joint center P 1 (Fig. 4), its axis -→ z B parallel to the end-effector rotation axis, and orientation defined by the "H-configuration" of the nacelle. The position of the joint centers P i is defined relatively to the corresponding joint centers on the nacelle in a similar way to the Model 12. The joint axis -→ z i are defined by Euler angles ψ i and β i . Thirty-one parameters are then necessary to define its geometry (Table 1).

Implicit model. The implicit model can be obtained as in II.B. for each kinematic chain i ∈ [START_REF] Merlet | Les Robots Parallèles[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF]:

L i - → V i + -→ W i 2 = l i 2 (4)
with

- → V i = sin(qi +qi 0 )cos(βi)sin(ψi)-cos(qi+qi 0 )cos(ψi) -sin(qi +qi 0 )cos(βi)cos(ψi)-cos(qi+qi 0 )sin(ψi) -sin(qi +qi 0 )sin(βi) -→ W i = X-xi+(1+ 1i-2i cos(θ))h Y -yi+d-2i hsin(θ) Z-zi
and 1i = ±1, 2i = ±1 depending on the assembly. The inverse kinematic model consists in expressing q i as a function of (X, Y, Z, θ), which seems not possible analytically.

Calibration method. The parameter vector ξ is obtained from the implicit model by solving:

min ξ N j=1 4 i=1 l i -L i - → V i j + -→ W ij 2 (5)

III. FROM VISION TO CALIBRATION

In this part, we consider how to use vision to perform the kinematic calibration of the H4 mechanism.

A. Vision-based measurement characteristics

The vision-based measuring system is composed of a camera, fixed onto the base, and a calibration board fixed onto the end-effector (Fig. 1). The system is calibrated at the beginning of the experiment by acquiring a sequence of about 8 images, using a software developed at LASMEA [START_REF] Lavest | Do we really need an accurate calibration pattern to achieve a reliable camera calibration[END_REF]. After calibration, the pose C T cb of the calibration board with respect to the camera can be computed for each image [START_REF] Dhome | Determination of the attitude of 3-D objects from a single perpsective view[END_REF]. Furthermore, the measuring system is easy to use, and the experimental procedure for the kinematic calibration is fast. The full-pose measurement enables one to perform calibration by the inverse kinematic model method. In this model, the end-effector pose B T ee is defined by its position and orientation with respect to the base frame, and related to the pose measurement by the relation:

B T ee = B T C C T cb cb T ee (6)
Two transformations have therefore to be identified simultaneously with the kinematic parameters: B T C between the camera and base frames, and cb T ee between the calibration board and the end-effector.

B. Prior Kinematic Analysis

Information about the kinematics of the system can be obtained before conducting the identification process. Indeed, the H4 robot has a constant rotation axis, perpendicular to the nacelle, provided that the assumption concerning the forearm parallelograms is valid. Consequently, the calibration board also rotates around this constant axis. The latter can hence be immediately estimated in the camera frame since the rotation matrix between the calibration board and the camera C R cb can be computed for each end-effector pose. Furthermore, as the rotation axis corresponds to the vector -→ z b , this vector can be identified in the camera frame R C . This enables us to reduce the number of kinematic parameters identified simultaneously.

C. Identifiability

Model 12. Identifying C T B and cb T ee is equivalent to base-world and tool-hand calibration problems. Since the calibration board movement is limited to one rotation w.r.t the camera, the transformation cb T ee cannot be completely identified [START_REF] Tsai | A new technique for fully autonomous and efficient 3D robotics hand/eye calibration[END_REF][START_REF] Andreff | Robot hand-eye calibration using structure-from-motion[END_REF]. Moreover, in our context, due to visibility condition of the calibration board, the camera and calibration board are approximately aligned with the mechanism rotation axis (Fig. 1). Then expanding [START_REF] Daney | Etalonnage géométrique des robots parallèles[END_REF] shows that z cb,ee and z B,C (the translation components along z of the transformations cb T ee and C T B ) can be identified only by their sum. Finally, as the angles defining parallelism between the end-effector and the calibration board have only a second-order influence, their identification seems also tedious. Hence the a priori value of these parameters will then be used. These remarks have been confirmed by the numerical estimation of the Jacobian matrix.

Model 31. This model is also invariant with respect to a simultaneous rotation of the location of the joints between the base and the legs, the camera frame and the calibration board frame around the axis -→ z B . Therefore, one parameter between the two corresponding angles of the transformations B T C and cb T ee has here again to be fixed to its a priori value. In the same way, the nacelle dimension d and the translation component y B,C of the transformation B T C are only identifiable by their sum. The a priori value of the parameter d is then used.

The identification by the inverse kinematic model method is therefore submitted to two identifiability problems: The first one is the number of degrees of freedom of the mechanism, that prevents from achieving the complete calibration of the transformations related to the measuring device. The second one comes from the number of degrees of freedom introduced in the joint location parameterization for the Model 31. We can also remark that the identification of the transformations related to the measuring device imply a global identification of the mechanism, and not the independent identification of each kinematic chain.

IV. EXPERIMENTATION

A. Set-up

The camera sensor has a resolution of 1024×768 pixels, 8bit encoded, with a 3.8 mm lens. Images are stored on a PC via an IEEE1394 bus. For each position, 10 images are stored and their average value is considered for the pose evaluation, in order to reduce high frequency noise. The pose can be measured with accuracy in the order of respectively 0.2 mm and 0.03 • for each translation and rotation component. Eighty-one poses are used, equally distributed in a 200 × 200 × 150 mm 3 volume, with three different orientations (θ = -20 • , 0 • , 20 • ). Out of them, seventy-one poses are randomly chosen for the calibration, the other ten are used to perform a validation test.

B. Kinematic Analysis

The variation of the rotation axis in the camera frame is quantified by the variation of the angle between the axis q 02 q 03 q 04 a priori 0 0 0 0 Identified -0.0662 -0.0080 -0.0476 -0.0561 and its mean direction. The estimated standard deviation is equal to 0.12 • . The amplitude of the axis direction variation confirms that the mechanism can be safely considered as having four degrees of freedom.

C. Identification

Model 12. The computation of the estimated parameters is achieved using the inverse kinematic model method, with non-linear optimization. The Levenberg-Marquardt algorithm is used, and columns of the identification Jacobian matrix are scaled with extremal scaling value [START_REF] Schroer | Robot Calibration, chapter Theory of kinematic modelling and numerical procedures for robot calibration[END_REF] to avoid biased estimation. The identified parameters related to the mechanism are listed in Table 2, and compared to their a priori values.

It is noticeable that using the a priori parameters, rather than the optimally estimated ones, yields an average positioning error of the nacelle of 26mm and 0.022rad.

Model 31. The angle around -→ z B between the nacelle and the calibration board identified with the Model 12 is used to achieve the kinematic calibration with the second model. The a priori value of d is employed.

D. Validation

Joint residuals. For Model 12, a first validation consists in estimating with the identified inverse kinematic model the joint variables from the ten pose measurements that were not used for calibration, and compare these values to the recorded joint variables. The mean and root mean square errors of the four joints are indicated in Table 3, showing an accuracy increase from some 0.1rad before calibration to some 10 -4 rad afterwards. For Model 31, the validation is achieved by computing the errors committed in the joint variables estimation, to enable comparison with Model 12. The errors are of the same order.

Straightness evaluation. To confirm these results independently from the measuring device, an experiment is Model 12 4.9 E-4 5.8 E-4 Calib. model 5.9 E-4 1.1 E-3 conducted where the end-effector is manually constrained to follow a line materialized by a ruler (Fig. 5). The corresponding joint variables are stored. From these joint variables values, poses are computed by means of a numerical forward kinematic model. The physical set-up implies that these poses should lie on a straight line. Hence, the straightness of the line is computed for the two kinematic parameter sets (a priori and identified) as the root mean square of the distance between the different positions and the line estimated by a least squares criterion. The experiment is conducted with two different orientations of the rule. The results are presented in Table 4. For Model 12, the straightness improvement is equal to 63% and 75% , which confirms the first validation. For Model 31, the improvement is actually lower, with a relative gain around 50% for the two experiments. The low decrease of straightness improvement can be due to several factors. The first one is the diminution of the ratio between the pose number and the kinematic parameter number, even if this ratio remains acceptable (36 parameters and 284 equations). The second factor is the identifiability problem bound to the use of an exteroceptive measuring device. Eventually the hypothesis concerning the spatial parallelograms may be questionable, and a kinematic model taking into account the geometry of the rods may be necessary.

With the control law. Another validation is performed by introducing the identified kinematic parameters in the control law, which uses Model 12. The end-effector is then displaced along a 100mm × 100mm square trajectory, visualized graphically. The error committed on the square side is reduced from 5mm to less than 0.5mm.

V. CONCLUSIONS

In this article, the kinematic calibration of a H4 parallel mechanism using a vision-based measuring device was presented. Using our vision system, a final positioning accuracy of the end-effector lower than 0.5mm could be obtained, and the accuracy improvement has been confirmed by several validation experiments. The vision-based measuring device allows us also to qualify directly the assumption validity concerning the number of degrees of freedom. For such a mechanism with less than six degrees of freedom, the parameter identifiability has been analyzed, showing that all the parameters related to the sensor installation cannot be identified. The lower results with the second presented kinematic model need further analysis concerning the modelling of the spatial parallelograms. To get more information about the kinematics of the mechanism, the use of the camera to look at the legs of the mechanism will be also further investigated.

Fig. 1 :

 1 Fig. 1 : H4 and vision-based measuring system

Fig. 2 :Fig. 3 :

 23 Fig. 2 : Location of the joints between base and forearms

Fig. 4 :

 4 Fig. 4 : Definition of the base frame and orientation of rotary joint between base and arm for the Model 31

Fig. 5 :

 5 Fig. 5 : Validation experiment -Kinematic constraint on the end-effector

TABLE 1 :

 1 Model 31 kinematic parameters Designation Parameter x i , y i , z i , i ∈[START_REF] Wang | On the accuracy of a Stewart platform -Part I : The effect of manufacturing tolerances[END_REF][START_REF] Wampler | Calibration of robots having kinematic closed loops using non-linear least-squares estimation[END_REF]

TABLE 2 :

 2 A priori and identified kinematic parameters of the model 12 (IS units)

		h	l	R	L
	a priori	0.060	0.2600	0.1400	0.4800
	Identified 0.0610	0.2600	0.1413	0.4876
		α 1	α 2	α 3	α 4
	a priori	0	3.1416	4.7124	4.7124
	Identified -0.0015 3.1016	4.6807	4.6859
		q 01

TABLE 3 :

 3 Mean and root mean square errors on joint variables (rad)

	Variable	q 1	q 2	q 3	q 4
		Before calibration
	Mean	9.0 E-2	3.5 E-2	7.3 E-2	8.3 E-2
	R.M.S	9.0 E-2	3.7 E-2	7.4 E-2	8.3 E-2
		After calibration -Model 12
	Mean	7.1 E-5	1.1 E-4 -7.7 E-4 -2.1 E-4
	R.M.S	1.4 E-3	1.3 E-3	1.4 E-3	2.6 E-3
		After calibration -Model 31
	Mean	-2.0 E-4 5.2 E-4 -4.7 E-4	7.4 E-5
	R.M.S	2.9 E-3	2.6 E-3	1.8 E-3	3.1 E-3

TABLE 4 :

 4 Straightness evaluation for the two experiments with initial and calibrated kinematic parameters Direction 1 2 Before calib. 1.3 E-3 2.3 E-3

VI. ACKNOWLEDGEMENTS This study was jointly funded by CPER Auvergne 2001-2003 program and by the CNRS-ROBEA program through the MAX project.


Marthe Bonamy

Łukasz Kowalik

A 13k-kernel for Planar Feedback Vertex Set via Region Decomposition *

We show a kernel of at most 13k vertices for the Feedback Vertex Set problem restricted to planar graphs, i.e., a polynomial-time algorithm that transforms an input instance (G, k) to an equivalent instance with at most 13k vertices. To this end we introduce a few new reduction rules. However, our main contribution is an application of the region decomposition technique in the analysis of the kernel size. We show that our analysis is tight, up to a constant additive term.

Introduction

A feedback vertex set in a graph G = (V, E) is a set of vertices S ⊆ V such that G -S is a forest. In the Feedback Vertex Set problem, given a graph G and integer k one has to decide whether G has a feedback vertex set of size k. This is one of the fundamental NP-complete problems, in particular it is among the 21 problems considered by Karp [START_REF] Karp | Reducibility among combinatorial problems[END_REF]. It has applications e.g. in operating systems (see [START_REF] Silberschatz | Operating System Concepts[END_REF]), VLSI design, synchronous systems and artificial intelligence (see [START_REF] Festa | Feedback set problems[END_REF]).

In this paper we study kernelization algorithms, i.e., polynomial-time algorithms which, for an input instance (G, k) either conclude that G has no feedback vertex set of size k or return an equivalent instance (G , k ), called kernel. In this paper, by the size of the kernel we mean the number of vertices of G . Burrage et al. [START_REF] Burrage | The undirected feedback vertex set problem has a poly(k) kernel[END_REF] showed that Feedback Vertex Set has a kernel of size O(k 11 ), which was next improved to O(k 3 ) by Bodlaender [START_REF] Bodlaender | A cubic kernel for feedback vertex set[END_REF] and to 4k 2 by Thomassé [START_REF] Thomassé | A 4k 2 kernel for feedback vertex set[END_REF]. Actually, as argued by Dell and van Melkebeek [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] the kernel of Thomassé can be easily tuned to have the number of edges bounded by O(k 2 ). This cannot be improved to O(k 2-) for any > 0, unless coNP ⊆ NP/ poly [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF].

In this paper we study Planar Feedback Vertex Set problem, i.e., Feedback Vertex Set restricted to planar graphs. Planar versions of NP-complete graph problems often enjoy kernels with O(k) vertices. Since an n-vertex planar graph has O(n) edges, this implies they have O(k) edges, and hence are called linear kernels. The first nontrivial result of that kind was presented in the seminal work of Alber, Fellows and Niedermeier [START_REF] Alber | Polynomial-time data reduction for dominating set[END_REF] who showed a kernel of size 335k for Planar Dominating Set. One of the key concepts of their paper was the region decomposition technique in the analysis of the kernel size. Roughly, in this method the reduced plane instance is decomposed into O(k) regions (i.e. subsets of the plane) such that every region contains O(1) vertices of the graph. It was next applied by Guo and Niedermeier to a few more graph problems [START_REF] Guo | Linear problem kernels for np-hard problems on planar graphs[END_REF]. In fact it turns out that for a number of problems on planar graphs, including Planar Dominating Set and Planar Feedback Vertex Set, one can get a kernel of size O(k) by general method of protrusion decomposition [START_REF] Fomin | Bidimensionality and kernels[END_REF]. However, in this general algorithm the constants hidden in the O notation are very large, and researchers keep working on problem-specific linear kernels with the constants as small as possible [START_REF] Chen | Parametric duality and kernelization: Lower bounds and upper bounds on kernel size[END_REF][START_REF] Luo | Improved linear problem kernel for planar connected dominating set[END_REF][START_REF] Wang | Planar graph vertex partition for linear problem kernels[END_REF][START_REF] Kowalik | Towards optimal kernel for connected vertex cover in planar graphs[END_REF][START_REF] Kowalik | Nonblocker in H-minor free graphs: Kernelization meets discharging[END_REF].

In the case of Planar Feedback Vertex Set, Bodlaender and Penninkx [START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF] gave an algorithm which outputs a kernel of size at most 112k. This was next improved by Abu-Khzam and Khuzam [1] to 97k. Very recently, and independently of our work, Xiao [START_REF] Xiao | A new linear kernel for undirected planar feedback vertex set: Smaller and simpler[END_REF] has presented an improved kernel of 29k vertices. However, neither of these papers uses the region decomposition. Indeed, it seems non-obvious how the regions of the region decomposition can be defined for Planar Feedback Vertex Set. Instead, the authors of the previous works cleverly apply simple bounds on the number of edges in general and bipartite planar graphs. Moreover, for certain problems these methods turned out to give better results and simpler proofs than those based on region decomposition, see e.g., the work of Wang, Yang, Guo and Chen [START_REF] Wang | Planar graph vertex partition for linear problem kernels[END_REF] on Connected Vertex Cover, Edge Dominating Set, and Triangle Packing in planar graphs improving previous results of Guo and Niedermeier [START_REF] Guo | Linear problem kernels for np-hard problems on planar graphs[END_REF].

Somewhat surprisingly, in this work we show that region decomposition can be successfully applied to Planar Feedback Vertex Set, and moreover it gives much tighter bounds than the previous methods. Furthermore, we add a few new reduction rules to improve the bound even further, to 13k. More precisely, we show the following result.

Theorem 1. There is an algorithm that, given an instance (G, k) of Planar Feedback Vertex Set, either reports that G has no feedback vertex set of size k or produces an equivalent instance with at most 13k -24 vertices. The algorithm runs in expected O(n) time, where n is the number of vertices of G.

We use the region decomposition approach in a slightly relaxed way: the regions are the faces of a k-vertex plane graph and the number of vertices of the reduced graph in each region is linear in the length of the corresponding face. We show that this gives a tight bound, i.e., we present a family of graphs which can be returned by our algorithm and have 13k -O(1) vertices.

Organization of the paper. In Section 2 we present a kernelization algorithm which is obtained from the algorithms in [START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF]1] by generalizing a few reduction rules, and adding some completely new rules. In Section 3 we present an analysis of the size of the kernel obtained by our algorithm. In the analysis we assume that in the reduced graph, for every induced path with internal vertices, the internal vertices have at least three neighbors outside the path. Based on this, we get the bound of (2 + 3)k -(4 + 4) for the number of vertices in the kernel. In Section 2 we present reduction rules which guarantee that in the kernel ≤ 6, resulting in the kernel size bound of 15k -28. To get the claimed bound of 13k -24 vertices in Section 4 we present a complex set of reduction rules, which allow us to conclude that ≤ 5. In Section 5 we discuss the running time of the algorithm. Finally, in Section 6 we discuss possibilities of further research.

Notation.

In this paper we deal with multigraphs, though for simplicity we refer to them as graphs. (Even if the input graph is simple, our algorithm may introduce multiple edges.)

k k Rule 2 w u v k w v k Rule 3 w u v k w k -1 Rule 4 k k Rule 5 k a b c u v k -2 Rule 6 u v w x k k v w x Rule 7
Figure 1: Reduction rules 1-7. Dashed edges are optional. We draw in black the vertices whose incident edges are all already drawn (as solid or dashed edges), in white the vertices which might be incident to other edges. Regardless of their color, vertices in the figures may not coincide.

By the degree of a vertex x in a multigraph G, denoted by deg G (x), we mean the number of edges incident to x in G. By N G (x), or shortly N (x), we denote the set of neighbors of x, while N

[x] = N (x) ∪ {x} is the closed neighborhood of x. Note that in a multigraph |N G (x)| ≤ deg G (x)
, but the equality does not need to hold. The neighborhood of a set of vertices S is defined as

N (S) = ( v∈S N (v)) \ S, while the closed neighborhood of S is N [S] = ( v∈S N (v)) ∪ S.
For a face f in a plane graph, a facial walk of f is the shortest closed walk induced by all edges incident with f . The length of f , denoted by d(f ) is the length of its facial walk.

Our kernelization algorithm

In this section we describe our algorithm which outputs a kernel for Planar Feedback Vertex Set. The algorithm exhaustively applies reduction rules. Each reduction rule is a subroutine which finds in polynomial time a certain structure in the graph and replaces it by another structure, so that the resulting instance is equivalent to the original one. More precisely, we say that a reduction rule for parameterized graph problem P is correct when for every instance (G, k) of P it returns an instance (G , k ) such that:

a) (G , k ) is an instance of P , b) (G, k) is a yes-instance of P iff (G , k ) is a yes-instance of P , and c) k ≤ k.
Below we state the rules we use. The rules are applied in the given order, i.e., in each rule we assume that the earlier rules do not apply. We begin with some rules used in the previous works [1,[START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF].

Rule 1 If there is a loop at a vertex v, remove v and decrease k by one.

Rule 2 Delete vertices of degree at most one.

Rule 3 If a vertex u is of degree two, with incident edges uv and uw, then delete u and add the edge vw. (Note that if v = w then a loop is added.) Rule 4 If a vertex u has exactly two neighbors v and w, edge uv is double, and edge uw is simple, then delete v and u and decrease k by one.

Rule 5

If there are at least three edges between a pair of vertices, remove all but two of the edges.

Rule 6 Assume that there are five vertices a, b, c, v, w such that 1) both v and w are neighbors of each of a, b, c and 2) each vertex x ∈ {a, b, c} is incident with at most one edge xy such that y ∈ {v, w}. Then remove all the five vertices and decrease k by two.

The correctness of the above reduction rules was proven in [1]. (In [1], Rule 6 is formulated in a slightly less general way which forbids multiplicity of some edges, but the correctness proof stays the same.) Now we introduce a few new rules.

Rule 7 If a vertex u has exactly three neighbors v, w and x, v is also adjacent to w and x, and both edges uw and ux are simple, then contract uv and add an edge wx (increasing its multiplicity if it already exists). If edge uv was not simple, add a loop at v. Lemma 2. Rule 7 is correct.

Proof. Let G be the graph obtained from a graph G by a single application of Rule 7. Let S be a feedback vertex set of size k in G . We claim S is a feedback vertex set in G too. Assume for a contradiction that there is a cycle

C in G -S. Then u ∈ V (C), for otherwise C ⊆ G . If v ∈ S then {wu, ux} ⊆ C and C -{wu, ux} + {wx} is a cycle in G , a contradiction. If v ∈ S, then w, x ∈ S and hence v is the only neighbor of u in G -S, so C is the 2-cycle uvu.
But then G -S contains a loop at v, a contradiction.

Let S be a feedback vertex set of size k in G. If |{u, v} ∩ S| = 2, then S \ {u} ∪ {w} is a feedback vertex set of size k in G . Assume |{u, v} ∩ S| = 1. Then we can assume v ∈ S for otherwise we replace S by S \ {u} ∪ {v}, which is also a feedback vertex set in G. If there is a cycle C in G -S , then wx ∈ E(C), for otherwise C ⊆ G -S. But then C -{wx} + {wu, ux} is a cycle in G, a contradiction. Finally, if |{u, v} ∩ S| = 0 then both w and x are in S, so S is also a feedback vertex set in G .

The graph modification in Rule 7 is an example of a gadget replacement, i.e., a subgraph of G is replaced by another subgraph in such a way that the answer to the Feedback Vertex Set problem does not change. We will use many rules of this kind, and their correctness proofs all use similar arguments. In order to make our proofs more compact, we define gadget replacement formally below, and prove a technical lemma (Lemma 3 below) which will be used in many rule correctness proofs.

Gadget replacement in graph A is a triple (X, Y, E I ), where X ⊆ V (A), Y is a set of vertices disjoint with V (A), and E I is a set of edges with both endpoints in N A (X) ∪ Y . The result of gadget replacement is a new graph B, obtained from A by deleting X and E(G[N [X]]) and inserting Y and E I .

For an example, in Rule 7, G is a result of gadget replacement ({u}, ∅, {xv, wv, xw}). Note that if (X, Y, E I ) is a gadget replacement in A that results in B then (Y, X, {uv ∈ E(A) : u, v ∈ N A [X]}) is a gadget replacement in B and its result is A. Lemma 3. Let (X, Y, E I ) be a gadget replacement in graph A, and let B be its result. Let Proof. Assume for a contradiction that there is a cycle

Q A = A[N A [X]] and Q B = B[Y ∪ N A (X)]. Let S A be a feedback vertex set in A. Let S B be a subset of vertices of B such that S A \ V (Q A ) = S B \ V (Q B ) and Q B -S B is a forest. Finally, assume that for every pair u, v ∈ N A (X) if there is a (u, v)-path in Q B -S B then there is a (u, v)-path in Q A -S A . Then S B is a feedback vertex set of B. v 1 v 2 v 3 u 1 u 2 w 1 w 2 k k y v 3 u 1 u 2 w 1 w 2 u 1 u 2 u 3 u 4 w 1 w 2 min{deg(u 1 ), deg(u 2 )} = 3 k k y u 3 u 4 w 1 w 2
C in B -S B . Since Q B -S B is a forest, C has at least one vertex outside Q B . Assume C has all vertices outside Q B . But then C ⊆ A and since S A \ V (Q A ) = S B \ V (Q B ) we also have C ⊆ A -S A ,
(B -E(Q B )) -S B . Every such subpath P B in Q B -S B is of the form v 1 , . . . , v t , where v 1 , v t ∈ N A (X) and v 2 , . . . , v t-1 ∈ V (Q B ) -S B .
Hence, by the assumption of the lemma, there is a (v 1 , v t )-path P A in Q A -S A . In particular, v 1 , v t ∈ S A (we will use this observation later). Let C be the closed walk obtained from C by replacing every maximal subpath in

Q B -S B by a path in Q A -S A . Now consider a maximal subpath P B of C in (B -E(Q B )) -S B . It is of the form v 1 , . . . , v t , where v 1 , v t ∈ N A (X) and v 2 , . . . , v t-1 ∈ (V (B) \ V (Q B )) \ S B . Since v 1 and v t are also endpoints of paths in Q B -S B , it holds that v 1 , v t ∈ S A as argued above. Since S A \ V (Q A ) = S B \ V (Q B ), it holds that v 2 , . . . , v t-1 ∈ V (A) \ S A . Hence P B ⊆ A -S A .
It follows that C is a closed walk in A-S A , hence there is a cycle in A-S A , a contradiction.

When applying Lemma 3, we will examine reachability relations in Q A -S A and in Q B -S B , in order to check whether the last assumption holds. It will be convenient to introduce the following notation. For a graph H and set of vertices S, let R H,S be the reachability relation in H truncated to S, i.e., (a, b) ∈ R H,S iff a, b ∈ S and there is an (a, b)-path in H. The set S does not need to be a subset of V (H); for every vertex a ∈ S \ V (H), {a} forms an equivalence class of R H,S .

Rule 8 Assume there are six vertices Proof. Let G be the graph obtained from a graph G by a single application of Rule 8. Note that G is a result of a gadget replacement (X, Y, E I ) with X = {v 1 , v 2 , u 1 } and Y = {y, u 1 } Let S be a feedback vertex set of size k in G. We claim that there is a feedback vertex set S in G of size at most k.

v 1 , v 2 , v 3 , u 1 , u 2 , w 1 , w 2 , such that N (u 1 ) = {w 1 , w 2 , u 2 }, N (v 1 ) = {w 1 , w 2 , v 2 }, N (v 2 ) = {w 1 , v 1 , v 3 },
If |S ∩ {w 1 , w 2 , v 1 , v 2 , u 1 }| ≥ 2, then by Lemma 3 we see that S = (S \ {w 1 , w 2 , v 1 , v 2 , u 1 })∪{w 1 , w 2 } works. Hence we can assume |S ∩{w 1 , w 2 , v 1 , v 2 , u 1 }| ≤ 1. Then S ∩{w 1 , w 2 , v 1 , v 2 , u 1 } = {w 1 } or S ∩{w 1 , w 2 , v 1 , v 2 , u 1 } = {v 1 } to hit the triangle v 1 v 2 w 1 and the quadrangle v 1 w 1 u 1 w 2 . In the prior case we pick S = S . Then R G[N G [X]]-S,{w 1 ,w 2 ,u 2 ,v 3 } and R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 2 ,v 3 } are the same relations since the v 3 v 2 v 1 path in G corresponds to the v 3 y edge in G , so Lemma 3 applies. We are left with the case S ∩{w 1 , w 2 , y 1 , u 1 } = {v 1 }. Then we pick S = (S \ {v 1 }) ∪ {y}. Again, R G[N G [X]]-S,{w 1 ,w 2 ,u 2 ,v 3 } = R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 2 ,v 3 } since the v 3 v 2 w 1 path in G corresponds to the v 3 w 1 edge in G , so Lemma 3 applies.
Let S be a feedback vertex set of size k in G . We claim that there is a feedback vertex set S in G of size at most k.

If |S ∩ {w 1 , w 2 , y 1 , u 1 }| ≥ 2, then by Lemma 3 we see that S = (S \ {y 1 , y 2 }) ∪ {w 1 , w 2 } works. Hence we can assume |S ∩ {w 1 , w 2 , y 1 , u 1 }| ≤ 1. Then S ∩{w 1 , w 2 , y 1 , u 1 } = {w 1 } or S ∩{w 1 , w 2 , y 1 , u 1 } = {y} to hit the digon w 1 y. In the prior case we pick S = S . Then R G[N G [X]]-S,{w 1 ,w 2 ,u 2 ,v 3 } = R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 2 ,v 3 } since the v 3 v 2 v 1
path in G corresponds to the v 3 y edge in G , so Lemma 3 applies. We are left with the case

S ∩{w 1 , w 2 , y 1 , u 1 } = {y}. Then we pick S = S \{y}∪{v 1 }. Again, R G[N G [X]]-S,{w 1 ,w 2 ,u 2 ,v 3 } = R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 2 ,v 3 } since the v 3 v 2 w 1 path in G corresponds to the v 3 w 1 edge in G , so Lemma 3 applies. Rule 9 Assume u 1 u 2 u 3 u 4 is an induced path such that for two vertices w 1 , w 2 outside the path, N (u 1 ) = {u 2 , w 1 , w 2 }, N (u 2 ) = {u 1 , u 3 , w 1 } and N (u 3 ) = {u 2 , u 4 , w 2 }, deg(u 3 ) = 3, and min{deg(u 1 ), deg(u 2 )} = 3. Then replace G[{u 1 , u 2 , u 3 , w 1 , w 2 }]
with the gadget presented in Figure 2 (right), i.e., remove u 1 and u 2 and add a vertex y, edges yu 3 and u 3 w 1 , and double edges yw 1 and yw 2 .

Lemma 5. Rule 9 is correct.

Proof. Let G be the graph obtained from a graph G by a single application of Rule

9. Note that G is a result of a gadget replacement (X, Y, E I ) with X = {u 1 , u 2 } and Y = {y} Let S be a solution of (G, k). If |S ∩ {w 1 , w 2 , u 1 , u 2 , u 3 }| ≥ 2 or S ∩ {w 1 , w 2 , u 1 , u 2 , u 3 } = {w 1 } we proceed as in the proof of Lemma 4. Otherwise, to hit the triangle w 1 u 1 u 2 , S ∩ {w 1 , w 2 , u 1 , u 2 , u 3 } equals either {u 1 } or {u 2 }. In both cases, R G[N G [X]]-S,{w 1 ,w 2 ,u 3 } has exactly one equivalence class {w 1 , w 2 , u 3 }. We observe that for S = S \ {u 1 , u 2 } ∪ {y} the relation R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 3 }
has also one equivalence class, so by Lemma 3, S is a solution of (G , k).

Let S be a feedback vertex set of size k in G . If |S ∩ {w 1 , w 2 , y, u 3 }| ≥ 2 we proceed as in the proof of Lemma 4. Otherwise,

S ∩ {w 1 , w 2 , u 1 , u 2 , u 3 } = {y}. If deg G (u 1 ) = 3 then we put S = S \{y}∪{u 2 }, and otherwise S = S \{y}∪{u 1 }. Note that G[{w 1 , w 2 , u 1 , u 2 , u 3 }]-S is a forest, since min{deg(u 1 ), deg(u 2 )} = 3. Moreover, R G[N G [X]]-S,{w 1 ,w 2 ,u 3 } and R G [N G [Y ]]-S ,{w 1 ,w 2 ,u 3 }
are the same (total) relation, so Lemma 3 applies and (S, k) is a solution of (G, k). Proof. Let G be the graph obtained from a graph G by a single application of Rule 10, i.e.,

Rule 10 Let A ⊆ V (G) and let w 1 and w 2 be two vertices in G, w 1 , w 2 ∈ A. If (i) no cycle in G \ {w 1 , w 2 } intersects A, and (ii) there is a subgraph Q ⊆ G[A ∪ {w 1 , w 2 }] such for every vertex x ∈ V (Q) \ {w 1 }, we have deg Q (x) ≤ |E(Q)| -|A| -1, then remove w
G = G -w 1 . Let S be a feedback vertex set of size k -1 in G . Then every cycle in G -S contains w 1 , so S ∪ {w 1 } is a feedback vertex set of size k in G.
Let S be a feedback vertex set of size On the other hand, by the degree bound, and because

k in G. If w 1 ∈ S, then clearly S \ {w 1 } is a solution of the instance (G , k -1). Hence assume w 1 ∈ S. We claim that |S ∩ V (Q)| ≥ 2. Assume the contrary, i.e., |S ∩ V (Q)| ≤ 1. Since Q -S is a forest, |E(Q -S)| ≤ |V (Q -S)| -1 = |V (Q)| -|S ∩ V (Q)| -1 = |A| + 1 -|S ∩ V (Q)|. (1) v 1 v 2 u w 1 w 2 u 1 u 2 u 3 w 1 w 2
w 1 ∈ S and |S ∩ V (Q)| ≤ 1, |E(Q -S)| ≥ |E(Q)| -(|E(Q)| -|A| -1)|S ∩ V (Q)|. (2)
By ( 1) and ( 2)

, |A| + 1 ≥ |E(Q)| -(|E(Q)| -|A| -2)|S ∩ V (Q)|. Since |S ∩ V (Q)| ≤ 1 this implies |A| + 1 ≥ |E(Q)| -(|E(Q)| -|A| -2) = |A| + 2, a contradiction. It follows that |S ∩ V (Q)| ≥ 2. Then S = S \ {u, v 1 , v 2 , v} ∪ {w 1 , w 2 } is of size at most k.
Moreover, S is a feedback vertex set in G, since S is a feedback vertex set and by (i). Again, this implies that S \ {w 1 } is a solution of the instance (G , k -1), as required.

Rule 10 is not used directly in our algorithm, because it seems impossible to detect it in O(n) time. However, to get the claimed kernel size we need just two special cases of Rule 10, which are stated in lemmas 7 and 8 below. Lemma 7. Assume there are five vertices v 1 , v 2 , u, w 1 , w 2 such that N (v 1 ) = {v 2 , w 1 , w 2 }, {w 1 , w 2 } ⊆ N (u), there is at most one edge incident to v 2 and a vertex outside {w 1 , w 2 , v 1 }, and there is at most one edge incident to u and a vertex outside {w 1 , w 2 }. Then Rule 10 applies.

Proof. It is easy to see that condition (i) of Rule 10 is satisfied. We proceed to condition (ii). Since Rule 3 does not apply, v 2 is adjacent to w 1 or w 2 ; by symmetry assume the former. Let A = {u, v 1 , v 2 }. We build E(Q) as follows. We start with

E(Q) = {v 2 w 2 , v 2 v 1 , v 1 w 1 , v 1 w 2 , uw 1 , uw 2 }. Since Rule 8 does not apply, v 2 w 2 ∈ E or one of {v 2 w 1 , uw 1 , uw 2 }
is a double edge. Hence, we add v 2 w 2 or another copy of one of {v 2 w 1 , uw 1 , uw 2 } to E(Q), respectively. Note that for every

x ∈ V (Q) \ {w 1 } we have deg Q (x) ≤ 3 = |E(Q)| -|A| -1, as required. Lemma 8. Assume there are five vertices u 1 , u 2 , u 3 , w 1 , w 2 such that N (u 1 ) = {w 1 , w 2 , u 2 }, {u 1 , u 3 } ⊆ N (u 2 ) ⊆ {w 1 , w 2 , u 1 , u 3 },
and there is at most one edge incident to u 3 and a vertex outside {w 1 , w 2 , u 2 }. Moreover, the edges v 1 v 2 and v 2 v 3 are simple. Then Rule 10 applies.

Proof. It is easy to see that condition (i) of Rule 10 is satisfied. We proceed to condition (ii).

Let A = {u 1 , u 2 , u 3 }. We build E(Q) as follows. We start with E(Q) = {u 1 w 1 , u 1 w 2 , u 1 u 2 , u 2 u 3 }.
There are some cases to consider. Since Rule 3 does not apply, u 2 w 1 ∈ E or u 2 w 2 ∈ E. CASE 1: u 2 w 1 , u 2 w 2 ∈ E. Then, since Rule 7 does not apply to the w 1 u 1 w 2 u 2 cycle, u 1 w 1 or u 1 w 2 is a double edge. Moreover, since Rule 3 does not apply, u 3 w 1 ∈ E or u 3 w 2 ∈ E. We add to E(Q) edges u 2 w 1 , u 2 w 2 , either u 3 w 1 or u 3 w 2 (but not both), and the second copy of either u 1 w 1 or u 1 w 2 (but not both). Then

|E(Q)| = 8 and max x∈V (Q)\{w 1 } deg Q (x) = 4 = |E(Q)| -|A| -1, so (ii) holds.
CASE 2: Exactly one of u 2 w 1 and u 2 w 2 is an edge; by symmetry assume u 2 w 1 ∈ E and u 2 w 2 ∈ E. Since Rule 7 does not apply, u 3 w 1 ∈ E. And then since Rule 3 does not apply, u 3 w 2 ∈ E. CASE 2.1: u 3 w 2 is a double edge. We add to E(Q) edge u 2 w 1 , and both copies of

u 3 w 2 . Then |E(Q)| = 7 and max x∈V (Q) deg Q (x) = 3 = |E(Q)| -|A| -1, so (ii) holds. CASE 2.2: u 3 w 2 is a simple edge. Since Rule 9 does not apply, deg G (u 1 ) ≥ 4 and deg G (u 2 ) ≥ 4.
We add to E(Q) edges u 2 w 1 and u 3 w 2 , exactly one edge incident to u 1 which is not yet in E(Q) and exactly one edge incident to

u 2 which is not yet in E(Q). Then |E(Q)| = 8 and max x∈V (Q)\{w 1 } deg Q (x) = 4 = |E(Q)| -|A| -1, so (ii) holds.
The following rule was shown to be correct by Abu-Khzam and Khuzam in [1].

Rule 11 Assume there is an induced path with endpoints u and v and with six internal vertices v 1 , . . . , v 6 such that for some vertices w 1 , w 2 outside the path

N ({v 1 , . . . , v 6 })\{u, v} = {w 1 , w 2 }. If |N (w 1 ) ∩ {v 1 , . . . , v 6 }| ≥ |N (w 2 )
∩ {v 1 , . . . , v 6 }|, then remove w 1 and decrease k by one.

In [1] it was assumed that when Rule 11 described above is applied, G does not contain an induced path v 1 , . . . , v 5 such that for some vertex w, we have

N (v 2 , v 3 , v 4 ) \ {v 1 , v 5 } = {w}.
In our algorithm this is guaranteed by Rule 7 (slightly more general than their Rule 6). We are able to extend Rule 11 as follows.

Lemma 9. Assume there is an induced path with endpoints u and v and with five internal vertices v 1 , . . . , v 5 such that for some vertices w 1 , w 2 outside the path N ({v 1 , . . . , v 5 })\{u, v} = {w 1 , w 2 }. Then there is an instance

(G , k ) with |V (G )| < |V (G)| such that (G, k) is a yes- instance iff (G , k ) is a yes-instance and k ≤ k.
The proof of Lemma 9 involves five more rules and is quite technical; we defer it to Section 4. We stress here that Lemma 9 is not crucial for getting a substantial improvement of the kernel size. Indeed, if one uses Rule 11 instead of Lemma 9, the resulting kernel is of size at most 15k -28 (see Section 3). Let us also remark that by the analysis in Section 3, if someone manages to exclude paths described in Lemma 9 with only four internal vertices, the kernel size decreases further to 11k -20.

To complete the algorithm we need a final rejecting rule which is applied when the resulting graph is too big. In Section 3 we prove that Rule 12 is correct.

Rule 12

If the graph has more than 13k -24 vertices, return a trivial no-instance (conclude that there is no feedback vertex set of size k in G).

The size bound

In this section we prove the following theorem.

Theorem 10. Let G be a planar graph such that rules 1-9 do not apply and G does not contain the configurations described in lemmas 7 and 8. Assume also that for every induced path P with endpoints u and v and with internal vertices v 1 , . . . , v the internal vertices have at least three neighbors outside the path, i. Let S be a feedback vertex set of size k in G (i.e., a "solution"), and let F be the forest induced by V (G) \ S. Denote the set of vertices of F by V F = V (G) \ S. We call the vertices in S solution vertices and the vertices in V F forest vertices.

A partition of V F . Now we define some subsets of V F . Let I 2 , I 3 + ⊆ V F denote the vertices whose degree in F is two or at least three, respectively. The leaves of F are further partitioned into two subsets. Let L 2 and L 3 + be the leaves of F that have two or at least three solution neighbors, respectively. By rules 2 and 3 all the vertices in G have degree at least 3. Hence, if a leaf of F has fewer than two solution neighbors, Rule 4 or Rule 5 applies. It follows that every leaf of F belongs to L 2 ∪ L 3 + . This proves claim (i) of Lemma 11 below.

Lemma 11. Graph G satisfies the following properties.

(i) The sets I 2 , I 3 + , L 2 , L 3 + form a partition of V F .
(ii) For every pair u, v of solution vertices there are at most two vertices x, y ∈ L 2 such that N (x) ∩ S = N (y) ∩ S = {u, v}.

(iii) Every vertex of G is of degree at least three.

(iv) Every face of G is of length at least two.

Claim (ii) follows from the fact that Rule 6 does not apply to G. Claim (iii) follows because rules 2 and 3 do not apply to G and Claim (iv) by Rule 1.

The inner forest. Let F I be the forest on the vertex set I 3 + ∪ L 3 + such that uv ∈ E(F I ) iff for some integer i ≥ 0, there is a path ux 1 • • • x i v in forest F such that u, v ∈ I 3 + ∪ L 3 + and for every j = 1, . . . , i, vertex x i belongs to I 2 .

Three sets of short chains. A path in F consisting of vertices from I 2 ∪ L 2 will be called a chain. A chain is maximal if it is not contained in a bigger chain. In what follows we introduce three sets of (not necessarily maximal) chains, denoted by CL 2 , C 2 -and C 3 + . We will do it so that each vertex in I 2 belongs to at least one chain from these sets of chains.

For every vertex x ∈ L 2 , we consider the maximal chain (y 1 , . . . , y p ) of degree 2 vertices in F such that y 1 is adjacent to x and no y i has a solution neighbor outside N G (x) ∩ S. Then the chain (x, y 1 , . . . , y p ) is an element of CL 2 . Note that

L 2 ⊆ V (CL 2 ).
Chains of C 2 -and C 3 + are defined using the following algorithm. We consider maximal chains in F , one by one (note that all maximal chains are vertex-disjoint). Let c = (x 1 , x 2 , . . . , x p ) be a maximal chain. The vertices of c are ordered so that if {x 1 , x p } ∩ L 2 = ∅, then x p ∈ L 2 . Using vertices of c we form disjoint bounded length chains and put them in the sets C 2 -and C 3 + as follows. Assume that for some i < p the vertices of a prefix (x 1 , x 2 , . . . , x i ) have been already partitioned into such chains (in particular i = 0 if we begin to process c). There are three cases to consider. Consider a shortest chain c i = (x i+1 , . . . , x j ) such that the vertices of c i have at least three solution neighbors, i.e., |S ∩ N ({x i+1 , . . . , x j })| ≥ 3. If the chain c i exists, we put it in C 3 + , and we proceed to the next vertices of c. Otherwise we consider the chain c i = (x i+1 , . . . , x p ). Note that vertices of c i have at most two solution neighbors.

If x p ∈ I 2 , then we add the chain c i to C 2 -and we finish processing c. Note that then x p is adjacent to a vertex u ∈ L 3 + ∪ I 3 + (otherwise c is not maximal, as we can extend it by a vertex in L 2 ). Moreover, because of the order of the vertices in c, we know that x 1 ∈ L 2 .

It follows that x 1 is also adjacent to a vertex v ∈ L 3 + ∪ I 3 + . Hence, uv ∈ E(F I ). We assign chain c i to edge uv.

If x p ∈ L 2 , then we do not form a new chain and we finish processing c. Note, however, that the vertices {x i+1 , . . . , x p } ∩ I 2 belong to a chain in CL 2 .

Note also that some vertices of the first chain c 0 can belong to two chains, one in C 3 + and one in CL 2 .

Let us summarize the main properties of the construction.

Lemma 12. The following properties hold: From now on, we fix a plane embedding of G. The vertices of H S are embedded in the plane exactly in the same points as in G. The edge multiset E S is defined as follows. For every triple (u, x, v) such that u, v ∈ S, x ∈ L 2 and there is a path uxv in G, we put an edge uv in E S . Moreover, the edge uv is embedded in the plane exactly as one of the corresponding paths uxv (note that there can be up to four such paths if some edges are double). Note that by Lemma 11(ii), every edge of H S has multiplicity at most two. The set of faces of H S is denoted by F S . By F S,2 we denote its subset with the faces of length two, while F S,3+ are the remaining faces. Note that there are no faces of length 1 in H S .

(i)
Lemma 13. We have

|V (CL 2 )| ≤ 2(|E S | -|F S,2 |).
Proof. By the definition, for every vertex x ∈ L 2 there is a corresponding edge uv ∈ E S , where N G (x) ∩ S = {u, v}. Also, for every chain c in CL 2 there is a corresponding vertex x ∈ L 2 , and thus a corresponding edge uv ∈ E S . We assign x, c and the vertices of c to the pair {u, v}.

Consider an arbitrary pair u, v such that uv ∈ E S . Note that there are exactly |E S |-|F S,2 | such pairs. We claim that there are at most two elements in V (CL 2 ) assigned to the pair {u, v}. Indeed, by Lemma 11(ii), there are at most two vertices in L 2 assigned to {u, v}. If there are no such vertices, no chain in CL 2 is assigned to {u, v}, so the claim holds. If there is exactly one vertex x ∈ L 2 assigned, there is exactly one chain c ∈ CL 2 assigned. By Lemma 5, chain c has at most two vertices, so the claim holds. Finally, if there are exactly two vertices x, y ∈ L 2 assigned, there are exactly two chains c x and c y assigned. By Lemma 4 we have |V (c x )| = |V (c y )| = 1. This concludes the proof.

Maximality.

In what follows we assume that graph G is maximal, meaning that one can add neither an edge to E(G) nor a vertex to L 2 obtaining a graph G such that S is still a feedback vertex set of G and all the claims of lemmas 11, 12 and 13 hold. Note that the number of L 2 -vertices which can be added to G is bounded, since each such vertex corresponds to an edge in H S , and H S has at most 6|S| edges as a plane multigraph with edge multiplicity at most two. Similarly, once the set of L 2 -vertices is maximal, and hence the vertex set of G is fixed, the number of edges which can be added to G is bounded by 6|V (G)|. It follows that such a maximal supergraph of G exists. Clearly, it is sufficient to prove Theorem 10 only in the case when G is maximal. Lemma 14. The planar graph H S is connected.

Proof. Assume now for contradiction that there is a partition S = S 1 ∪ S 2 such that there is no edge in H S between a vertex of S 1 and a vertex of S 2 .

Every face of G is incident to at least one vertex of S, for otherwise the boundary of the face does not contain a cycle, a contradiction. Assume that a face f of G contains a solution vertex u 1 in S 1 and a solution vertex u 2 in S 2 . Then we can add a vertex x, two edges xu 1 and two edges xu 2 . Note that S is still a feedback vertex set in the new graph; in particular now x ∈ L 2 . In the new graph there are no more vertices in L 2 adjacent to both u 1 and u 2 because of our assumption that S 1 and S 2 are not connected by an edge in H S , so Lemma 11(ii) holds. Moreover, |V (CL 2 )| was increased by one and |E S | -|F S,2 | was also increased by one, so Lemma 13 holds. The other claims of lemmas 11 and 12 trivially hold, so F is not maximal, a contradiction.

Let F 1 and F 2 be the collections of faces of G containing a vertex in S 1 , or in S 2 , respectively. We have shown above that F 1 ∪ F 2 is a partition of the set of all the faces of G. Let V 1 and V 2 denote the sets of vertices incident to a face in F 1 , or in F 2 , respectively. Note that V 1 ∩ V 2 = ∅, since there must be two neighboring faces, one in F 1 and the other in

F 2 . Let x ∈ V 1 ∩ V 2 . Since faces of G are of length at least two, x has in G at least two neighbors in V 1 ∩ V 2 . It follows that G[V 1 ∩ V 2 ] has minimum degree two, so G[V 1 ∩ V 2 ] contains a cycle. However, (V 1 ∩ V 2 ) ∩ S = ∅, since F 1 and F 2 are disjoint. Hence V 1 ∩ V 2 ⊆ F , a contradiction.
Bounding the number of forest vertices in a face of H S . For a face f of H S and a set of vertices A ⊆ V (G) we define A f as the subset of A of vertices which are embedded in f or belong to the boundary of f . Note that all vertices of every chain belong to the same face f of H S . When C is a set of chains, by C f we denote the subset of chains of C which lie in f , i.e.,

C f = {c ∈ C : V (c) ⊆ V (G) f }. Lemma 15. For every face f of H S , it holds that |L f 3 + | + |I f 3 + | + |C f 3 + | ≤ d(f ) -2.
Proof. First we note that the forest F f is in fact a tree. Indeed, if F f has more than one component, we can add an edge between two solution vertices on the boundary of f preserving planarity, what contradicts the assumed maximality.

Consider a plane subgraph A of G induced by V (G) f , i.e., we take the plane embedding of G and we remove the vertices outside V (G) f . Then we can define graph A S , analogously to H S . We treat f as a face of A S . Let u 1 u 2 • • • u d(f ) u 1 be the facial walk of f . Consider an arbitrary vertex x of I f 3 + . Let T 1 , . . . , T r be the r trees obtained from the tree T in F containing x after removing r from T . Then r ≥ 3 since x has at least three neighbors in T . By planarity, there are 2r indices b 1 , e 1 , b 2 , e 2 , . . . , b r , e r such that for every i = 1, . . . , r what, by Lemma 15 , is bounded by

{u b i , u e i } ⊆ N (V (T t )) ∩ {u 1 , . . . , u d(f ) } ⊆ {u b i , u b i +1 , . . . , u e i }.
1 + • (d(f ) -3) = • (d(f ) -2) -( -1), as required. Lemma 17. For every face f in H S of length two, V f F ⊆ V (CL f 2 ).
Proof. Since the boundary of f has only two solution vertices, F f contains no vertices of L f 3 + , V (C 3 + ) f or I f 3 + . Then by Lemma 12(iv), C f 2 -is also empty. The claim follows. Now we proceed to the bound of Theorem 10. By Lemmas 16 and 17 we have

|V F | ≤ |V (CL 2 )| + f ∈F S,3+ ( (d(f ) -2) -( -1))
By Lemma 13 we get

|V F | ≤ 2(|E S | -|F S,2 |) + f ∈F S,3+ ( (d(f ) -2) -( -1)) = 2(|E S | -|F S,2 |) + f ∈F S ( (d(f ) -2) -( -1)) + ( -1)|F 2,S | = (2 + 2)|E S | -(3 -1)|F S | + ( -3)|F 2,S | = (2 + 2)|E S | -(2 + 2)|F S | -( -3)|F S | + ( -3)|F 2,S | ≤ (2 + 2)(|E S | -|F S |).
By Lemma 14 graph H S is connected, so we can apply Euler's formula This concludes the proof of Theorem 10. By Lemma 9, we can put = 5, which results in |V (G)| ≤ 13k -24. In Figure 4 we show an example of a graph, where our reduction rules do not apply and our analysis is tight (up to a constant additive term).

|S| -|E S | + |F S | = 2. Thus, |V (G)| = |V F | + |S| ≤ (2 + 2)(|S| -2) + |S|, = (2 + 3)k -(4 + 4). u x 1 x 2 x 3 v w 1 w 2
u 0 u v 0 y v w 1 w 2 u 0 u v 0 y v w 1 w 2 u 0 u v 0 y 2 y 1 v w 1 w 2

Reducing induced 5-paths with at most two neighbors

This section is devoted to a proof of Lemma 9. Let us recall its statement here.

Lemma 9 (restated). Assume there is an induced path u 0 ux 1 x 2 x 3 vv 0 such that for some vertices w 1 , w 2 outside the path N ({u,

x 1 , x 2 , x 3 , v}) \ {u 0 , v 0 } = {w 1 , w 2 }. Then there is an instance (G , k ) with |V (G )| < |V (G)| such that (G, k) is a yes-instance iff (G , k ) is a yes-instance and k ≤ k. Denote the path ux 1 x 2 x 3 v by P . Let Q = G[V (P ) ∪ {w 1 , w 2 }]. By symmetry we assume |N (w 1 ) ∩ V (P )| ≥ |N (w 2 ) ∩ V (P )|.
Then also |N (w 1 ) ∩ V (P )| ≥ 3, for otherwise Rule 3 applies. In our proof of Lemma 9 we do not apply a single rule, but one of four rules. The kernelization algorithm finds the family S of all feedback sets of Q. (Note that there is a bounded number of such sets.) Based on the structure of S, one of the four rules is chosen and applied. Let us also define δ(Q) = N G (X) = {u, v, w 1 , w 2 }. Let us state the rules now. Rule 13 Assume every set S Q ∈ S satisfies at least one of the conditions below: 1)-( 4) or (5) the sets {v} and {u, w 1 , w 2 } are the equivalence classes of R Q-S Q ,δ(Q) , then replace Q by the gadget from Figure 6 (left), i.e., remove x 1 , x 2 , x 3 and edges in G[Q], and add a vertex y and edges uy, yv, uw 1 , uw 2 and double edges vw 1 , vw 2 , yw 1 , yw 2 .

(1) |S Q | ≥ 3, (2) Q -S Q contains a (u, v)-path, (3) w 1 ∈ S Q , or (

Rule 16

If every set S Q ∈ S satisfies at least one of the conditions ( 1)-( 5) or (6) the sets {u} and {v, w 1 , w 2 } are the equivalence classes of R Q-S Q ,δ(Q) , then replace Q by the gadget from Figure 6 (middle), i.e., remove x 1 , x 2 , x 3 and edges in G[Q], and add a vertex y and edges uy, yv, uw 1 , uw 2 , vw 1 , vw 2 and double edges yw 1 , yw 2 .

Rule 17

If every set S Q ∈ S satisfies at least one of the conditions ( 1)-( 5) or

(7) the sets {u, w 2 } and {v, w 1 } are the equivalence classes of R Q-S Q ,δ(Q) ,
then replace Q by the gadget from Figure 6 (right), i.e., remove x 1 , x 2 , x 3 and edges in G[Q], and add vertices y 1 , y 2 and edges uy 1 , y 1 y 2 , y 2 v, uw 2 , y 1 w 2 , y 2 w 2 , y 2 w 1 , vw 1 and a double edge y 1 w 1 .

Note that the graph modifications in rules 15-17 can be phrased as gadget replacements (X, Y, E I ) in graph G, where X = {x 1 , x 2 , x 3 }, Y = {y} for rules 15 and 16, while Y = {y 1 , y 2 } for Rule 17.

Lemma 18. If there is an induced path described in Lemma 9, then one of rules 13-17 applies. Moreover, if Rule 17 is applied, then S contains both a set satisfying (5) and a set satisfying [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF].

Proof. Assume rules 13-16 do not apply. We will show that Rule 17 applies. Then there is a set S Q ∈ S that satisfies none of ( 1)-( 6). Since (1), ( 3) and ( 4) do not hold for S Q , we infer that |S Q | ≤ 2 and S Q ⊆ {u, x 1 , x 2 , x 3 , v}. Recall that |N (w 1 ) ∩ V (P )| ≥ 3. Let p, q, r be three arbitrary vertices of N (w 1 ) ∩ V (P ), sorted by increasing distance from u in the path ux 1 x 2 x 3 v. Assume |S Q | ≤ 1. Then q ∈ S Q , for otherwise S Q is not a feedback vertex set of Q. But then there is a (u, v)-path in Q -S Q : from u follow the path ux 1 x 2 x 3 v to p, then via w 1 to r and again follow the path ux 1 x 2 x 3 v to v. Hence S Q satisfies (2), a contradiction. In what follows we assume

|S Q | = 2. CASE 1: In Q -S Q there is an edge ab ∈ E(P ).
Then in particular a, b ∈ S Q . Since Rule 3 does not apply, both a and b have a neighbor in {w 1 , w 2 }. However, since Q -S Q does not contain cycles, the neighbor of a is different than the neighbor of b. Hence, Q -S Q contains path w 1 abw 2 or path w 1 baw 2 . If u ∈ {a, b}, S Q satisfies (5), a contradiction, and if v ∈ {a, b}, S Q satisfies ( 6), a contradiction. Hence {u, v} ∩ {a, b} = ∅. It follows that {a, b} = {x 1 , x 2 } or {a, b} = {x 2 , x 3 }. In the former case x 3 ∈ S Q and in the latter case x 1 ∈ S Q , for otherwise Q-S Q has a cycle because x 3 (resp. x 1 ) has a neighbor in {w 1 , w 2 } by Rule 3. Since |S Q | = 2, it follows that exactly one of u, v is not in S Q . But by Rule 3 both of them have a neighbor in {w 1 , w 2 }, so ( 5) or ( 6) is satisfied, a contradiction.

CASE 2: Q -S Q contains no edge of E(P ). Then S Q = {x 1 , x 3 }.
If uw 2 ∈ E, then vw 2 ∈ E, for otherwise (2) holds. It follows that vw 1 ∈ E, for otherwise Rule 3 applies. Then uw 1 ∈ E, for otherwise (2) holds.

By the same arguments, if uw 2 ∈ E, then uw 1 ∈ E, vw 1 ∈ E and vw 2 ∈ E. We see that the two cases above are symmetric, so let us consider only the former one, i.e., uw 2 , vw 1 ∈ E and uw 1 , vw 2 ∈ E. Then also w 1 w 2 ∈ E, for otherwise (2) holds.

CASE 2.1: x 2 w 1 ∈ E. Since Rule 3 does not apply, x 2 w 2 ∈ E. Since |N (w 1 ) ∩ V (P )| ≥ 3, x 1 , x 3 ∈ N (w 1 ). Hence N Q (w 1 ) = {x 1 , x 3 , v}. Since |N (w 2 ) ∩ V (P )| ≤ |N (w 1 ) ∩ V (P )| and |N (w 2 ) ∩ V (P )| ≥ 3 as Rule 14 does not apply, we get |N (w 2 ) ∩ V (P )| = 3. It follows that either N Q (w 2 ) = {u, x 1 , x 2 } or N Q (w 2 ) = {u, x 2 , x 3 }. In both cases S Q satisfies (7). CASE 2.1.1: N Q (w 2 ) = {u, x 1 , x 2 }.
Consider an arbitrary S Q ∈ S that satisfies none of ( 1)-( 4) or [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF]. Similarly as we argued for S Q , S Q ⊆ {u, x 1 , x 2 , x 3 , v} and |S Q | ≤ 2. Then x 1 ∈ S Q , for otherwise it is impossible to hit all three cycles w 2 ux 1 , w 2 x 1 x 2 and w 1 x 3 v. It follows that S Q contains x 3 or v, but in the former case ( 7) holds. Hence S Q = {x 1 , v}, and ( 5) holds for S Q . This proves our claim. CASE 2.1.2: N Q (w 2 ) = {u, x 2 , x 3 }. Then we rename vertices of Q: swap names of w 1 and w 2 , u and v, x 1 and x 3 , obtaining N Q (w 1 ) = {x 1 , x 2 , v} and N Q (w 2 ) = {u, x 1 , x 3 }. Notice that in this new setting {x 1 , x 3 } is still a feedback vertex set of Q and satisfies [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF]. In the new setting, consider an arbitrary S Q ∈ S that satisfies none of ( 1)-( 4) or [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF]. Similarly as we argued for S Q , S Q ⊆ {u, x 1 , x 2 , x 3 , v} and |S Q | ≤ 2. Then x 1 ∈ S Q , for otherwise it is impossible to hit all three cycles w 2 ux 1 , w 1 x 1 x 2 and w 1 x 1 w 1 x 3 v. It follows that S Q contains x 2 , x 3 or v, but in the first case (2) holds and in the second case [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] holds. Hence S Q = {x 1 , v}, and ( 5) holds for S Q . This proves our claim. CASE 2.2:

x 2 w 1 ∈ E. Then x 2 w 2 ∈ E, for otherwise (2) holds. Since |N (w 2 ) ∩ V (P )| ≥ 3 by Rule 14, x 1 , x 3 ∈ N (w 2 ). Hence N Q (w 2 ) = {u, x 1 , x 3 }. Since |N (w 1 ) ∩ V (P )| ≥ 3, we have x 1 w 1 ∈ E or x 3 w 1 ∈ E.
If both edges x 1 w 1 and x 3 w 1 are present, then Rule 7 applies, a contradiction. It follows that either N Q (w 2 ) = {x 1 , x 2 , v} or N Q (w 2 ) = {x 2 , x 3 , v}. The former case was already considered in Case 2.1.2 (after renaming vertices). In the latter case, we rename vertices by swapping names of w 1 and w 2 , u and v, x 1 and x 3 . Thus we obtain the already considered Case 2.1.1.

The lemma below will be very useful in proving that the rules above are correct in particular settings of subgraph Q.

Lemma 19. In each of the situations below all rules 13-17 are correct.

(i) (G, k) is a no-instance.
(ii) there is a solution S to the instance (G, k) such that |V (Q) ∩ S| ≥ 2 and

(ii.1) |V (Q) ∩ S| ≥ 3, or (ii.2) in Q -S there is an (x 1 , x 5 ) path, or (ii.3) w 1 ∈ S, or (ii.4) w 2 ∈ S.
Proof. We begin with (i). We need to show that for each of the rules 13-17 the resulting instance (G , k ) is a no-instance. Assume the contrary, i.e., let S be a solution of (G , k ). We will show that there is a solution S of (G, k), contradicting our assumption. For rules [START_REF] Kowalik | Towards optimal kernel for connected vertex cover in planar graphs[END_REF] Hence we can assume that there is no (u, v) path in G -S . Note that this implies that V (Q ) ∩ S is equal to {u, y} for Rule 15, {u, y} or {y, v} for Rule 16, and {y 1 , y 2 } or {y 1 , v} for Rule 17.

Consider Rule 15. Since Rule 13 does not apply, there is at least one feedback vertex set S Q ∈ S of size at most two which satisfies [START_REF] Burrage | The undirected feedback vertex set problem has a poly(k) kernel[END_REF]. Since V (Q ) ∩ S = {u, y}, the equivalence classes of R Q -S ,δ(Q) are {v} and {u, w 1 , w 2 }, hence by Lemma 3 (for

A = G and B = G) S = S \ V (Q ) ∪ S Q is a feedback vertex set G, so (G, k) is a yes-instance.
Now consider Rule 16. Note that it cannot happen that S contains only sets that satisfy ( 1)-( 4), or ( 6), because then Rule 15 applies to Q with vertices renamed (swap the names of u and v, x 1 and x 3 ). Since rules 13 and 15 do not apply to Q, S contains both a feedback vertex set S 1 Q ∈ S which satisfies ( 5) and S 2 Q ∈ S which satisfies ( 6), and |S

Q |, |S (5)
Q | ≤ 2. Since V (Q ) ∩ S = {u, y} or V (Q ) ∩ S = (6)
Q | satisfying ( 5) and a set |S

Q | satisfying [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF]. Since V (Q ) ∩ S = {y 1 , y 2 } or V (Q ) ∩ S = {y 1 , v} the equivalence classes of R Q -S ,δ(Q) are {u, w 2 } and {v, w 1 }, or {v} and {u, w 1 , w 2 }, respectively. In the former case we put S = S \ V (Q ) ∪ S [START_REF] Dell | Satisfiability allows no nontrivial sparsification unless the polynomial-time hierarchy collapses[END_REF] Q and in the latter one

S = S \ V (Q ) ∪ S (5)
Q . By Lemma 3 (for A = G and B = G) S is a feedback vertex set G, so (G, k) is a yes-instance. This ends the proof of (i).

We proceed to (ii). We need to show that in each of the cases (ii.1)-(ii. [START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF], (G , k ) is a yes-instance. To this end we will show a feedback vertex set S of size at most k in G .

For (ii. 1) we pick S = (S \V (Q))∪{u, w 1 , w 2 }. Then the equivalence classes of R Q -S ,δ(Q) are all singletons, so by Lemma 3 (for A = G, B = G ) S is a feedback vertex set of G .

For (ii.2) we pick S = (S \ V (Q)) ∪ {w 1 , w 2 }. Then the equivalence classes of R Q -S ,δ(Q) are {u, v}, {w 1 } and {w 2 }, so by Lemma 3 (for A = G, B = G ) S is a feedback vertex set of size at most k in G .

For (ii.3) we consider two cases. In case of rules 13 and 14 it is clear that S = S \ {w 1 } works. Hence we can assume that Rule 14 does not apply. Let p, q, r be arbitrary three vertices of N (w 2 ) ∩ V (P ), in the order of increasing distance from u in the path P . We can assume that |V (Q) ∩ S| ≤ 2, for otherwise we use (ii. 1). Then r ∈ S, for otherwise we need to include both p and q (at least) to hit all the cycles of Q. Hence V (Q) ∩ S = {w 1 , r}. But then there is a path going from u to p along P , then via w 2 to r and to v along P . Hence we apply (ii.2).

For (ii. [START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF], we can assume that |V (Q) ∩ S| ≤ 2 and w 1 ∈ S, for otherwise we apply (ii.1) or (ii.3). Since |N (w 1 ) ∩ V (P )| ≥ 3 we can pick three vertices p, q, r of N (w 1 ) ∩ V (P ), in the order of increasing distance from u in the path P . Then r ∈ S, for otherwise we need to include both p and q (at least ) to hit all cycles of Q. Hence V (Q) ∩ S = {w 2 , r}. But then there is a path going from u to p along P , then via w 1 to r and to v along P . Hence we apply (ii.2).

Lemma 20. Rules 13-17 are correct.

Proof. By Lemma 19(i) it suffices to prove the correctness when there is a feedback vertex set S of size at most k. R Q-{w 1 ,z},{w 1 ,w 2 ,u,v} are {v}, {w 1 } and a partition of {u, w 2 }. Then, by Lemma 3 (applied to A = B = G), S 1 = S \ V (Q) ∪ {w 1 , z} is another feedback vertex set of size at most k in G and we can apply Lemma 19. This finishes the proof of correctness of Rule 14. Now consider Rule 15. Since S ∩ V (Q) satisfies none of ( 1)-( 4), we infer that (5) applies to S ∩ V (Q). Then we pick S = S \ V (Q) ∪ {y, v}. Note that the equivalence classes of both R Q -S ,δ(Q) and R Q-S,δ(Q) are {v}, {u, w 1 , w 2 }. Then, by Lemma 3 S is a feedback vertex set in G . Now consider Rule 16. Since S ∩ V (Q) satisfies none of ( 1)-( 4), we infer that ( 5) or ( 6) applies to S ∩V (Q). Then we pick S = S \V (Q)∪{y, v} or S = S \V (Q)∪{u, y}, respectively. Note that the equivalence classes of both R Q -S ,δ(Q) and R Q-S,δ(Q) are either {v}, {u, w 1 , w 2 } or {u}, {v, w 1 , w 2 }. Then, by Lemma 3 S is a feedback vertex set in G .

Finally consider Rule 17. Since S ∩ V (Q) satisfies none of ( 1)-( 4), we infer that ( 5) or ( 7) applies to S ∩ V (Q). Then we pick S = S \ V (Q) ∪ {y 1 , v} or S = S \ V (Q) ∪ {y 1 , y 2 }, respectively. Note that the equivalence classes of both R Q -S ,δ(Q) and R Q-S,δ(Q) are either {v}, {u, w 1 , w 2 } or {u, w 2 }, {v, w 1 }. Then, by Lemma 3, S is a feedback vertex set in G . This finishes the proof of Lemma 9.

Running time

It is easy to see that each of our reduction rules can be detected and performed in O(n) time in such a way that loops and triple edges are not introduced. Since every rule except for Rule 1 and Rule 5 decreases the number of vertices, the total time needed for detecting and performing them is O(n 2 ). In what follows we will show that it can be improved to O(n) expected time.

We assume that the graph is stored using adjacency lists. Additionally, we use four data structures:

• A dictionary D 1 implemented as a hash table storing all pairs of adjacent vertices. The hash table stores the corresponding two adjacency list elements for each such pair.

• A dictionary D 2 implemented as a hash table storing all pairs of vertices (x, y) for which the set S x,y = {z ∈ V : x, y ∈ N (z) and there is at most one edge zu such that u ∈ {x, y}} is nonempty. The hash table stores the set S x,y for each such pair.

• A queue Q 3+ storing all pairs (x, y) such that |S x,y | ≥ 3.

• A queue Q s storing vertices with at most four neighbors (not necessarily all).

Once we have the dictionary D 1 answering adjacency queries in constant expected time, it is easy to detect and apply Rule 1 and Rule 5 immediately after a graph modification. The total expected time needed for that is bounded by total time of graph modifications. Hence, in what follows we exclude from our considerations Rule 1 and Rule 5 and we can assume that application of every rule decreases the number of vertices.

The major challenge in implementing the kernelization algorithm efficiently is detecting that a rule applies. In other words we have to find the particular subgraphs described in the rules, which we call configurations, efficiently. If a configuration C appears in G then there is an injective homomorphism h C : V (C) → V (G). Vertices of every configuration are partitioned into two categories: black and white vertices, defined in the figures. Let B C and W C denote the corresponding sets of vertices of C.

Lemma 21. Assume Q 3+ is empty. Then for every vertex v of G with at most four neighbors one can check in O(1) time whether there is a configuration C in G such that h -1 C (v) is a black vertex.

Proof. Since the number of configurations used in the algorithm is bounded, we can consider a fixed configuration C. We claim that there are only O(1) candidate homomorphisms to check. Note that in each configuration, every white vertex has a black neighbor. It follows that it suffices to show that there are O(1) mappings of all the black vertices of C to V (G) that can extend to a homomorphism h C , since the configurations are bounded and black vertices have bounded degree. This claim is immediate for configurations where black vertices induce a connected subgraph. The remaining configurations are those from Rule 6, Rule 8, and Lemma 7. Since Q 3+ is empty, Rule 6 does not apply. In the configurations from the remaining two rules black vertices induce exactly two connected components. Moreover, for both these configurations, once we fix a mapping h of black vertices in the connected component Clearly, both invariants hold before before the while loop (Invariant 2 holds since all the black vertices have at most four neighbors). Moreover, after every modification of G resulting in an application of a rule we update the data structures so that both invariants hold, as follows.

Q of C[B C ] such that h -1 (v) ∈ V (Q),
• Whenever an adjacency list changes, we update D 1 .

• If the set of incident edges of a vertex v with at most four neighbors changes, then we add v to Q s , and for every pair (x, y) of its neighbors we add the pair to D 2 if needed; if |S x,y | grows to three, we add the pair to Q 3+ .

• If an edge xy is added to G, we add all elements of S x,y to Q s . Note that then Q 3+ = ∅, since in Rule 6 no edges are added. Hence |S x,y | ≤ 3.

It is easy to check that the updates described above guarantee that both invariants are satisfied (note that the last item above is needed only to guarantee Invariant 1 for configurations of Rule 7, since this is the only configuration where two white vertices must be adjacent). We are left with the time complexity analysis. Observe that the expected time of the algorithm is bounded by a function which is linear in the total number of insertions to Q 3+ and Q s . (A lookup, insert or delete opertion in a hash table works in O(1) expected time and this is the only source of randomness in the running time.) The number of insertions to Q 3+ and Q s is linear in the size of the input graph added to the number of applications of the rules. Since each application decreases the number of vertices, there are at most n of them. Hence the total expected time is bounded by O(n). Note that we can turn it to O(n log n) deterministic time by replacing hash tables by balanced binary search trees.

Concluding remarks and further research

We have shown a kernel of 13k vertices for Planar Feedback Vertex Set. Our main contribution was applying the region decomposition technique in a new way. It would be interesting to see more applications of the region decomposition technique in problems in which it was not used before.

An obvious open problem is improving the kernel size even further. In particular, it would be nice to break the psychological barrier or single digit kernel, i.e., to get a 9k-kernel. We suppose that if this is possible, it would require finding a number of new, very specialized reduction rules.

Figure 2 :

 2 Figure 2: Reduction rules 8 and 9.

  and deg(v 2 ) = deg(u 1 ) = 3. Then contract the edge v 1 v 2 to a new vertex y and add an edge w 1 v 3 , as presented in Figure 2 (left).

Lemma 4 .

 4 Rule 8 is correct.

1 and decrease k by 1 . 6 .

 16 Lemma Rule 10 is correct.

Figure 3 :

 3 Figure 3: Configurations in lemmas 7 and 8.

  e., |N ({v 1 , . . . , v }) \ {u, v}| ≥ 3. If there is a feedback vertex set of size k in G, then |V (G)| ≤ (2 + 4)k -(4 + 6).

Figure 4 :

 4 Figure 4: A tight example. The big black vertices are solution vertices, the small gray ones are forest vertices. The zigzag edges represent paths of -1 forest vertices, each adjacent to the two available solution vertices. Asymptotically for larger cycles, we have 2 + 3 forest vertices for each solution vertex.

Figure 5 :

 5 Figure 5: Configuration from Lemma 9.

Figure 6 :

 6 Figure 6: Gadgets of rules 15, 16 and 17.

  [START_REF] Bodlaender | A linear kernel for planar feedback vertex set[END_REF] w 2 ∈ S Q .Then remove vertex w 1 and decrease k by one. Rule 14 If |N (w 2 ) ∩ V (P )| ≤ 2 Then remove vertex w 1 and decrease k by one. Rule 15 If every set S Q ∈ S satisfies at least one of the conditions (

  and 14 we see that S = S ∪ {w 1 } works. Now focus on the remaining rules. Let Y = {y} for rules 15 and 16, and Y = {y 1 , y 2 } for Rule 17. Let Q = G [N [Y ]]. It is easy to verify that for each of the three rules |V (Q )∩S| ≥ 2. If |V (Q )∩S| ≥ 3 then we see that S = S \V (Q )∪{w 1 , w 2 , x 1 } works. Hence we are left with the case |V (Q ) ∩ S| = 2. Assume there is a (u, v)-path in G -S . Then we put S = S \ V (Q ) ∪ {w 1 , w 2 }. Note that the equivalence classes of R Q-S,δ(Q) are {u, v}, {w 1 } and {w 2 }. Hence, by Lemma 3 (for A = G and B = G) S is a feedback vertex set of G, so (G, k) is a yes-instance, a contradiction.

  {y, v} the equivalence classes of R Q -S ,δ(Q) are {u} and {v, w 1 , w 2 }, or {v} and {u, w 1 , w 2 }, respectively. In the former case we put S = S \V (Q )∪S

  and in the latter oneS = S \ V (Q ) ∪ S (5) Q . By Lemma 3 (for A = G and B = G) S is a feedback vertex set G, so (G, k) is a yes-instance.Finally, consider Rule 17. By Lemma 18, S contains both a set |S

  then there are vertices a ∈ V (Q) and b ∈ B C \ V (Q) such that for some pair of white vertices x, y we have x, y ∈ N C (a) and x, y ∈ N C (b). Note also that in both cases there is at most one edge h C (b)u such that u ∈ {h C (x), h C (y)}. But it means that the homomorphic image of b must belong to S h C (x),h C (y) and since Q 3+ = ∅, there are only O(1) candidates for it. Then there are only O(1) candidates for other black vertices in the connected component of C[B C ] containing b. The claim follows. Now we can describe our algorithm.

Algorithm 1 :1 6 else 7 Invariant 1 Invariant 2

 16712 Kernelize(G, k) Initialize D 1 , D 2 , Q 3+ according to their definitions; 2 Initialize Q s with all vertices of G with at most four neighbors;3 while Q 3+ ∪ Q s = ∅ do 4 if Q 3+ = ∅ then 5Remove an element from Q 3+ and apply Rule 6;Remove a vertex from Q s and apply Lemma 21; 8 If a configuration is found, apply the corresponding rule;The correctness of Algorithm 1 follows from the following invariants. The information stored in D 1 , D 2 , Q 3+ is up to date. If a configuration C appears in G, then there is a vertex z ∈ Q s such that for some black vertex v ∈ V (C) we have h C (v) = z.

  so S A is not a feedback vertex set of A, a contradiction.Hence we know that C has vertices both inside and outside Q B . It follows that C can be divided into subpaths of two kinds: subpaths in Q B -S B and in

  Every vertex from I 2 belongs to a chain in CL 2 , C 2 -or C 3 + . (ii) Every chain in CL 2 ∪ C 2 -has at most two solution neighbors.

(iii) Every chain in C 3 + has at least three solution neighbors. (iv) Every chain in C 2 -is assigned to a different edge of inner forest F I . (v) Every chain in C 2 -∪ CL 2 has at most -1 vertices. (vi) Every chain in C 3 + has at most vertices. A solution graph H S . Let us introduce a new plane multigraph H S = (S, E S ). Since the vertices of H S are the solution vertices we call it a solution graph.

* A preliminary version (with a slightly weaker result) was presented at IPEC 2014, Wrocław, Poland. Work partially supported by the ANR Grant EGOS (2012-2015) 12 JS02 002 01 (MB) and by the National Science Centre of Poland, grant number UMO-2013/09/B/ST6/03136 (ŁK).

Then, for every j ∈ {b 1 , b 2 , . . . , b r } there is an edge xu j , for otherwise we can add it in the current plane embedding, contradicting the maximality of G. This means that every vertex in I f 3 + has at least three neighbors in {u 1 , u 2 , . . . , u d(f ) }.

We further define B as the plane graph obtained from A by (1) replacing every triple (u, x, v) where x ∈ L 2 , u, v ∈ S and uxv forms a path by a single edge, (2) removing vertices of V (CL 2 ), (3) contracting every chain from C 3 + into a single vertex, and (4) contracting every chain from C 2 -into a single edge. By (4) we mean that every maximal chain d = x 1 , . . . , x i of I 2 vertices which is contained in a chain from C 2 -, is replaced by the edge yz where y and z are the forest neighbors (in L 3 + ∪ I 3 + ) of x 1 and x i outside the chain d. Let us call the vertices of B that are not on the boundary of f as inner vertices.

Note that the set of inner vertices is in a bijection with

Moreover, I forms a tree, since F f is a tree. Also, each inner vertex has at least three neighbors in {u 1 , u 2 , . . . , u d(f ) }. We show that |I| ≤ d(f ) -2 by the induction on d(f ). When d(f ) = 2 the claim follows since each inner vertex has at least three neighbors on the boundary of f . Now assume d(f ) > 2. Let x be leaf in the tree I. Then the edges from x to the boundary of face f split F into at least three different faces. The subtree I -x lies in one of these faces, say face bounded by the cycle xu i u i+1 • • • u j x. We remove x and vertices u j+1 , . . . , u i-1 (there is at least one of them) and we add edge u i u j . The outer face of the resulting graph is of length at most d(f ) -1, so we can apply induction and the claim follows.

Lemma 16. For every face f in H S of length at least three,

Proof. We have

By Lemma 12(iv), |C f 2 -| is bounded by the number of edges of the inner forest

In the prior case, by (3) we get that

and the result then follows from Lemma 15. Hence it suffices to prove the claim when

Then the forest F f is a non-empty collection of paths, each with both endpoints in L 2 . Let c be such a path on p vertices x 1 , . . . , x p . Then x 1 ∈ L 2 and x 1 has exactly two neighbors u, v in S. Let i be the largest such that N ({x 1 , . . . , x i }) ∩ S = {u, v}. By definition, (x 1 , . . . , x i ) is a chain in CL f 2 . We infer that if i = p for every such path, then |V f F \ V (CL f 2 )| = 0 and the claim follows. Hence we can assume that i < p, i.e., x i+1 has a neighbor in S \ {u, v}. Then, by definition, (x 1 , . . . , x i+1 ) is a chain in C f 3 + . Since (x 1 , . . . , x i ) ∈ CL f 2 , we get |{x 1 , . . . , x i+1 } \ V (CL f 2 )| = 1. Hence,