Improved Kernels for Several Problems on Planar Graphs

Abstract

In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem. For the Induced Matching problem on planar graphs, based on Gallai-Edmonds structure, a kernel of size 26k is presented, which improves the current best result 28k. For the Parameterized Planar 4-Cycle Transversal problem, by partitioning the vertices in given instance into four parts and analyzing the size of each part independently, a kernel with at most $51k-22$ vertices is obtained, which improves the current best result 74k. Based on the kernelization process of the Parameterized Planar 4-Cycle Transversal problem, a kernel of size $51k-22$ can also be obtained for the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem, which improves the current best result 96k.

This work is supported by the National Natural Science Foundation of China under Grants (61420106009, 61232001, 61472449, 61672536).

1 Introduction

Given an instance (I, k) of a parameterized problem Q, the kernelization process is to transform (I, k) into a new instance $(I', k')$ in polynomial time such that (I, k) is a yes-instance of Q if and only if $(I', k')$ is a yes-instance of Q, where $k'\le k$, and $|I'|\le f(k)$ for some computable function f. In this paper, we study the kernelization of the Induced Matching problem on planar graphs, the Parameterized Planar 4-Cycle Transversal problem, and the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem.

Induced matching

In graph theory, a matching in a graph $G=(V, E)$ is a set of edges without common vertices. A matching M of G is an induced matching of G if no edge in $E-M$ has both endpoints contained in V(M) (V(M) is the set of vertices contained in M). The Induced Matching problem is to decide whether a given graph G has an induced matching of size at least k. The Induced Matching problem was introduced by Stockmeyer and Vazirani [29], and has attracted lots of attention. Duckworth et al. [9] proved that the Induced Matching problem on general graphs is NP-complete. The NP-hardness of the problem was also studied on many restricted graph classes, such as, the bipartite graphs with maximum degree three [23], planar bipartite graphs [9], 3-regular planar graphs [9], $C_4$-free bipartite graphs [23], chair-free graphs [19], line-graphs [19], and Hamiltonian graphs [19]. The Induced Matching problem is polynomial time solvable in many graph classes, such as, trees [11, 12], interval-filament graphs [16], AT-free graphs [16], circular arc graphs [16], chordal graphs [5], weakly chordal graphs [7], line-graphs of Hamiltonian graphs [19], polygon-circle graphs [6], $(P_5, D_m)$-free graphs [19, 24], $(P_k, K_{1, n})$-free graphs [19, 24], trapezoid graphs [12], interval-dimension graphs [12], and comparability graphs [12].

Duckworth et al. [9] proved that the Induced Matching problem is APX-complete on r-regular graphs ($r\ge 3$) and bipartite graphs with maximum degree three. Orlovich et al. [27] gave that in general graphs, the Induced Matching problem cannot be approximated within a factor of $n^{1/2-\varepsilon }$ for any $\varepsilon >0$. Chlebík and Chlebíková [8] proved that it is NP-hard to approximate the Induced Matching problem within factor of $r/2^{O(\sqrt{lnr})}$ for r-regular graphs. Duckworth et al. [9] gave an approximation algorithm for the problem on r-regular graphs ($r\ge 3$) with ratio $r-1$, and proposed a polynomial-time approximation scheme (PTAS) for the Induced Matching problem on planar graphs of maximum degree three. Gotthilf and Lewenstein [13] gave an approximation algorithm for the Induced Matching problem with ratio $0.75r+0.15$.

In this paper, we study the following problem.

Induced Matching problem on planar graphs: Given a planar graph $G=(V, E)$ and an integer k, find an induced matching of size at least k in G, or report that no such matching exists.

Moser and Thilikos [25] proved that the Induced Matching problem on general graph is W[1]-hard. It was pointed out in [26] that the Induced Matching problem is even W[1]-hard on bipartite graphs. Based on the kernelization methods in [1], Moser and Sikdar [26] gave a linear kernel for the Induced Matching problem on planar graphs. Kanj et al. [18] improved the above kernel result to 40k. Erman et al. [10] gave that every n-vertex twinless planar graph contains an induced matching of size $(n+9)/28$, and a kernel of size 28k was obtained, which is the current best result. A kernel of size $2k(1+d+d^2)$ was presented for the Induced Matching problem on degree-bounded graphs with maximum degree d by Moser and Sikdar [26].

