On Polynomial Kernelization of $\mathcal {H}$-free Edge Deletion

Abstract

For a set $\mathcal {H}$ of graphs, the $\mathcal {H}$-free Edge Deletion problem is to decide whether there exist at most k edges in the input graph, for some $k\in \mathbb {N}$, whose deletion results in a graph without an induced copy of any of the graphs in $\mathcal {H}$ . The problem is known to be fixed-parameter tractable if $\mathcal {H}$ is of finite cardinality. In this paper, we present a polynomial kernel for this problem for any fixed finite set $\mathcal {H}$ of connected graphs for the case where the input graphs are of bounded degree. We use a single kernelization rule which deletes vertices ‘far away’ from the induced copies of every $H\in \mathcal {H}$ in the input graph. With a slightly modified kernelization rule, we obtain polynomial kernels for $\mathcal {H}$-free Edge Deletion under the following three settings:

• $\mathcal {H}$ contains $K_{1,s}$ and $K_t$;

• $\mathcal {H}$ contains $K_{1,s}$ and the input graphs are $K_t$-free;

• $\mathcal {H}$ contains $K_{t}$ and the input graphs are $K_{1,s}$-free;

where $s>1$ and $t>2$ are any fixed integers. Our result provides the first polynomial kernels for Claw-free Edge Deletion and Line Edge Deletion for $K_t$-free input graphs which are known to be NP-complete even for $K_4$-free graphs.

1 Introduction

For a graph property ${\varPi }$, the ${\varPi }$ Edge Deletion problem is to decide whether there exist at most k edges such that deleting them from the input graph results in a graph with property ${\varPi }$. Numerous studies have been done on edge deletion problems from 1970s onward dealing with various aspects such as hardness  [2, 6, 15, 18, 28, 31, 34–37], polynomial-time algorithms [22, 31, 34], approximability [1, 31, 34], fixed-parameter tractability [7, 17, 19, 29], polynomial problem kernels [5, 14, 20, 21] and incompressibility [8, 9, 24].

Lewis and Yannakakis [26] proved that the corresponding vertex deletion problem, ${\varPi }$ Vertex Deletion is NP-complete if ${\varPi }$ is non-trivial and hereditary on induced subgraphs. Such a generalized result is not yet found for ${\varPi }$ Edge Deletion. Nevertheless, there is a recent result that, if ${\varPi }$ is the property H-free (without any induced copies of a graph H), then the problem is NP-complete if and only if H has at least two edges [2]. By a result of Cai [7], the ${\varPi }$ Edge Deletion problem is fixed-parameter tractable for any hereditary property ${\varPi }$ that is characterized by a finite set of forbidden induced subgraphs. We observe that polynomial problem kernels have been found only for a few parameterized ${\varPi }$ Edge Deletion problems.

In this paper, we study a subset of ${\varPi }$ Edge Deletion problems known as $\mathcal {H}$-free Edge Deletion problems where $\mathcal {H}$ is a set of graphs. The objective is to decide whether there exist at most k edges, for some $k\in \mathbb {N}$, in the input graph such that deleting them results in a graph without an induced copy of any of the graphs in $\mathcal {H}$. In the natural parameterization of this problem, the parameter is k. In this paper, we give a polynomial problem kernel for the parameterized version of $\mathcal {H}$-free Edge Deletion where $\mathcal {H}$ is any fixed finite set of connected graphs and when the input graphs are of bounded-degree. In this context, we note that Triangle-free Edge Deletion [5], Cluster ( $P_3$ -free) Edge Deletion [23] and Trivially Perfect ( $\{C_4,P_4\}$ -free) Edge Deletion [14] are NP-complete even for bounded-degree input graphs. We also note that, under the assumption NP$\not \subseteq$coNP/poly, there exist no polynomial problem kernels for the H-free Edge Deletion problems when H is 3-connected but not complete, or when H is a path or cycle of at least 4 edges [8]. When the input graph has maximum degree at most ${\varDelta }$ and the maximum diameter of graphs in $\mathcal {H}$ is D, then the number of vertices in the kernel we obtain is at most $2{\varDelta }^{2D+1}\cdot k^{pD+1}$ where $p=\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}{\varDelta }$ (asymptotically, $p=O({\varDelta }\log {\varDelta })$). Our kernelization consists of a single rule which removes vertices of the input graph G that are ‘far enough’ from all induced $H\in \mathcal {H}$ in G. We are able to relax the restriction on the input graph such that $\mathcal {H}$-free Edge Deletion admits polynomial kernelization even if high degree vertices are present ‘far away’ from the initial induced obstructions.