In this paper, we study the Induced Matching problem on planar graphs. The key point to get the improved kernel is based on the analysis of Gallai-Edmonds decomposition structure. Several new reduction rules are presented, which results in a kernel of size 26k for the Induced Matching problem on planar graphs.

s-Cycle Transversal

The s-Cycle Transversal problem has been widely studied in extremal graph theory [2], graph coloring [35] and computational biology [28], which is to find a set S of edges of size at most k in a given graph G such that S intersects every cycle of length s in G, where s is a constant. When s is small, several related problems have also been studied, such as the chromatic numbers in graphs without 3-cycles [30] and 5-cycles [31], designing Low-Density Parity-Check (LDPC) codes [15] based on Taner graphs without 4-cycles.

The s-Cycle Transversal problem for any fixed $s\ge 3$ is known to be NP-complete on general graphs [34]. Brügmann et al. [4] showed that the s-Cycle Transversal problem remains NP-complete on planar graphs for $s = 3$. Xia and Zhang [32] proved that the s-Cycle Transversal problem is NP-complete on planar graphs for any fixed $s\ge 3$. Krivelevich [21] presented a 2-approximation algorithm for the 3-Cycle Transversal problem. Kortsarz et al. [20] showed that a $(2-\epsilon )$-approximation algorithm for 3-Cycle Transversal problem implies a $(2-\epsilon )$-approximation algorithm for Vertex Cover problem. Kortsarz et al. [20] presented a generalized $(s-1)$-approximation algorithm for s-Cycle Transversal problem for odd number s.

The s-Cycle Transversal and related problems have also been studied from parameterized complexity point of view, which are defined as follows.

Parameterized 4-Cycle Transversal: Given an undirected graph $G = (V, E)$ and an integer k, find a subset $E' \subseteq E$ with $|E'| \le k$ such that each 4-cycle in G contains at least one edge from $E'$, or report that no such subset exists.

Parameterized ($\le$ s)-Cycle Transversal: Given an undirected graph $G =(V, E)$, a constant s and an integer k, find a subset $E' \subseteq E$ with $|E'| \le k$ such that each ($\le$ s)-cycle in G contains at least one edge from $E'$, or report that no such subset exists.

Parameterized Planar 4-Cycle Transversal: Given a planar graph $G =(V, E)$ and an integer k, find a subset $E' \subseteq E$ with $|E'| \le k$ such that each 4-cycle in G contains at least one edge from $E'$, or report that no such subset exists.

A kernel with 6k vertices and a kernel with $11k\text {/}3$ vertices in general graphs and planar graphs for 3-Cycle Transversal problem were presented in [4], respectively. Xia and Zhang [32] gave that the Parameterized 4-Cycle Transversal problem and the Parameterized ($\le$4)-Cycle Transversal problem admit a kernel with $6k^{2}$ vertices on general graphs. By applying the region decomposition technique developed by Guo and Niedermeier [14], Xia and Zhang [32] obtained several kernelization results on planar graphs: a kernel with 74k vertices for Parameterized 4-Cycle Transversal problem, a kernel with 32k vertices for Parameterized ($\le$4)-Cycle Transversal and a kernel with 266k vertices for the Parameterized ($\le$5)-Cycle Transversal problem. Xia and Zhang [33] studied the kernelization of the Parameterized ($\le$ s)-Cycle Transversal problem, and obtained a kernel of size $36s^{3}k$ for $s > 5$.

In this paper, we study the kernelization of the Parameterized Planar 4-Cycle Transversal problem. We give several reduction rules and partition the vertices in given instance into four parts to bound the size of reduced instance. A kernel with at most $51k-22$ vertices is obtained for the Parameterized Planar 4-Cycle Transversal problem, which improves the current best result 74k. The kernelization process for the Parameterized Planar 4-Cycle Transversal problem can be applied to the kernelization of the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem, which is to decide whether k edge-disjoint 4-cycles can be found in a given planar graph G. We can get that the Parameterized Planar Edge-Disjoint 4-Cycle Packing problem admits a kernel of size $51k-22$, which improves the current best result given in [17].

2 Preliminaries

Given a graph $G=(V, E)$, for two vertices u, v in G, let uv denote the edge between u and v. For a vertex $v \in G$, let $N(v)=\{u|vu\in E\}$. For a vertex v in G, let deg(v) denote the degree of v. A vertex in G with degree d is called a degree-d vertex. For a subset $V'\subseteq V$, let $G - V'$ denote the graph obtained by removing the vertices in $V'$ and all its incident edges from G. For a subset $E'\subseteq E(G)$, let $G - E'$ denote the graph obtained by deleting all edges in E from G. Assume that all paths discussed in this paper are simple. For two sets A, B, let $A\backslash B$ denote $A-B$. A 4-cycle in G is a cycle in G with four vertices and four edges. An edge subset S is called a 4-Cycle Transversal set of G if $G \setminus S$ is 4-cycle free. For any cycle C in G, let E(C) be the set of edges contained in C.

For two vertices u, v in G, if u and v have the same neighborhood, i.e., $N(u)=N(v)$, then u, v are called twin-vertices. A graph G is called a twinless graph if no twin-vertices are contained in G. For a subset $V'$ of V, the subgraph induced by $V'$ is denoted by $G[V']$. For a set S of edges of G, let V(S) denote the set of vertices contained in S. For a set M of edges of G, if no two edges in M have common vertices, then M is a matching of G, all the vertices in M are called matched vertices, and the vertices in $V\backslash V(M)$ are called unmatched vertices. The size of a matching M is the number of edges in M, denoted by |M|. A maximum matching is a matching that contains the largest possible number of edges. A matching is a perfect matching if all the vertices in graph are matched vertices. For a set S of edges of G, S is an induced matching of G if S satisfies the following properties: (1) S is a matching of G; (2) no edge in $E\backslash S$ has both endpoints contained in V(S). For an induced matching S of G, the size of S is the number of edges contained in S, denoted by |S|. For a graph G, the independence number of G is the size of the maximum independent set of G.

Given a graph $G=(V,\,E)$, a 4-cycle packing $\mathcal{P} = \{C_{1},\,C_{2},\,\ldots \,,C_{t}\}$ of size t is a collection of t edge-disjoint 4-cycles, i.e., each element $C_{i}\in \mathcal{P}$ is a 4-cycle and $E(C_{i}) \cap E(C_{j})=\emptyset$ for any two different 4-cycles $C_{i},\,C_{j}\in \mathcal{P}$. A 4-cycle packing is maximal if it is not properly contained in any strictly larger 4-cycle packing in G. The set of vertices in 4-cycles in $\mathcal P$ is denoted by $V(\mathcal P)$.

3 Improved Kernel for the Induced Matching Problem on Planar Graphs

Given an instance (G, k) of the Induced Matching problem on planar graphs, we first give several reduction rules for the problem.

Rule 3.1

[26]. For a vertex v in G with degree zero, delete v from G.

Rule 3.2

[26]. For a vertex v in G, if v contains at least two degree-1 neighbors, denoted by $\{u_1, u_2, \cdots , u_i\}$ ($i \ge 2$), then delete arbitrarily $i-1$ vertices from $\{u_1, u_2, \cdots , u_i\}$.

Rule 3.3

[26]. For two vertices u, v with $|N(u)\cap N(v)|\ge 2$, if $N(u)\cap N(v)$ contains at least two degree-2 vertices, denoted by $\{w_1, w_2, \cdots , w_j\}$ ($j \ge 2$), then delete arbitrarily $j-1$ vertices from $\{w_1, w_2, \cdots , w_j\}$.

Rule 3.4

For any two twin-vertices u, v in G, delete one of $\{u, v\}$.

It is easy to see that if the induced matching contains vertex from $\{u, v\}$, then only one of $\{u, v\}$ is contained in the induced matching, and any one of $\{u, v\}$ can be in the induced matching.

Rule 3.5

For any two vertices u, v in G, if there is a degree-2 vertex w in $N(u)\cap N(v)$, u has a degree-1 neighbor x, and v has a degree-1 neighbor y, then vertex w can be deleted.

Lemma 1

Rule 3.5 is correct and can be applied in $O(n^3)$ time.

Proof

Assume that (G, k) is an instance of the Induced Matching problem on planar graphs. We prove this lemma based on the following cases.

(1) no edge from $\{[u, w], [u, x], [v, w], [v, y]\}$ is contained in any induced matching of size at least k of G.

Assume that S is an induced matching of size k of G without containing any edge from $\{[u, w], [u, x], [v, w], [v, y]\}$. By deleting vertex w, S is still an induced matching of size k in $G[V\backslash \{w\}]$.

(2) one edge from $\{[u, w], [v, w]\}$ is contained in an induced matching of size at least k in G.

Without loss of generality, assume that edge [v, w] is contained in an induced matching S of size k in G. Let $S'=(S\backslash \{[v, w]\})\cup \{[v, y]\}$. It is easy to see that $S'$ is an induced matching of size k in G.

This reduction rule can be executed in the following way: for each possible w in G, check any two vertices u, v in N(w), and decide whether u, v have degree-1 vertices in their neighbors, respectively. It is easy to see that Rule 3.5 can be applied in $O(n^3)$ time.    $\square$

Rule 3.6

For any three vertices $v_1, v_2, v_3$ in G, if there is degree-3 vertex u in $N(v_1)\cap N(v_2)\cap N(v_3)$, $v_1$ has a degree-1 neighbor x, $v_2$ has a degree-1 neighbor y, and $v_3$ has a degree-1 neighbor z, then vertex u can be deleted.

Lemma 2

Rule 3.6 is correct and can be applied in $O(n^4)$ time.

Proof

Assume that (G, k) is an instance of the Induced Matching problem on planar graphs. We prove this lemma based on the following cases.

(1) no edge from $\{[u, v_1], [u, v_2], [u, v_3]\}$ is contained in any induced matching of size at least k of G.

Assume that S is an induced matching of size k of G without containing any edge from $\{[u, v_1], [u, v_2], [u, v_3]\}$. By deleting vertex u, S is still an induced matching of size k in $G[V\backslash \{u\}]$.

(2) one edge from $\{[u, v_1], [u, v_2], [u, v_3]\}$ is contained in an induced matching of size at least k in G.

Without loss of generality, assume that edge $[u, v_1]$ is contained in an induced matching S of size k in G. Let $S'=(S\backslash \{[u, v_1]\})\cup \{[v_1, x]\}$. It is easy to see that $S'$ is an induced matching of size k in G.

This reduction rule can be executed in the following way: for each possible u in G, check any three vertices $v_1, v_2, v_3$ in N(w), and decide whether $v_1, v_2, v_3$ have degree-1 vertices in their neighbors, respectively. It is easy to see that Rule 3.6 can be applied in $O(n^4)$ time.   $\square$

We first introduce the terminologies related to Gallai-Edmonds structure [22].

Given a graph G, if for each vertex v in G, $G\backslash \{v\}$ has a perfect matching, then G is called a factor-critical graph. For a subset $V'$ of vertices in G, let $N(V')$ denote all the vertices of G which are adjacent to at least one vertex in $V'$. For a matching M in G, M is called a near-perfect matching of G if there is exactly one unmatched vertex in G.