We slightly modify this technique to obtain polynomial kernels for $\mathcal {H}$-free Edge Deletion under the following three settings:

• $\mathcal {H}$ contains $K_{1,s}$ and $K_t$;

• $\mathcal {H}$ contains $K_{1,s}$ and the input graphs are $K_t$-free;

• $\mathcal {H}$ contains $K_{t}$ and the input graphs are $K_{1,s}$-free;

where $s>1$ and $t>2$ are any fixed integers. The main observation we use for this is that $\{K_{1,s}, K_t\}$-free graphs are bounded-degree. We note that Yannakakis’ result [37] saying that Line Edge Deletion is NP-complete implies the NP-completeness of $\{K_{1,3}\}$-free Edge Deletion on $K_4$-free graphs and $\{K_{1,3},K_4\}$-free Edge Deletion. The number of vertices in the kernel we obtain in all these three settings is at most $8d^{3D+1}\cdot k^{pD+1}$ where $d=R(s,t-1)-1$, $R(s,t-1)$ is the Ramsey number and $p=\log _{\frac{2d}{2d-1}}d$. As a corollary of our result, we obtain the first polynomial kernels for Claw ( $K_{1,3}$ ) -free Edge Deletion and Line Edge Deletion when the input graphs are $K_t$-free for any fixed $t>2$. The existence of a polynomial kernel for Claw-free Edge Deletion and Line Edge Deletion were raised as open problems in [8, 11, 12] and the former is considered as ‘one of the most tantalizing questions’ [12] and a ‘very challenging case’ [8] in this area of research. We note that for $s>9$, there is an incompressibility result for $K_{1,s}$-free Edge Deletion for general graphs [9].

1.1 Related Work

Here, we give an overview of various results on edge deletion problems.

NP-hardness: It has been proved that ${\varPi }$ Edge Deletion problems are NP-hard if ${\varPi }$ is one of the following properties: bipartite [16], without cycle of any fixed length $l\ge 3$, connected with maximum degree r for every fixed $r\ge 2$, outerplanar, line graph, comparability [37], planar [27], series-parallel [3], $P_l$-free for any fixed $l\ge 3$ [15], threshold [28], interval, unit-interval [18], cograph, cluster [30], chordal, chain, perfect, split, AT-free [31], trivially perfect [35], biclique [32], no subgraph isomorphic to a fixed non-bipartite graph [1] and H-free, for any fixed H with at least two edges [2].

Polynomial-Time Algorithms: It is proved [22] that Bipartite Edge Deletion is polynomial-time solvable on planar graphs. There are polynomial-time algorithms for chain, split and threshold edge deletion problems on bounded-degree graphs [31]. 2-Cluster Edge Deletion is polynomial-time solvable [34].

Approximability: If ${\varPi }$ is a graph property characterized by a finite set of forbidden induced subgraphs, then ${\varPi }$ Edge Deletion can be approximated for bounded-degree graphs within a factor of $t{\varDelta }$ where t is the maximum number of vertices in each forbidden subgraph and ${\varDelta }$ is the maximum degree of the input graph [31]. For any fixed $\epsilon > 0$ and any monotone property (i.e., property closed under removal of vertices and edges) $\mathcal {P}$, there is a deterministic algorithm, which given a graph $G=(V, E)$ of size n, approximates $E_{\mathcal {P}}'(G)$ (i.e., the minimum number of edge deletions needed in order to turn G into a graph satisfying property $\mathcal {P}$) in linear time $O(|V|+|E|)$ to within an additive error of $\epsilon n^2$ [1]. If there is a bipartite graph that does not satisfy $\mathcal {P}$, then there is a $\delta > 0$ for which it is possible to approximate $E_{\mathcal {P}}'$ to within an additive error of $n^{2-\delta }$ in polynomial time [1]. If all bipartite graphs satisfy $\mathcal {P}$, then for any $\delta > 0$ it is NP-hard to approximate $E_{\mathcal {P}}'$ to within an additive error of $n^{2-\delta }$ [1]. It is proved [34] that there is some constant $\epsilon > 0$ such that it is NP-hard to approximate Cluster Edge Deletion to within a factor of $1+\epsilon$.