Theorem 1

(The Gallai-Edmonds Structure Theorem) [22]. For a given graph G, let D be the set of vertices which are not covered by at least one maximum matching of G, let A be the set of vertices in $V\backslash D$ which are adjacent to at least one vertex in D, and let $C=V\backslash (A\cup D)$. Then,

• (a) the components of the subgraph induced by D are factor-critical,

• (b) the subgraph induced by C has a perfect matching,

• (c) if M is any maximum matching of G, it contains a near-perfect matching of each component of G[D], a perfect matching of each component of G[C] and matches all vertices of A with vertices in distinct components of G[D],

• (d) the size of the maximum matching is $1/2(|V|-c(G[D])+|A|)$, where c(G[D]) is the number of components in G[D].

For simplicity, a Gallai-Edmonds structure of graph G is denoted by (C, A, D).

Lemma 3

[22]. For a given graph $G=(V, E)$, a Gallai-Edmonds structure (C, A, D) of G can be obtained in polynomial time.

The relationship between maximum matching and induced matching can be obtained as follows.

Lemma 4

[18]. Let $\mathcal G$ be a minor-closed family of graphs and let c be a constant such that any graph in $\mathcal G$ is c-colorable. Moreover, let G be a graph from $\mathcal G$ and let M be a matching in G. Then G contains an induced matching of size at least $|M|\text {/}c$.

For an instance (G, k) of the Induced Matching problem on planar graphs, apply Rules 3.1–3.6 whenever possible on G. Let $(G'=(V', E'), k')$ be the reduced instance such that no rule is applicable on $G'$.

Theorem 2

The Induced Matching problem on planar graphs admits a kernel of size 26k.

Proof

For a Gallai-Edmonds structure (C, A, D) of $G'$, the components in $G'[D]$ are divided into two parts S, T such that T contains the set of components, each of which has at least three vertices, and S contains the set of isolated vertices in $G'[D]$. Let $T_{2i+1}$ ($i\ge 1$) be a subset of T such that each component in $T_{2i+1}$ has $2i+1$ vertices. Assume that $T=\bigcup _{i=1}^hT_{2i+1}$. Let $S_1=\{u|u\in S, deg(u)=1\}$, $S_2=\{u|u\in S, deg(u)=2\}$, and $S_3=\{u|u\in S, deg(u)\ge 3\}$. Since Rule 3.4 is not applicable on $G'$, $G'$ contains no twin-vertices. Therefore, in the subgraph induced by the vertices in $A\cup D$, by Euler formula, $|S_2|\le 3|A|-6$, and $|S_3|\le 2|A|-4$. We discuss the size of S by the following cases.

• (1) $0\le |S_1|< |A|/2$.

  Under this case, we can get that:

  $$\begin{aligned} |S|= & {} |S_1|+|S_2|+|S_3| \\\le & {} |S_1|+3|A|-6+2|A|-4 \\\le & {} |S_1|+5|A|-10\\< & {} 5.5|A|-10 \end{aligned}$$

• (2) $|A|/2\le |S_1|\le |A|$.

  By Rule 3.5, if there exists a degree-2 vertex w in common neighbors of u, v and both u, v have degree-1 neighbors, then vertex w can be deleted. Therefore, if $|A|/2\le |S_1|\le |A|$, then the number of degree-2 vertices in $S_2$ is bounded by $3|A|-6-(|S_1|-|A|/2)$. Then, we can get that

  $$\begin{aligned} |S|= & {} |S_1|+|S_2|+|S_3| \\\le & {} |S_1|+3|A|-6-(|S_1|-|A|/2)+2|A|-4 \\\le & {} 5.5|A|-10 \end{aligned}$$

By the above two cases, we can get that $|S|\le 5.5|A|-10$.

For a subset $T_{2i+1}$ of T and for a maximum matching M in $G'$, at least i edges of $T_{2i+1}$ can be added into M. Therefore, we can get that