Fixed-parameter Tractability and Kernelization: Cai proved in [7] that the parameterized ${\varPi }$ Edge Deletion problem is fixed-parameter tractable if ${\varPi }$ is a hereditary property characterized by a finite set of forbidden induced subgraphs. Hence $\mathcal {H}$-free Edge Deletion is fixed-parameter tractable for any finite set of graphs $\mathcal {H}$. Polynomial problem kernels are known for chain, split, threshold, co-trivially perfect [21], cluster [19], triangle-free [5], cograph [20], diamond-free [33], and trivially perfect [14] edge deletions. It has been proved [24] that, unless NP$\subseteq$coNP/poly, H -free Edge Deletion admits no polynomial kernel if H is $K_1 \times \ (2K_1\cup 2K_2)$, where $\times$ is the standard join operation. This was the first H-free Edge Deletion problem proved to be incompressible. It is proved in [8] that for 3-connected H, H-free Edge Deletion admits no polynomial kernel if and only if H is not a complete graph, under the assumption NP$\not \subseteq$coNP/poly. Under the same assumption, it is proved [8] that for H being a path or cycle, H-free Edge Deletion admits no polynomial kernel if and only if H has at least four edges, and $K_{1,s}$ -free Edge Deletion admits no polynomial kernel if $s>9$ [9].

2 Preliminaries and Basic Results

We consider only simple graphs. For a set $\mathcal {H}$ of graphs, a graph G is $\mathcal {H}$-free if there is no induced copy of any $H\in \mathcal {H}$ in G. For $V'\subseteq V(G)$, $G - V'$ denotes the graph $(V(G)\setminus V', E(G)\setminus E')$ where $E'\subseteq E(G)$ is the set of edges incident to vertices in $V'$. Similarly, for $E'\subseteq E(G)$, $G - E'$ denotes the graph $(V(G), E(G)\setminus E')$. For an edge set $E'\subseteq E(G)$, $V_{E'}$ denotes the set of vertices incident to the edges in $E'$. For a vertex set $V'\subseteq V(G)$, the closed neighbourhood of $V'$ is $N_G[V']=\{v: v\in V'\ \text {or}\ (u,v)\in E(G)\ \text {for some}\ u\in V'\}$. In a graph G, distance from a vertex v to a set of vertices $V'$ is the shortest among the distances from v to the vertices in $V'$.

A parameterized problem is fixed-parameter tractable (FPT) if there exists an algorithm to solve it in time $O\left( f(k)\cdot n^c\right)$ where f is a computable function, n is the input size, c is a constant and k is the parameter. The idea is to solve the problem efficiently for small parameter values. A related notion is polynomial kernelization where the parameterized problem instance is reduced in polynomial (in $n+k$) time to a polynomial (in k) sized instance of the same problem called problem kernel such that the original instance is a yes-instance if and only if the problem kernel is a yes-instance. We refer to [10] for an exhaustive treatment on these topics. A kernelization rule is safe if the answer to the problem instance does not change after the application of the rule. In this paper, we consider $\mathcal {H}$-free Edge Deletion, which is defined as given below.

2.1 Basic Results

We define an $\mathcal {H}$ deletion set (HDS) of a graph G as a set $M\subseteq E(G)$ such that $G - M$ is $\mathcal {H}$-free. A minimum $\mathcal {H}$ deletion set (MHDS) is an HDS with smallest cardinality. Every graph in $\mathcal {H}$ is called an obstruction. An obstruction in a graph G is an induced copy of any of the graphs in $\mathcal {H}$. When we use these terms, $\mathcal {H}$ will always be clear from the context. We define a partition of an MHDS M of G as follows.

$$\begin{aligned} M_1= & {} \left\{ e: e\in M\ \text {and}\ e\ \text {is part of an obstruction in}\ G\right\} .\\ M_j= & {} \left\{ e: e\in M\setminus \bigcup \nolimits _{i=1}^{i=j-1}M_i\ \text {and}\ e\ \text {is part of an obstruction in}\ G \right. \\&\left. - \bigcup \nolimits _{i=1}^{i=j-1}M_i\right\} , \text {for}\ j>1. \end{aligned}$$

We define the depth of an MHDS M of G, denoted by $l_M$, as the least integer such that $|M_i|>0$ for all $1\le i\le l_M$ and $|M_i|=0$ for all $i>l_M$. Proposition 1 shows that this notion is well defined.

Proposition 1

• 1. $\{M_j\}$ forms a partition of M.

• 2. There exists $l_M\ge 0$ such that $|M_i|>0$ for all $1\le i\le l_M$ and $|M_i|=0$ for all $i > l_M$.

Proof

If $i\not = j$ and $M_i$ and $M_j$ are nonempty, then clearly, $M_i\cap M_j=\emptyset$. For $i\ge 1$, by definition, $M_i\subseteq M$. Assume that there is an edge $e\in M - \bigcup M_j$. Then, $|\bigcup M_j| < |M|$. Delete all edges in $\bigcup M_j$ from G. By definition, what remains is an $\mathcal {H}$-free graph. This is a contradiction to the fact that M is an MHDS. Hence there can not exist such an edge e. This proves that $\{M_j\}$ forms a partition of M. Now let j be the smallest integer such that $M_j$ is empty. Then from definition, for all $i>j$, $|M_i|=0$. Therefore $l_M=j-1$.$\square$

We observe that for an $\mathcal {H}$-free graph, the only MHDS M is $\emptyset$ and hence $l_M=0$. For an MHDS M of G with depth $l_M$, we define the following terms.

• $S_j=\bigcup _{i=j}^{i=l_M}M_i$ for $1\le j\le l_M+1$.

• $T_j= M\setminus S_{j+1}$ for $0\le j\le l_M$.

• $V_{\mathcal {H}}(G)$ is the set of all vertices part of some obstructions in G.

We observe that $S_1=T_{l_M}=M$, $S_{l_M} = M_{l_M}$, $T_1= M_1$ and $S_{l_M+1}=T_0=\emptyset$.

Proposition 2

For a graph G, let $E'\subseteq E(G)$ be such that at least one edge in every obstruction in G is in $E'$. Then, at least one vertex in every obstruction in $G - E'$ is in $V_{E'}$.

Proof

Assume that there exists an induced $H\in \mathcal {H}$ in $G - E'$ with the vertex set $V'$. For a contradiction, assume that $V'\cap V_{E'}=\emptyset$. Then, $V'$ induces a copy of H in G. Hence, $E'$ must contain some of its edges. $\square$

For a set $\mathcal {H}$ of connected graphs and an input graph G, the following lemma gives an upper bound on the distance between $V_{\mathcal {H}}(G)$ and the vertices of any MHDS M of G.

Lemma 1

Let G be an input graph of an $\mathcal {H}$-free Edge Deletion problem instance where $\mathcal {H}$ is a set of connected graphs with diameter at most D. Let M be an MHDS of G. Then, every vertex in $V_M$ is at a distance at most $\left( l_M-1\right) D$ from $V_{\mathcal {H}}(G)$ in G.

Proof

For $2\le j\le l_M$, from definition, at least one edge in every obstruction in $G - T_{j-2}$ is in $M_{j-1}$. Hence by Proposition 2, at least one vertex in every obstruction in $G - T_{j-1}$ is in $V_{M_{j-1}}$. By definition, every vertex in $V_{M_j}$ is part of some obstruction in $G - T_{j-1}$. This implies that every vertex in $V_{M_j}$ is at a distance at most D from $V_{M_{j-1}}$. Hence every vertex in $V_{M_{l_M}}$ is at a distance at most $(l_M-1)D$ from $V_{M_1}$. By definition, $V_{M_1}\subseteq V_{\mathcal {H}}(G)$. This completes the proof.$\square$

Proposition 3

Let $\mathcal {H}$ be a set of connected graphs. Let $E'\subseteq E(G)$ be such that at least one edge in every obstruction in a graph G is in $E'$. Let $M'$ be the set of all edges incident to $V_{E'}$ in G. Then, $M'$ is an HDS of G.