$$\begin{aligned} \frac{|M|}{|V'|}\ge & {} \frac{|A|+\sum _{i=1}^h i |T_{2i+1}|+1/2|C|}{|A|+5.5|A|-10+\sum _{i=1}^h (2i+1)|T_{2i+1}|+|C|}\\> & {} \frac{1}{6.5} \end{aligned}$$

Then, $|V'|< 6.5 |M|$. Let I be any induced matching of size k in $G'$. By Lemma 4 and the Four-color theorem of planar graphs, $|M|\le 4|I|$. Therefore, $|V'|< 6.5\cdot 4 |I|\le 26k$.    $\square$

4 Improved Kernel for the Parameterized Planar 4-Cycle Transversal Problem

For a given instance $(G=(V, E), k)$ of the Parameterized Planar 4-Cycle Transversal problem, we firstly find a maximal 4-cycle packing $\mathcal P$ in G, and let $Q=V-V(\mathcal{P})$. We can get that the size of $V(\mathcal P)$ is at most 4k, and Q contains no 4-cycle. The remaining task is to bound the size of Q. We first give several reduction rules.

Rule 4.1

If there exists an edge $e\in E$ which is not contained in any 4-cycle, then delete e from G; if there exists a vertex v in G not contained in any cycle, then delete v from G.

It is easy to see that Rule 4.1 is safe and can be executed in polynomial time. For any vertex v in G and any cycle C in $\mathcal P$, if v is connected to at least one vertex in C, then we call v is adjacent to C. For each cycle $C \in \mathcal P$, let Q(C) denote the set of vertices in Q that are adjacent to C.

Rule 4.2

If there is a 4-cycle $C \in \mathcal P$ with $V'$ = $Q(C)\cup V(C)$ such that $G[V']$ contains at least two edge-disjoint 3-cycles, then replace C by these 4-cycles in $\mathcal P$.

Rule 4.3

If there are two 4-cycles $C_1, C_2 \in \mathcal P$ with $V''$ = $Q(C_1)\cup V(C_1)\cup Q(C_2)\cup V(C_2)$ such that $G[V'']$ contains at least three edge-disjoint 4-cycles, then replace $C_1, C_2$ in $\mathcal P$ by these 4-cycles in $\mathcal P$.

Each execution of Rule 4.2 and Rule 4.3 can be done in polynomial time, and increases the number of 4-cycles in $\mathcal P$ by at least 1.

For a given instance (G, k) of the Parameterized Planar 4-Cycle Transversal problem, Rule 4.3 is applied when Rule 4.2 is not applicable on graph G. Note that after each application of Rule 4.3, the updated 4-cycle packing $\mathcal P$ is still maximal. For simplicity, a maximal 4-cycle packing $\mathcal P$ is called a $proper$ 4-cycle packing if neither Rule 4.2 nor Rule 4.3 is applicable to update $\mathcal P$.

In the following, we assume that $\mathcal P$ is a proper 4-cycle packing obtained by applying Rules 4.1–4.3 exhaustively, and let $Q=V-V(\mathcal{P})$. We now discuss the properties of the edges in G[Q]. For an edge $e=uv$ in G[Q], if there exists a cycle C in $\mathcal P$ such that u, v with two adjacent vertices in C form a 4-cycle, then edge uv is called a single edge in G[Q], and we say e is adjacent to cycle C.

Lemma 5

Let C be an arbitrary 4-cycle in $\mathcal P$, and let R be the set of vertex-disjoint single edges in G[Q] adjacent to C. If $|R|\ge 2$, then all the single edges in R must be adjacent to a unique edge in C.

For a 4-cycle C in G, if only one edge of C is shared with other 4-cycles in G, then C is called a $dangling$ cycle in G.

Rule 4.4

For a dangling 4-cycle C in G, all the edges in C can be deleted from G, and $k=k-1$.

Let (G, k) be the reduced instance of the Parameterized Planar 4-Cycle Transversal problem by exhaustively applying reduction Rules 4.1–4.4. We now analyze the size of G. Assume that $\mathcal P$ is a proper 4-cycle packing in G, and let $Q=V-V(\mathcal{P})$. We divide the vertices in Q into the following parts: $Q_{1} = \{v \in Q | |N(v) \cap V(\mathcal{P}) | = 1\}$, $Q_{2} = \{v \in Q | |N(v) \cap V(\mathcal{P}) | = 2\}$, $Q_{3} = \{v \in Q | |N(v) \cap V(\mathcal{P}) |\ge 3\}$, $Q_{0} = Q\setminus (Q_{1}\cup Q_{2}\cup Q_{3})$.

Since $\mathcal P$ is a proper 4-cycle packing in G and reduction Rule 4.1 is not applicable on G, we can get that $Q_{0} = \emptyset$. We now bound the size of $Q_3$.

Lemma 6

$|Q_{3}| \le max\{0,2|V(\mathcal{P})| - 4\}$.