Proof

For a contradiction, assume that $G-M'$ has an induced copy of a graph $H\in \mathcal {H}$ induced by a vertex set $U\subseteq V(G)$. Since every obstruction is a connected graph and the vertices in $V_{E'}$ in $G-M'$ are isolated, U and $V_{E'}$ are disjoint. Hence, U induces H in G. Therefore at least one edge in G[U] must be in $E'$. This implies that $U\cap V_{E'}\ne \emptyset$, which is a contradiction.

Lemma 2

Let G be a graph with maximum degree at most ${\varDelta }$ and M be an MHDS of G, where $\mathcal {H}$ is a set of connected graphs. Then, for $1\le j\le l_M$, $(2{\varDelta }-1)\cdot |M_j|\ge |S_{j+1}|$.

Proof

For $1\le j\le l_M$, from definition, $M_j$ has at least one edge from every obstruction in $G - T_{j-1}$. Let $M'_j$ be the set of all edges incident to vertices in $V_{M_j}$ in $G - T_{j-1}$. By Proposition 3, $\left( G - T_{j-1}\right) - M'_j$ is $\mathcal {H}$-free and hence $|T_{j-1}\cup M'_j|$ is an HDS of G. Clearly, $|M'_j|\le {\varDelta }|V_{M_j}|\le 2{\varDelta }|M_j|$. Since M is an MHDS, $|T_{j-1}\cup M'_j| = |T_{j-1}|+|M'_j|\ge |M|=|T_{j-1}|+|S_j|$. Therefore $|M'_j|\ge |S_j|$. Hence, $2{\varDelta }|M_j|\ge |S_j|=|M_j|+|S_{j+1}|$.$\square$