In the following, we will bound the size of $Q_1$ and $Q_2$. For any two distinct vertices u, v in $\mathcal P$, let $Q_{2}(uv)=\{w \in Q_{2} | N(w)\cap V(\mathcal{P}) =\{u,\,v\}\}$. Assume that T is the set of all non-empty subsets $Q_{2}(uv)$ for each distinct vertices u, v in $\mathcal P$.

Lemma 7

Each subset in T has size one.

Lemma 8

$|T|\le 3|V(\mathcal{P})| - 6$.

In graph G, a path with three vertices and two edges is called a 3-path. For any two 3-paths $p_1=(x_1, x_2, x_3)$ and $p_2=(y_1, y_2, y_3)$, $p_1$ is called connected to $p_2$ if $p_1, p_2$ satisfies the following properties: for any vertex $x_i$ ($1\le i\le 3)$, there exists a unique vertex $y_j$ in $p_2$ ($1\le j\le 3)$ such that $x_iy_j$ is an edge in G.

Lemma 9

For any arbitrary 4-cycle $C \in \mathcal P$, there exists at most one 3-path in G[Q] connected to a 3-path of C.

For a single edge e in G[Q], we first claim that the two endpoints of edge $e=uv$ are not both from $Q_1$. Assume that u, v are both from $Q_1$, and are connected to an edge $e'=u'v'$ of 4-cycle C in $\mathcal P$. It is easy to see that 4-cycle constructed by vertices $u, v, u', v'$ is a dangling 4-cycle, which can be handled by Rule 4.4, a contradiction. Thus, we can get that for each single edge e with one vertex from $Q_1$ in G[Q], e is adjacent to the unique edge in a 4-cycle of $\mathcal P$, and the other endpoints of e must be from $Q_{2} \cup Q_{3}$.

Suppose that $e_{1}=\{a,\,b\}$ and $e_{2}=\{c,\,d\}$ are two single edges in G[Q] which are adjacent to the same edge $e=\{u,\,v\}$ of a 4-cycle in $\mathcal P$, where a, c are the vertices in $Q_{2} \cup Q_{3}$, b, d are the vertices in $Q_{1}$. Assume that a, c are adjacent to u, and b, d are adjacent to v. We first claim that $e_{1}$ and $e_{2}$ cannot share a vertex. Assume that $e_{1}$ and $e_{2}$ share a vertex. If $a=c$, then a 4-cycle $\{a,\,b,\,v,\,d\}$ can be found, which is edge-disjoint with the 4-cycles in $\mathcal P$, contradicting with the maximality of $\mathcal P$. Other cases of sharing vertices of $e_1$ and $e_2$ can be similarly discussed.

Assume that e is a single edge in G[Q] which is adjacent to an edge $e'$ of a 4-cycle in $\mathcal P$. Let u be one vertex in e from $Q_1$, and let v be the other endpoint of e which is from $Q_{2} \cup Q_{3}$. It is not hard to see that vertex u can be adjacent to exactly one vertex in $Q_{2} \cup Q_{3}$, and vertex v can be adjacent to exactly one vertex of $Q_{1}$. Otherwise, one of reduction rules can be applied again. We now bound the number of vertices in $Q_1$.

Lemma 10

The number of vertices in $Q_{1}$ is at most $6|V(\mathcal{P})|+3k-12$.

Proof

It is not hard to get that the vertices in $Q_{1}$ might form single edges and 3-paths. By Lemma 9, we get that for any arbitrary 4-cycle $C \in \mathcal P$, there exists at most one 3-path in G[Q] that is connected to 3-path of C. Assume that $P'$ is a 3-path in G[Q] that is connected to 3-path of C. The vertices in $P'$ might be from $Q_{1}$ and $Q_{2} \cup Q_{3}$. The vertices in the 3-paths whose vertices are all from $Q_{1}$ are bounded by 3k. Thus, the remaining task is to consider the vertices in 3-paths that contain vertices from $Q_{2} \cup Q_{3}$, and the vertices in the single edges that contain vertices from $Q_{2} \cup Q_{3}$.