Now we give an upper bound for the depth of an MHDS in terms of its size and the maximum degree of the input graph.

Lemma 3

Let M be an MHDS of G, where $\mathcal {H}$ is a set of connected graphs. If the maximum degree of G is at most ${\varDelta }>0$, then $l_M\le 1+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}|M|$.

Proof

The statement is clearly true when $l_M = 0$. Hence assume that $l_M\ge 1$. The result follows from repeated application of Lemma 2.

$$\begin{aligned} |M|&= |S_1|=|M_1|+|S_2|\ge \frac{|S_2|}{2{\varDelta }-1}+|S_2|\\&\ge |S_{l_M}|\left( \dfrac{2{\varDelta }}{2{\varDelta }-1}\right) ^{l_M-1}\\&\ge \left( \dfrac{2{\varDelta }}{2{\varDelta }-1}\right) ^{l_M-1} \quad [\because |S_{l_M}|\ge 1] \end{aligned}$$

$\square$

Corollary 1

Let (G, k) be a yes-instance of $\mathcal {H}$-free Edge Deletion, where $\mathcal {H}$ is a set of connected graphs and G has maximum degree at most ${\varDelta }>0$. For any MHDS M of G, $l_M\le 1 + \log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k$.

Lemma 4 will be used to prove the safety of our kernelization rules and Lemma 5 will be used to find the kernel size in the upcoming sections.

Lemma 4

Let $\mathcal {H}$ be a set of connected graphs, each with diameter at most D. Let $V'\supseteq V_{\mathcal {H}}(G)$ and let $c\ge 0$. Let $G'$ be obtained by removing all vertices of G at a distance more than $c+D$ from $V'$. Furthermore, assume that if $G'$ is a yes-instance then there exists an MHDS $M'$ of $G'$ such that every vertex in $V_{M'}$ is at a distance at most c from $V'$ in $G'$. Then (G, k) is a yes-instance if and only if $(G',k)$ is a yes-instance of $\mathcal {H}$-free Edge Deletion.

Proof

Let (G, k) be a yes-instance with an MHDS M. Since $G'$ is an induced subgraph of G, $M\cap E(G')$ is an HDS of $G'$. Hence, $(G',k)$ is a yes-instance. Conversely, let $G'$ be a yes-instance. By the assumption, there exists an MHDS $M'$ of $G'$ such that every vertex in $V_{M'}$ is at a distance at most c from $V'$ in $G'$. We claim that $M'$ is an HDS of G. For a contradiction, assume $G - M'$ has an induced $H\in \mathcal {H}$ with a vertex set $V''$. As G and $G'$ have the same set of induced copies of graphs in $\mathcal {H}$, at least one edge in every obstruction in G is in $M'$. Then, by Proposition 2, at least one vertex in $V''$ is in $V_{M'}$. By the construction of $G'$, for every vertex in $G'$, the distance from $V'$ is the same in G and $G'$. Hence every vertex in $V''$ is at a distance at most $c+D$ from $V'$ in G. Then, by the construction of $G'$, $V''$ induces a copy of H in $G' - M'$, which is a contradiction. $\square$

Lemma 5

Let G be a graph and let $d>1$ be an integer. Let $V'\subseteq V(G)$ be such that all vertices in G with degree more than d are in $V'$. Partition $V'$ into $V_1$ and $V_2$ such that $V_1$ contains all the vertices in $V'$ with degree at most d and $V_2$ contains all the vertices with degree more than d. If every vertex in G is at a distance at most $c>0$ from $V'$, then $|V(G)|\le |V_1|\cdot d^{c+1} + |N_G[V_2]|\cdot d^{c}$.

Proof

To enumerate the number of vertices in G, consider the d-ary breadth first trees rooted at vertices in $V_1$ and in $N_G[V_2]$.

$$\begin{aligned} |V(G')|&\le |V_1|\left( \dfrac{d^{c+1}-1}{d-1}\right) + |N_G[V_2]|\left( \dfrac{d^{c}-1}{d-1}\right) \\&\le |V_1|d^{c+1} + |N_G[V_2]|d^{c}. \end{aligned}$$

$\square$

3 Polynomial Kernels

In this section, we assume that $\mathcal {H}$ is a fixed finite set of connected graphs with diameter at most D. First we devise an algorithm to obtain a polynomial kernel for $\mathcal {H}$-free Edge Deletion for bounded-degree input graphs.

We assume that the input graph G has maximum degree at most ${\varDelta }>1$ and G has at least one induced copy of H. We observe that if these conditions are not met, obtaining polynomial kernel is trivial. Now we state the kernelization rule which is the single rule in the kernelization.

• Rule 0: Delete all vertices in G at a distance more than $\left( 1+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k\right) D$ from $V_{\mathcal {H}}(G)$.

For a graph $H\in \mathcal {H}$, the set of vertices part of an induced H in G can be computed by considering all possible subsets of V(G) of size |V(H)|. Clearly, this can be done in time $O\left( |V(G)|^{|V(H)|}\right)$. By doing this for every graph in $\mathcal {H}$, the set $V_{\mathcal {H}}(G)$ can be computed in time $O\left( |V(G)|^{|V(H')|}\right)$, where $H'$ is a graph in $\mathcal {H}$ with maximum number of vertices. We note that the rule can be applied efficiently with the help of breadth first search from vertices in $V_{\mathcal {H}}(G)$. Now we prove the safety of the rule.

Lemma 6

Rule 0 is safe.

Proof

Let $G'$ be obtained from G by applying Rule 0. Let $M'$ be an MHDS of $G'$. If $(G',k)$ is a yes-instance, then by Lemma  and Corollary 1, every vertex in $V_{M'}$ is at a distance at most $D\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k$ from $V_{\mathcal {H}}(G')$. Hence, we can apply Lemma 4 with $V'=V_{\mathcal {H}}(G)$ and $c=D\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k$. $\square$

Lemma 7

Let (G, k) be a yes-instance of $\mathcal {H}$-free Edge Deletion. Let $G'$ be obtained by one application of Rule 0 on G. Then, $|V(G')|\le \left( 2{\varDelta }^{2D+1}\cdot k^{pD+1}\right)$ where $p=\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}{\varDelta }$.

Proof

Let M be an MHDS of G such that $|M|\le k$. We observe that every vertex in $V_{\mathcal {H}}(G)$ is at a distance at most D from $V_{M_1}$ in G. Hence, by construction, every vertex in $G'$ is at a distance at most $\left( 2+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k\right) D$ from $V_{M_1}$ in G and in $G'$. We note that $|V_{M_1}|\le 2k$. To enumerate the number of vertices in $G'$, we apply Lemma 5 with $V'=V_{M_1}$, $c=\left( 2+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k\right) D$ and $d={\varDelta }$.

$$\begin{aligned} |V(G')|&\le 2k{\varDelta }^{\left( 2+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k\right) D+1}\\&\le 2{\varDelta }^{2D+1}\cdot k^{pD+1} \end{aligned}$$

$\square$

Now we present the algorithm to obtain a polynomial kernel. The algorithm applies Rule 0 on the input graph and depending on the number of vertices in the resultant graph it returns the resultant graph or a trivial no-instance.

Theorem 1

The kernelization for $\mathcal {H}$-free Edge Deletion returns a kernel with at most $2{\varDelta }^{2D+1}\cdot k^{pD+1}$ vertices, where $p=\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}{\varDelta }$.

Proof

Follows from Lemma 6 and Lemma 7 and the observation that the number of vertices in the trivial no-instance is at most $2{\varDelta }^{2D+1}\cdot k^{pD+1}$.$\square$

We observe that the kernelization works even if the input graph contains high degree vertices far away from the induced obstructions.

Theorem 2

$\mathcal {H}$-free Edge Deletion admits polynomial kernelization if $\mathcal {H}$ is a finite set of connected graphs with maximum diameter D and the input graphs do not have any vertices with degree more than ${\varDelta }$ at a distance at most $\left( 1+\log _{\frac{2{\varDelta }}{2{\varDelta }-1}}k\right) D$ from $V_{\mathcal {H}}(G)$.

3.1 Stronger Results for Restricted Cases

Here we give polynomial kernels for $\mathcal {H}$-free Edge Deletion in the following three settings:

• $\mathcal {H}$ contains $K_{1,s}$ and $K_t$;

• $\mathcal {H}$ contains $K_{1,s}$ and the input graphs are $K_t$-free;

• $\mathcal {H}$ contains $K_{t}$ and the input graphs are $K_{1,s}$-free;

where $s>1$ and $t>2$ are any fixed integers and all graphs in $\mathcal {H}$ are connected. Henceforth, we assume that the problem $\mathcal {H}$-free Edge Deletion we consider satisfies one of these constraints.

It is proved in [25] that the maximum degree of a $\{\text {claw},K_4\}$-free graph is at most 5. We give a straightforward generalization of this result for $\{K_{1,s},K_t\}$-free graphs. Let R(s, t) denote the Ramsey number. Ramsey number R(s, t) is the least integer such that every graph on R(s, t) vertices has either an independent set of order s or a complete subgraph of order t.

Lemma 8

For integers $s> 1,t> 1$, any $\{K_{1,s}, K_t\}$-free graph has maximum degree at most $R(s,t-1)-1$.

Proof

Assume that G is $\{K_{1,s}, K_t\}$-free. For contradiction, assume that G has a vertex v of degree at least $R(s,t-1)$. By the definition of the Ramsey number there exist at least s mutually non-adjacent vertices or $t-1$ mutually adjacent vertices in the neighborhood of v. Hence there exists either an induced $K_{1,s}$ or an induced $K_t$ in G.$\square$

We modify the proof technique used for devising polynomial kernelization for $\mathcal {H}$-free Edge Deletion for bounded-degree graphs to obtain polynomial kernels for $\mathcal {H}$-free Edge Deletion under all the three settings mentioned above.

Let M be an MHDS of G. Let $d=R(s,t-1)-1$. Let D be the maximum diameter of graphs in $\mathcal {H}$. We define the following.

• $V_R(G)=\{v: v\in V(G)\ \text {and}\ v\ \text {has degree at least} d+1 \text {in} G\}$.

• $M_0=\{e: e\in M\ \text {and}\ e\ \text {is incident to a vertex in}\ V_R(G)\}$.

Lemma 9

$G - M_0$ has degree at most d and every vertex in G with degree at least $d+1$ is incident to at least one edge in $M_0$.

Proof

As $G - M$ is $\{K_{1,s}, K_t\}$-free and every edge in M which is incident to at least one vertex of degree at least $d+1$ is in $M_0$, the statement follows from Lemma 8.$\square$

Lemma 10

Let M be an MHDS of G. Let $M^{\blacktriangledown }=M\setminus M_0$ and $G^{\blacktriangledown }=G - M_0$. Then, $M^{\blacktriangledown }$ is an MHDS of $G^{\blacktriangledown }$ and every vertex in $V_M$ is at a distance at most $Dl_{M^{\blacktriangledown }}$ from $V_{\mathcal {H}}(G)\cup V_R(G)$ in G .

Proof

It is straightforward to verify that $M^{\blacktriangledown }$ is an MHDS of $G^{\blacktriangledown }$. By Lemma 1, every vertex in $V_{M^{\blacktriangledown }}$ is at a distance at most $\left( l_{M^{\blacktriangledown }}-1\right) D$ from $V_{\mathcal {H}}(G^{\blacktriangledown })$ in $G^{\blacktriangledown }$. Every induced $H\in \mathcal {H}$ in $G^{\blacktriangledown }$ is either an induced H in G or formed by deleting $M_0$ from G. Therefore, every vertex in $V_{\mathcal {H}}(G^{\blacktriangledown })$ is at a distance at most D from $V_{\mathcal {H}}(G)\cup V_R(G)$ in $G^{\blacktriangledown }$. Hence, every vertex in $V_{M^{\blacktriangledown }}$ is at a distance at most $Dl_{M^{\blacktriangledown }}$ from $V_{\mathcal {H}}(G)\cup V_R(G)$ in $G^{\blacktriangledown }$. Therefore, every vertex in $V_{M^{\blacktriangledown }}$ is at a distance at most $Dl_{M^{\blacktriangledown }}$ from $V_{\mathcal {H}}(G)\cup V_R(G)$ in G. The result follows from the fact $M=M^{\blacktriangledown }\cup M_0$.$\square$

The single rule in the kernelization is:

• Rule 1: Delete all vertices in G at a distance more than $\left( 2+\log _{\frac{2d}{2d-1}}k\right) D$ from $V_{\mathcal {H}}(G)\cup V_R(G)$ where $d=R(s,t-1)-1$.

Lemma 11

Rule 1 is safe.

Proof

Let $G'$ be obtained from G by applying Rule 1. Let $M'$ be an MHDS of $G'$. If $G'$ is a yes-instance, then by Lemma 10 and Corollary 1, every vertex in $V_{M'}$ is at a distance at most $D(1+\log _{\frac{2d}{2d-1}}k)$ from $V_{\mathcal {H}}(G')\cup V_R(G')$ in $G'$. We note that $V_{\mathcal {H}}(G)=V_{\mathcal {H}}(G')$ and $V_R(G)=V_R(G')$. Hence, we can apply Lemma 4 with $V'=V_{\mathcal {H}}(G)\cup V_R(G)$, $c=D(1+\log _{\frac{2d}{2d-1}}k)$, where $d=R(s,t-1)-1$. $\square$

Lemma 12

Let (G, k) be a yes-instance of $\mathcal {H}$-free Edge Deletion. Let $G'$ be obtained by one application of Rule 1 on G. Then, $|V(G')|\le 8d^{3D+1}\cdot k^{pD+1}$ where $p=\log _{\frac{2d}{2d-1}}d$.

Proof

Let M be an MHDS of G such that $|M|\le k$. We observe that every vertex in $V_{\mathcal {H}}(G)$ is at a distance at most D from $V_{M_1}$ in G. Hence, by construction, every vertex in $G'$ is at a distance at most $D\left( 3+\log _{\frac{2d}{2d-1}}k\right)$ from $V_{M_1}\cup V_R(G)$. Clearly $|V_{M_1}|\le 2k$. Using Lemma 9 we obtain $|N_G[V_R(G)]|\le 2k(d+2)$. To enumerate the number of vertices in $G'$, we apply Lemma 5 with $V'=V_{M_1}\cup V_R(G)$, $c=D\left( 3+\log _{\frac{2d}{2d-1}}k\right)$ and $d=R(s,t-1)-1$.

$$\begin{aligned} |V(G')|&\le 2kd^{D\left( 3+\log _{\frac{2d}{2d-1}}k\right) +1}+2k(d+2)d^{D\left( 3+\log _{\frac{2d}{2d-1}}k\right) }\\&\le 8d^{3D+1}\cdot k^{pD+1} \end{aligned}$$

$\square$

Now we present the algorithm. We use the same algorithm to obtain polynomial kernels for $\mathcal {H}$-free Edge Deletion in all the three settings.

We remark that the precise value of Ramsey number R(s, t) is not known even for small values of s and t. However, our algorithm runs in polynomial time as computing R(s, t) takes constant time for constants s and t. For practical implementation, we can use any specific known upper bound for $R(s,t-1)$ or the general upper bound $\left( {\begin{array}{c}s+t-3\\ s-1\end{array}}\right)$.

Theorem 3

The kernelization for $\mathcal {H}$-free Edge Deletion where $\mathcal {H}$ is a finite set of connected graphs under the following settings returns kernels with the number of vertices at most $8d^{1+3D}\cdot k^{1+pD}$ where $d=R(s,t-1)-1$ and $p=\log _{\frac{2d}{2d-1}}d$.

• $\mathcal {H}$ contains $K_{1,s}$ and $K_t$

• $\mathcal {H}$ contains $K_{1,s}$ and the input graphs are $K_t$-free

• $\mathcal {H}$ contains $K_{t}$ and the input graphs are $K_{1,s}$-free

where $s>1$ and $t>2$ are any fixed integers

Proof

Follows from Lemma 11 and Lemma 12.$\square$

It is known [4] that line graphs are characterized by a finite set of connected forbidden induced subgraphs including a claw ($K_{1,3}$).

Corollary 2

Claw-free Edge Deletion and Line Edge Deletion admit polynomial kernels for $K_t$-free input graphs for any fixed $t>2$. Specifically, Claw-free Edge Deletion admits a kernel of $O\left( k^{32}\right)$ vertices on $K_4$-free input graphs and Line Edge Deletion admits a kernel of $O\left( k^{63}\right)$ vertices on $K_4$-free input graphs.

Corollary 3

$\{K_{1,3},K_4\}$-free Edge Deletion admits a kernel of $O\left( k^{32}\right)$ vertices.

As planar graphs are $K_5$-free, Claw-free Edge Deletion and Line Edge Deletion admit polynomial kernels on planar graphs as well.

4 Concluding Remarks

Recently, Drange, Dregi and Sandeep [13] proved that for any finite set $\mathcal {H}$ of graphs , $\mathcal {H}$ -free Edge Editing admits a polynomial kernel on bounded-degree graphs. Under the assumption NP$\not \subseteq$coNP/poly, they proved that, in general, $\mathcal {H}$ -free Edge Completion does not admit polynomial kernel on bounded-degree graphs and that $\mathcal {H}$-free Edge Deletion does not admit polynomial kernel on 2-degenerate graphs. These results have shed much light on the compressibility of edge modification problems. We conclude with an open problem: does $\mathcal {H}$-free Edge Deletion admit a polynomial kernel for planar input graphs?