Let $Q'_2$ be a subset of $Q_2$ such that each vertex in $Q'_2$ has at least one neighbor in $Q_1$, and let $Q'_3$ be a subset of $Q_3$ such that each vertex in $Q'_3$ has at least one neighbor in $Q_1$. In order to bound the number of vertices in $Q_1$, we first construct an auxiliary graph H as follows: (1) add vertices $Q_{1} \cup Q'_{2} \cup Q'_{3} \cup V(\mathcal{P})$ into H; (2) for a vertex u in $Q_1$ and a vertex v in $Q'_{2} \cup Q'_{3} \cup V(\mathcal{P})$, if there exists an edge between u and v in G, then add edge uv into H. Based on the auxiliary graph H, another auxiliary graph $H'$ can be constructed in the following way: (1) add vertices $Q'_{2}\cup Q'_{3}\cup V(\mathcal{P})$ into $H'$; (2) for any vertex $u \in Q'_{2} \cup Q'_{3}$ and any vertex $v \in V(\mathcal{P})$, if there exists a vertex w in $Q_1$ such that uw and wv are the edges in H, then add edge uv into $H'$. It is easy to see that $H'$ is a bipartite planar graph and triangle-free, and each vertex in $Q'_{2} \cup Q'_{3}$ has degree at least three. By the above discussion, for any vertex u in $Q'_{2} \cup Q'_{3}$ and any vertex v in $V(\mathcal P)$, u and v can have at most one common neighbor from $Q_{1}$ in G. Thus, no two vertices in $H'$ have multiple edges. The number of vertices in $Q_{1}$ is exactly the number of edges in $H'$. The number of vertices contained in $Q'_{2} \cup Q'_{3}$ is bounded by $2|V(\mathcal{P})|-4$. Therefore, the number of edges in $H'$ is bounded by $2((2|V{(\mathcal{P})}|-4)+|V{(\mathcal P)}|)-4$ = $6|V(\mathcal{P})|-12$. Thus, the total number of vertices in $Q_{1}$ is at most $6|V(\mathcal{P})|+3k-12$.    $\square$

For an isolated vertex v in G[Q], if v is connected to the vertices of C, such as a, c or b, d, then it is called vertex v is connected to 4-cycle C.

Lemma 11

For any arbitrary 4-cycle $C \in \mathcal P$, if an isolated vertex v in G[Q] is connected to C, then no single edge or 3-path in G[Q] can be connected to C. Similarly, if a single edge in G[Q] is connected to C, then no isolated vertex or 3-path in G[Q] can be connected to C; if a 3-path in G[Q] is connected to C, then no isolated vertex or single edge can be connected to C.

Theorem 3

The Parameterized Planar 4-Cycle Transversal problem admits a kernel of at most $51k-22$ vertices.

Proof

For the reduced instance (G, k) of the Parameterized Planar 4-Cycle Transversal problem, the size of G is bounded by $|V(\mathcal{P})|+|Q_1|+|Q_2|+|Q_3|$. The size of $V(\mathcal{P})$ is bounded by 4k. By Lemma 8, the number of vertices in $Q_2$ is bounded by $3|V(\mathcal{P})|-6$, and by Lemma 6, the number of vertices in $Q_3$ is bounded by $2|V(\mathcal{P})|-4$. By Lemma 10, the number of vertices in $Q_1$ is bounded by $6|V(\mathcal{P})|+3k-12$. Thus, the total number of vertices in the reduced graph G is $|V(G)|=|V(\mathcal{P})|+|Q_{1}|+|Q_{2}|+|Q_{3}| \le |V(\mathcal{P})|+(6|V(\mathcal{P})|+3k-12)+(3|V(\mathcal{P})|-6)+(2|V(\mathcal{P})|-4)\le 51k-22$.   $\square$

The kernelization process for the Parameterized Planar 4-Cycle Transversal problem can be applied to the kernelization of the Parameterized Planar Edge-Disjoint 4-Cycle Packing.

Corollary 1

The Parameterized Planar Edge-Disjoint 4-Cycle Packing problem admits a kernel of at most $51k-22$ vertices.