Kernelization Dichotomies for Hitting Subgraphs under Structural Parameterizations
Marin Bougeret Bart M. P. Jansen Ignasi Sau


Dimensional Crossover of Microscopic Magnetic Metasurfaces for Magnetic Field Amplification
    A. V. Silhanek
    April 29, 2024
===========================================================================================




For a fixed graph H, the H-Subgraph Hitting problem consists in deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of H as a subgraph. This problem can be seen as a generalization of Vertex Cover, which corresponds to the case H = K_2. We initiate a study of H-Subgraph Hitting from the point of view of characterizing structural parameterizations that allow for polynomial kernels, within the recently active framework of taking as the parameter the number of vertex deletions to obtain a graph in a “simple” class . Our main contribution is to identify graph parameters that, when H-Subgraph Hitting is parameterized by the vertex-deletion distance to a class  where any of these parameters is bounded, and assuming standard complexity assumptions and that H is biconnected, allow us to prove the following sharp dichotomy: the problem admits a polynomial kernel if and only if H is a clique. These new graph parameters are inspired by the notion of -elimination distance introduced by Bulian and Dawar [Algorithmica 2016], and generalize it in two directions.
Our results also apply to the version of the problem where one wants to hit H as an induced subgraph, and imply in particular, that the problems of hitting minors and hitting (induced) subgraphs have a substantially different behavior with respect to the existence of polynomial kernels under structural parameterizations.







    
    
    
    
    
    
    
    

    
    








§ INTRODUCTION



The theory of parameterized complexity deals with parameterized problems, which are decision problems in which a positive integer k, called the parameter, is associated with every instance x. One of the pivotal notions in the domain is that of kernelization <cit.>, which is a polynomial-time
algorithm that reduces any  instance (x, k) of a parameterized problem to an equivalent instance (x',k') of
the same problem whose size is bounded by f(k) for some function f, which is the size of
the kernelization. A kernelization algorithm, or just kernel, can be seen as a preprocessing procedure with provable guarantees, and it is fundamental to find kernels of the smallest possible size, ideally polynomial. Identifying which parameterized problems admit polynomial kernels is one of the most active areas within Parameterized Complexity (cf. for instance <cit.>).

When dealing with a problem where the goal is to find a (say, small) subset of vertices S of an input graph G satisfying some property, such as Vertex Cover, it is natural to consider as the parameter the size of the desired set S. Assuming that the problem admits a polynomial kernel parameterized by |S|, as it is the case for Vertex Cover and many other problems <cit.>, we can ask whether the problem still admits polynomial kernels when the parameter is (asymptotically) smaller than the solution size. The goal of this approach is to provide better preprocessing guarantees, as well as to understand what is the limit of the polynomial-time “compressibility” of the considered problem. For problems defined on graphs, apart from using the solution size as a parameter, it is common  to consider so-called structural parameters, which quantify some structural property of the input graph that can be seen as a measure of its “complexity”. Among structural parameters, the most successful is probably treewidth <cit.>, but unfortunately taking the treewidth of the input graph as the parameter does not allow for polynomial kernels for essentially all natural optimization problems, unless NP⊆ coNP/ poly <cit.>. The same applies to another relevant graph parameter called treedepth, denoted by  and defined as the minimum number of rounds needed to obtain the empty graph, where each round consists of removing one vertex from each connected component.


In fact, the lower bound proofs go through for parameterizations for which the value on a disconnected graph is the maximum, rather than the sum, of the values of its components, and whose value is polynomially bounded  in the size of the graph. Hence, to be able to obtain positive kernelization results, we need to turn to parameterizations other than width measures. This motivates to consider structural parameters that quantify the “distance from triviality”, a concept first coined by Guo, Hüffner, and  Niedermeier <cit.>.  The idea is to take as the parameter the vertex-deletion distance of a graph to a “trivial” graph class where the considered problem can be solved efficiently. This paradigm has proved very successful for a number of problems, in particular for Vertex Cover. In an influential work, Jansen and Bodlaender <cit.> showed that Vertex Cover  admits a polynomial kernel
when parameterized by the feedback vertex number of the input graph,
which is the vertex-deletion distance to the “trivial” class of forests. This result triggered a number of results in the area, aiming to characterize the “trivial” families  for which Vertex Cover admits a polynomial kernel under this parameterization <cit.>.

Let us mention some of these results that are relevant to our work. Bougeret and Sau <cit.> proved that Vertex Cover admits a polynomial kernel parameterized by the vertex-deletion distance to a graph of bounded treedepth. This result was further generalized into two orthogonal directions, namely by considering a more general problem or a more general target graph class . For the former generalization, Jansen and Pieterse <cit.> proved that the following problem also admits a polynomial kernel parameterized by the vertex-deletion distance to a graph of bounded treedepth: for a fixed finite set of connected graphs , the -Minor Deletion problem consists in deleting the minimum number of vertices from an input graph to obtain a graph that does not contain any of the graphs in  as a minor. Note that this problem (vastly) generalizes Vertex Cover, which corresponds to the case ={K_2}. For the latter generalization, Bougeret, Jansen, and Sau <cit.> proved that Vertex Cover admits a polynomial kernel parameterized by the vertex-deletion distance to a graph of bounded bridge-depth, which is a parameter that generalizes treedepth and the feedback vertex number. It turns out that, under the assumption that the target graph class  is minor-closed, the property of  having bounded bridge-depth is also a necessary condition for Vertex Cover admitting a polynomial kernel. Another complexity dichotomy of this flavor has been achieved by Dekker and Jansen <cit.> for the Feedback Vertex Set problem (with another characterization of the target graph class ). These complexity dichotomies, while precious, are unfortunately quite hard to obtain, and the current knowledge seems still far from obtaining dichotomies of this type for general families of problems, such as for -Minor Deletion for any finite family of graphs . Indeed, it is wide open whether -Minor Deletion admits a polynomial kernel parameterized by the solution size for any set  containing only non-planar graphs <cit.>, so considering parameters smaller than the solution size is still out of reach.



    Our contribution.
 We consider an alternative generalization of Vertex Cover by considering (induced) subgraphs instead of minors. Namely, for a fixed graph H, the H-Subgraph Hitting problem is defined as deleting the minimum number of vertices from an input graph to obtain a graph without any occurrence of H as a subgraph. The H-Induced Subgraph Hitting problem is defined analogously by forbidding occurrences of H as an induced subgraph.
(As we shall see later, both problems behave in the same way with respect to our results.) Note that both problems correspond to Vertex Cover for the case H=K_2 and therefore are indeed generalization of it. As opposed to the case for hitting minors, it is well-known that both the H-Subgraph Hitting and H-Induced Subgraph Hitting problems admit polynomial kernels parameterized by the solution size for any graph H <cit.>.

Therefore, it does make sense to parameterize these problems by structural parameters in the “distance from triviality” spirit, and this is the main focus of this article. To be best of our knowledge, this is an unexplored topic, besides all the literature for Vertex Cover discussed above. Our main result is to identify structural parameters that allow to provide sharp dichotomies for these problems depending on the forbidden (induced) subgraph H.

Before presenting our results, we proceed to motivate and define these structural parameters. They are inspired by the following parameter, first
introduced by Bulian and Dawar <cit.> and further studied, for instance, in <cit.>. For a fixed class of graphs $̋, the$̋-elimination distance of a graph G, denoted by (G), is defined by mimicking the above definition of treedepth and replacing “empty graph” with “a graph in $̋”. The recursive definitions of treedepth and$̋-elimination distance suggest the notion of elimination forest, which is the forest-like process of vertex removals from the considered graph to obtain either an empty graph for treedepth, or a graph in $̋ for$̋-elimination distance. Suppose now that $̋ is defined by the exclusion of a fixed graphHas a subgraph or as an induced subgraph. Formally, let_H̅(resp.^𝗂𝗇𝖽_H̅) be the class of graphs that exclude a fixed graphHas a subgraph (resp. induced subgraph). For this particular case, the notion of_H̅-elimination distance (or^𝗂𝗇𝖽_H̅-elimination distance) can be interpreted as a generalization of treedepth where, in the last round of the elimination process, the vertices that do not belong to any occurrence of$̋ as a subgraph (or induced subgraph) can be deleted “for free”. We generalize the notion of $̋-elimination distance by allowing  “free removal” of vertices not contained in a copy ofHin  every round of the elimination process, rather than just the last; we denote the corresponding parameter by(or), where `v' stands for the removal of  vertices, in order to distinguish this parameter from the one defined below (see <ref> for the formal definitions of these parameters). Our first main result is the following somehow surprising dichotomy, which states that, under the assumption thatHis biconnected,

wheneverHhas a non-edge, the problem is unlikely to admit a polynomial kernel.
Our result applies to both the induced and non-induced versions of the problem.


Let H be a biconnected graph, let λ≥ 1 be an integer, and assume that NP⊈ coNP/ poly. H- Subgraph Hitting  (resp. H- Induced Subgraph Hitting) admits a polynomial kernel parameterized by the size of a given vertex set X of the input graph G such that (G-X) ≤λ (resp. (G-X) ≤λ) if and only if H is a clique.


Note that a graphGsatisfies(G) = 0(resp.(G) = 0) if and only ifGdoes not containHas a subgraph (resp. induced subgraph), so the settingλ=0corresponds to the parameterization by solution size which always admits a polynomial kernel <cit.>; this is why we assume thatλ≥1in the statement of <ref>.

<ref> shows that the behavior of the considered problems in terms of the existence of polynomial kernels drastically changes as far as one edge is missing fromH(under the biconnectivity assumption, which is needed in the reduction). To the best of our knowledge, this is the first time that such a dichotomy, in terms ofH, is found with respect to the existence of polynomial kernels. It is worth mentioning that, with respect to the existence of certain fixed-parameter tractable algorithms parameterized by treewidth, dichotomies of this flavor exist for hitting subgraphs <cit.>, induced subgraphs <cit.>, or minors <cit.>.




The proof of <ref> consists of two independent pieces. On the one hand, we need to prove that both problems admit a polynomial kernel whenHis a clique (note that, in that case, both problems are equivalent, as anyH-subgraph is induced). On the other hand, we need to provide a kernelization lower bound for all other graphsH(cf. <ref>), and here is where we need the hypothesis thatNP ⊈coNP/polyand, for technical aspects of the reduction, thatHis biconnected.


In fact, we provide a kernel that is more general than the one stated in <ref>. Also, on the negative side, we present another lower bound incomparable to that of <ref>. For the former, we provide a polynomial kernel, whenHis a clique, for a parameter that is more powerful than(or).
 This more powerful parameter is somehow inspired by the parameter bridge-depth mentioned before <cit.>, which is a generalization of treedepth in which, in every round of the elimination process, we are allowed to remove subgraphs in each component that are more general than just single vertices. In our setting, it turns out that we can afford to remove vertex setsT ⊆V(G)that induce connected subgraphs that do not containHas a subgraph (or induced subgraph) and that are “weakly attached” to the rest of the graph, meaning that each connected component ofG-Thas at most one neighbor inT. IfHis biconnected, it is easily seen that the “candidate” setsTto be removed can be assumed to be connected unions of blocks (biconnected components) ofG, and this is why we call this parameter(or), where `b' stands for the removal of  blocks. For any two graphsGandH, the following inequalities, as well as the corresponding ones for the induced version, follow easily from the definitions (cf. <ref>):

    (G) ≥ ed__H̅(G) ≥(G) ≥(G).

 We prove the following result, whereK_tdenotes the clique ont-vertices, and note that in this case the induced and non-induced versions of the problem coincide.

 
Let t≥ 3 and λ≥ 1 be fixed integers. The K_t- Subgraph Hitting  problem admits a polynomial kernel parameterized by the size of a given vertex set X of the input graph G such that (G-X) ≤λ.


Note that fort=2, the parameteris exactly treedepth, and therefore <ref> can be seen as a far-reaching generalization of the main result of <cit.>, that is, a polynomial kernel for  Vertex Cover parameterized by the vertex deletion distance to a graph of bounded treedepth.

Also, note that <ref>
and <ref> imply that the same dichotomy stated in <ref> holds if we replace `(G-X) ≤λ' with `(G-X) ≤λ', and the same for the induced version.




As for strengthening our hardness results, we present kernelization lower bounds forH- Subgraph Hitting andH- Induced Subgraph Hitting, whenHis not a clique, parameterized by the vertex-deletion distance to a graph of constant  treedepth. By <ref>, lower bounds for treedepth are stronger than the ones of
<ref>. However, in our next main result, we need a condition onHthat is stronger than biconnectivity, namely the non-existence of a stable cutset, that is, a vertex separator that induces an independent set.



theoremhardness-treedepth
Let H be a graph on h vertices that is not a clique and that has no stable cutset. H- Subgraph Hitting and H- Induced Subgraph Hitting do not admit a polynomial kernel parameterized by the size of a given vertex set X of the input graph G such that (G-X) = Ø(h), unless NP⊆ coNP/ poly.


Note that, fort ≥4, the graphK_tminus one edge satisfies the conditions of <ref>. The mere existence of a graphHsatisfying the conditions of <ref> is remarkable, as it shows that  (induced) subgraph hitting problems behave differently than minor hitting problems. Indeed, as mentioned before, it is known <cit.> that, for  every finite familyof connected graphs, the- Minor Deletion problem admits a polynomial kernel parameterized by the vertex-deletion distance to a graph of constant treedepth.

Dekker and Jansen <cit.> asked if for every finite set of graphs,- Minor Deletion  admits a polynomial kernel parameterized by the vertex-deletion distance to a graph with constantexc()-elimination distance, whereexc()is the class of graphs that excludes all the graphs inas a minor. <ref> shows that, by <ref>, for the problems of excluding subgraphs or induced subgraphs, the answer to this question is negative.


Finally, let us mention another consequence of our results. Agrawal et al. <cit.> proved, among other results, that for every hereditary target graph classsatisfying some mild assumptions,
parameterizing by the vertex-deletion distance toand by the-elimination distance are equivalent from the point of view of the existence of fixed-parameter tractable algorithms. Our results imply, in particular, that the same equivalence does  not hold with respect to the existence of polynomial kernels in this “distance from triviality” setting, namely for problems defined by the exclusion of (induced) subgraphs.



    Organization of the paper.
  In <ref> we provide an overview of the main ideas of the kernelization algorithm, which is our main technical contribution. The full version of the kernel, which is quite lengthy, is presented from <ref> to  <ref>. More precisely, in <ref> we provide some preliminaries for the analysis of blocking sets (defined later) and the kernel. In <ref> we bound the size of minimal blocking sets, which is a crucial ingredient for the analysis of the kernelization algorithm, whose actual description can be found in <ref>, namely in <ref>. Its analysis also needs the results proved in <ref> (which are somehow independent)  to compute the decomposition associated with the parameteralong with optimal solutions in graphs with bounded. In <ref> we present our hardness results, and in <ref> we discuss some directions for further research.


§ OVERVIEW OF THE KERNELIZATION ALGORITHM




In this section we sketch the main ideas of the kernelization algorithm stated in <ref>, along with intuitive explanations and the required definitions.



    Preliminaries.
 Given a graphGandC ⊆V(G), we denote byN(C)=⋃_v ∈CN(v)∖CandG-C=G[V(G)∖C].
Given a graphH, and a subgraph (resp. induced subgraph)FofG, we say thatFis a copy (resp. induced copy) ofHifFis isomorphic toH. We say thatGisH-free (resp.H-induced free) if there is no copy ofH(resp. induced copy) inG.
Given two disjoint subsetsA,B ⊆V(G), we say that there is an edge betweenAandBif there existse ∈E(G)such that|e ∩A|=|e ∩B|=1. Otherwise,AandBare said to be anticomplete.
When={V_1, …, V_m}is a set of subsets ofV(G), we letV()=⋃_V_i ∈ V_i.
A t-clique is a setK ⊆V(G)such thatG[K]is a clique and|K|=t.
For any integern ∈ℕ, we denote by[n]={1,…,n}. We study the following problem(s) for a fixed graphH.




13.5cm (for H- Subgraph Hitting)
Input:  A graph G.
Objective:  Find a set S⊆ V(G) of minimum size such that G-S is H-free.


We denote by(for H- Induced Subgraph Hitting) the variant of the above problem where we impose thatG-SisH-induced free.










We denote by^H(G)the optimal value of the considered problem forG, or simply(G)whenHis clear from the context.

Let us now introduce the main graph measures used in this paper.


Let H be a fixed graph. For a graph G, define (G) as

    0    
    (G-v)    
    max_C_i(C_i)    
    
        1+min_v ∈ V(G)(G-v)

We definein the same way as, except that we replace “in any copy ofH” by “in any induced copy ofH”. Note that the notationis motivated by the fact that it corresponds to vertex elimination distance, with additional power of removing “free” vertices not in any copy ofH. Note also that even though there could be multiple verticesvwhich satisfy the second criterion, the value is well-defined since it does not matter which one is picked; the second case will apply until all such vertices have been removed.

As the case whereH=K_tplays an important role in this paper, for the sake of shorter notation we use the shortcutto denote the parameter(or, which is the same).






To define the parametersand, it is convenient to introduce the following definitions (see <ref>).

Given a fixed graph H and a connected graph G, we say that a set T ⊆ V(G) is a root of G if

  * T ≠∅, G[T] is connected and H-free, and
    
  *  for any connected component C of G-T, |N(C) ∩ T|=1.

We extend to notion of root to any graph G as follows. For any graph G with connected components 𝒞, we say that a set ={T_C | C ∈𝒞} is a root of G if for any C ∈𝒞,
T_C is a root of G[C].





Given a graph G and a root  of G, we define the pending component of v relatively to , denoted by C^(v), as the connected component of v in the graph obtained from G by removing all edges e ⊆ E().
We extend the notation to any subset Z ⊆ V() with
C^(Z) = ⋃_v ∈ ZC^(v). When the root is clear from context, we use C(v) instead of C^(v).


We define an induced root in the same way, except that we replace “G[T]is connected andH-free” by “G[T]is connected andH-induced free”. Note that any graph admits a root, by taking for example a single vertex (to play the role ofT_C) in each connected component.




Let G be a graph and  be a root of G.
For any v ∈ V(), there is no edge between C(v)∖{v} and V(G)  ∖ C(v).

Let H be a fixed graph. For a graph G,  we define (G) as

    0    
    (G-v)    
    max_C_i(C_i)    
    
        1+min_T ⊂ V(G)(G-T)

We definein the same way as, except that we replace “whereTranges over all roots ofG” by  “whereTranges over all induced roots ofG”.

Again, as the case whereH=K_tplays an important role in this paper,
 for the sake of shorter notation we use the shortcutto denote the parameter(or, which is the same).
We point out that, to make the definition ofas simple as possible, we allowedTto range over all roots ofG.
However, as shown in <ref>, as soon asHis biconnected, there always exists a root that is the connected union ofH-(induced-)free blocks ofG, hence our choice of notation to differentiatefrom.

















     




Givenλ∈ℕ, let us now define the following variant of the considered problem, where we suppose that we are given as an additional input a modulator (corresponding to setX) to a “simple” graphG-X, where the simplicity is captured bybeing at mostλ.



13.6cm^λ (for K_t-Subgraph Hitting given a modulator to  at most λ)
Input:  A graph G and a set X ⊆ V(G) such that (G[R]) ≤λ, where R = V(G)∖ X.
Objective:  Find a set S⊆ V(G) of minimum size such that for any t-clique Z of G, S ∩ Z ≠∅.



 We denote byλthe associated parameterized decision problem with an additionalkin the input, where the goal to decide whether(G) ≤k, and the parameter is|X|.

In <ref> we prove our main positive result that we restate here with less details, and which is a reformulation of <ref> with the notation introduced in this section:

  There is a polynomial kernel for λ of size Ø_λ,t(|X|^δ(λ,t)) for some function  δ(λ,t).

Let us now overview the techniques used to establish the above result.



    Warming up with  Vertex Cover.

As an extreme simplification of our set up, let us consider the case wheret=2, corresponding to   Vertex Cover, and assume thatXis a modulator to the simplest graph class, namely an independent set.
Our kernel uses a marking procedure (<ref>) that corresponds to the following marking algorithm for   Vertex Cover.
For anyu ∈X, mark up to|X|+1verticesv ∈Rsuch that{u,v} ∈E(G). LetM ⊆Rbe the set of marked vertices.
Observe the following “packing property” of the marking algorithm: if there existsv ∈R∖Mandu ∈Xwith{u,v} ∈E(G),
then there exists a “packing”⊆Mof|X|+1vertices such that for anyv' ∈,{v',u} ∈E(G)(the term “packing” may seem inappropriate
here, but becomes natural fort > 2as the marking algorithm will mark disjoint sets of vertices instead of distinct vertices).
Now, ifR=Mthen|R| ≤Ø(|X|^2)and the instance is kernelized. Otherwise, if there existsv ∈R∖M, then define a reduced instance asG'=G-vandk'=k.
Let us sketch why this removing step is safe, as the arguments also correspond to a very simplified version of <ref>. The only non-trivial direction is that if(G',k')is a -instance, then(G,k)is also a -instance.
Given a solutionZ'of(G',k'), if there existsu∈X ∖Z'such that{u,v} ∈E(G),
then the packing property implies the existence of the above set. Thus, we get thatZ'overpays for u: it contains one extra vertex (in this case, one instead of zero) for eachv' ∈as we must have⊆Z'. This implies that we can restructureZ'intoZ̃=X, while ensuring that|Z̃| ≤|Z'|. Now,Z̃can be easily completed to a solution ofGof sizek(in this case, by doing nothing).
By repeating this reduction rule, we get the kernel of size(|X|^2).





    Parts, chunks, and conflicts.

Let us now point out some important ideas used to lift up the previous kernel for   Vertex Cover toλ.

In the previous setting, the key property when proving the safeness of the reduction rule, given a solutionZ'of(G',k'), is the following:
when “adding back” a non-marked vertexv ∈R ∖MtoG',  either there existsu ∈X ∖Z'such thatZ'overpays foru, or there is no edge{u,v}for anyu ∈X ∖Z'.

Let us now rephrase this key property in the setting of hittingt-cliques using the adapted concepts of part, chunk, and conflict, and we will formally define these terms later.
When “adding back” a non-marked partV' ⊆R ∖MtoG', we know that either there exists a chunkX' ⊆X ∖Z'such thatZ'overpays forX', or there is no conflict between X' and V' for any chunkX'.
Observe first that, asG-Xis now more general than an independent set, we have to consider a packing of “parts” (subsets of vertices ofR), meaning that if there is a non-marked partV'that we remove, we now setk'=k-(G[V']). The second difference is the notion of “conflict  betweenX'andV'” that plays the role of “edge{u,v}”.
We say that there is no conflict betweenX'andV'if^t_X'(V')=0, the condition^t_X'(V')=0being equivalent to the fact that we can pick only(G[V'])vertices inV', while still hitting allt-cliques inG[X' ∪V'](see <ref> for the formal definition of^t).



The third difference is the notion of chunk and blocking set. A good starting point when trying to complete a solutionZ'ofG'to a solutionZofGis that^t_X ∖Z'(V')=0.
Indeed, this condition implies that there exists a setS^⋆_V'of size(G[V'])such thatS^⋆_V'hits allt-cliques inG[V' ∪(X ∖Z')]. Thus,S^⋆_V'is a good candidate to build a solutionZ = Z' ∪S^⋆_V'of(G,k). Note that this only remains a good starting point, asZmay not be a solution: it could miss cliques usingV',(X ∖Z'), and other vertices inR ∖V'.
This condition^t_X ∖Z'(V')=0could be achieved by a marking algorithm that, for anyU ⊆X, marks up to|X|+1partsV'such that^t_U(V')>0, which is  a generalization of the previous marking algorithm for   Vertex Cover.
However, the running time and the number of marked parts by such an algorithm would not be polynomial in|X|, as there are too many subsetsUto consider.

To overcome this issue, the trick is the notion of maximum minimal blocking sets, denoted by_t(<ref>), which is a graph parameter for which we skip the definition for the moment. What is important to state about_there is that in <ref> in <ref>, we prove that there exists a functionβ: ℕ^2 →ℕsuch that for every graphG,_t(G) ≤β((G),t). As in the kernelization algorithm we apply this toG[R]and(G[R]) ≤λ, we obtain_t(G[R]) ≤β(λ,t). Moreover, <ref> implies that the previous marking condition “there existsU ⊆Xsuch that^t_U(V')>0” is equivalent to “there existsX' ∈such that^t_X'(V')>0”, where= {X' ⊆X | }is the set of chunks.
Observe that, as the chunks have bounded size, the marking algorithm runs in timeØ^⋆(|X|^(t-1)β(λ,t)).
The conclusion is that the “triviality” ofG[R]((G[R]) ≤λ) implies thatG[R]has bounded_t, which allows to certify the absence of conflict (for anyU ⊆X) in polynomial time.

These notions of conflict, chunk, and minimal blocking set were also critical in previous work on kernelization: the notion of conflict was introduced in <cit.>, and bounds on_2(for   Vertex Cover) have been proved for different triviality measures ofG[R]<cit.>.
 A first difference here is the study of_tfor K_t-Subgraph Hitting, whose behavior is more complex than   Vertex Cover, as discussed below when mentioning the new challenges.





    Decreasing (G[R]) and using recursion.

Let us now informally describe the main steps of the kernel (see <ref>). Given a graphG, we denote byN^t(G)={v ∈V(G) |∄}the set of vertices ofGthat do not occur in any copy ofK_t, called the non-K_t-vertices.
Given an input(G,X,k)ofλ, we first computeN^t(G[R])and, using the algorithm of <ref>, a-rootofG[R]-N^t(G[R]), where a -root ofGis a rootsuch that(G-V()) = (G)-1.
We point out that, unlike  the case for treedepth or bridge-depth, computing such a root is not straightforward, as one cannot try the a priori exponentially many possible roots to find one that decreases.
However, the algorithm of <ref> relies on the fact that it is possible to compute in polynomial time a set of size(n)that contains a-root.


Coming back to the kernel strategy, observe that there may be edges between someC(v)andN^t(G), but not betweenC(v)andC(u)foru ≠v, and that by definition of a-root,(G[R']) < λ, whereR'=R-V().
      Then, we mark a small (polynomial in|X|) setM(,N^t(G[R]),G,X)of vertices (<ref>) ofV()using the  mark algorithm (<ref>).
      If there existsv ∈V() ∖M(,N^t(G[R]),G,X), then we can removeC(v)and decreasekby(G[C(v)])(<ref>).
      Otherwise,|M(,N^t(G[R]),G,X)|=Ø(|X|^f(λ,t))for some functionf, and thus we can moveM(,N^t(G[R]),G,X)to the modulator and get a new modulatorX' = X ∪M(,N^t(G[R]),G,X)whose
      size is still polynomial in|X|.
      The key point is that(G-X') = (G[R']) < λ, and thus we use induction onλand make a recursive call to(G,X'),
      which is an input ofλ-1, leading to a kernel  polynomial in|X'|, and thus in|X|.

  


This idea of shrinking the “root” of a decomposition ofG-Xto decrease the “triviality measure” (here,) and recurse originates in <cit.>, and was used in <cit.> for treedepth.

It was subsequently generalized in <cit.>, where the triviality measure is a parameter called bridge-depth and the equivalent of a root is a so-called tree of bridges for each connected component ofG[R].



    New challenges.

With respect to the strategies followed in previous work on related topics <cit.>, in our setting we encounter (at least)
 the following three orthogonal difficulties, for which we have to develop new ideas: dealing with the non-K_t-vertices, dealing with cliquesK_tfor arbitrary fixedtinstead oft=2, and proving that there exists a functionβsuch that for every graphG,_t(G) ≤β((G)).

The first difficulty is handling vertices ofN^t(G[R]), which are vertices not belonging to at-clique inG[R].
Indeed, observe that these non-K_t-vertices are “free” for, in the sense that(G[R])=(G[R]-N^t(G[R])).
However, these vertices make the structure ofG[R]more complicated. Indeed,being a root ofG[R]-N^t(G[R])implies that for anyT ∈andv ∈T,
there are no edges betweenC(v) ∖{v}and other vertices inC(u)foru ∈V() ∖{v}, but there could be edges betweenC(v)andN^t(G[R]).
Thus, unlike in <cit.>, we cannot just bound the number of connected components ofG[R], and then assume that we have a single rootTwith simple properties
(again, the root being a single vertex in <cit.>, and a tree of bridges in <cit.>).
Typically, hereG[R]could have only one connected component, but  the nice structure given bycould be “polluted” by vertices ofN^t(G[R]).
We handle these vertices by considering a packing of “bidimensional” parts(V_i,N_i), where in particularV_i ⊆V()is a clique of size at mostt-1andN_i ⊆N^t(G[R]), and we use a kind of generalized “sunflower-like” marking by first creating a maximal packingof parts(V_i,N_i), of size at most|X|+1,
and then recursively marking around each possibleg ∈⋃N_i(see the last line of <ref>).






















The second difficulty is to handlet-cliques instead of edges.
Indeed, assume that we just removed a pending componentC(v)for somev ∈V()and definedk'=k-(G[C(v)]).
Assume also that, given a solutionZ'of(G',k'), we have the good starting point^t_(X ∪N^t(G[R])) ∖Z'(C(v)) = 0, implying, by the definition of conflict, that there exists a locally optimal solutionS^⋆_vofG[C(v)]that intersects allt-cliques ofG[C(v) ∪((X ∪N^t(G[R])) ∖Z')].
However, there could also exist “spread” cliquesKcontainingvand using vertices of((X ∪N^t(G[R])) ∖Z')andM' ⊆(V()∖{v}).
These cliques may be spread across several vertices ofV(), and by definition of a root they cannot use vertices inC(u) ∖{u}for anyu ∈M' ∪{v}(according to <ref>).
To take into account the potential conflicts generated by these spread cliques, we performt-1marking steps  (<ref>),
where informally at each step we guess all possible subsetsM', with|M'| ≤t-1, corresponding to a guessed intersection of a spread clique with previously marked vertices.


The last difficulty is to bound_t(G)as a function of(G)for any graphG. We first need to define the notion of blocking set adapted to our problem. Let(for ExtendedK_t- Subgraph Hitting) be the problem where given(G,), whereis a set of subsets ofGsuch that for anyZ ∈, 1 ≤|Z| ≤t-1andG[Z]is a clique, a solution must intersect allt-cliques ofGand allZ ∈. A blocking setofGis a set of subsets of vertices ofGsuch that(G,)>(G), where(G,)is the minimum size of a solution of theproblem with input(G,), meaning that any set hitting allt-cliques ofGand allZ ∈cannot be an optimal solution ofGfor.
Then,_t(G)is the maximum size of an inclusion-wise minimal blocking set ofG.
The “max-min” taste of this definition makes it difficult to handle, but fortunately we will use Property <ref> stating that for anyβ,_t(G) ≤βis equivalent to the fact that for any blocking setofG, there exists ⊆such thatis still a blocking set ofGand|| ≤β.
We obtain the following upper bound, which requires a considerable amount of technical work.

  For any graph G and any integer t ≥ 3, it holds that _t(G) ≤β((G),t), where β(x,t)=
^2^t2^t2^⋯^t_x times
(i.e.,β(1)=2^t, β(2)=2^t2^t, etc.)


To explain the difficulty of proving the above theorem, let us sketch how such a bound is obtained for   Vertex Cover as a function of treedepth, for example in the proof in <cit.> that, for every graphG,_2(G) ≤2^(G).

Observe first that for the   Vertex Cover problem, a blocking setis
a set of singletons, which we consider as a subset of vertices,
such that any vertex coverScontainingis not optimal.
Let us now use Property <ref> and consider a blocking setofG, and let us show that there exists ⊆such thatis still a blocking set ofGand|| ≤2^(G).
Consider a graphGand  a “root”vof a treedepth decomposition ofG, meaning that(G-v) < (G).
Let us consider the most complex case where there exists an optimal solution usingv, another avoidingv, andv ∉.
It is not difficult to prove that, asis a blocking set ofG,_1=is a blocking set ofG_1:=G-v,
and_2=∖{N(v)}is a blocking set ofG_2 := G-({v} ∪N(v)). Thus, as for anyi ∈[2],(G_i) < (G), by induction
we get that there exists_i ⊆_isuch that_iis a blocking set ofG_iand|_i| ≤2^(G)-1. As_1 ∪_2is a blocking set ofG, we get the desired bound.
The problem when lifting this idea to K_t-Subgraph Hitting instead of   Vertex Cover is that, when considering an optimal solutionSthat avoids a rootv, we do not know which vertex
the solutionSwill pick inN(v). This is the reason for which we consider the more general version of the problem, namely, to encode the fact that a solution of(G,∅)avoiding
a rootvmust be a solution of(G-v,^t_v(V(G)∖{v})), where
given two disjoint setsA,B ⊆V(G),^t_A(B)= {K ∩B |K }. We also need to define the corresponding generalized notion of blocking set of an instance(G,)of(<ref>), and not only of a graphG.
Moreover, we have to keep track of the structure of, as there is no hope to bound_t(G,)as a function of(G)for an arbitrary set.
Indeed, for example, letG_ℓbe a chain of triangles of lengthℓ, as depicted in <ref>.
We have_2(G_ℓ) ≥ℓ, as if we letbe the set of top vertices of theℓtriangles, then it can be easily seen thatis a minimal blocking set ofG_ℓwith||=ℓ.
Now, take= E(G_ℓ),t=4, and observe that any solution of  instance(G_ℓ,)ofis a vertex cover ofG_ℓ, and thusis also a minimal blocking set of sizeℓfor the input(G_ℓ,)witht=4,
while(G_ℓ)=0asG_ℓisK_4-free.












We resolve this problem by proving bounds on_t(G,)only for a special type of instances that we call clean, which are pairs(G,)such that(G,)=(G).
The first main difficulty is that, when starting with a blocking setof(G,), reducing to a graphG'with(G') < (G)requires to remove the entire rootofG-N^t(G), instead of just one vertex as in the treedepth case. As|V()|may be arbitrarily large, we need to prove (see <ref>) that it is enough to “zoom” on a small number of subgraphs (pending components here), allowing us to extract (by induction) a small blocking set only in each of these subgraphs.
The second main difficulty is to ensure that we can reduce via recursion to smaller clean instances. Indeed, even if we initially consider a clean instance(G,∅), and even in the favorable case whereis just one vertexv(as in treedepth), we have to consider the case where there exists an optimal solution ofGusingv, another avoidingv, andv ∉, whereis fixed blocking set from which we try to extract a small one. However, observe that optimal solutions avoidingvare optimal solutions of(G-v,^t_v(V(G)∖{v})), and that(G-v,^t_v(V(G)∖{v}))=(G)=1+(G-v)(the last equality holds since there are optimal solutions takingv). Thus, we observe that this situation leads to a non-clean instance(G-v,^t_v(V(G)∖{v})), but “almost clean” as(G-v,^t_v(V(G)∖{v}))=(G-v)+1.
We treat these almost clean instances in <ref>, which is the main cause of the huge growth of functionβin the final bound_t(G) ≤β((G),t)given in <ref>. As this bound directly reverberates both in the running time and the size of the kernel (see <ref>, whereδ(λ,t)is dominated byβ(λ,t)for an instance(G,X)ofwhere(G-X) ≤λ), improving this bound is crucial in order to improve the kernel size. In this direction, we provide in <ref> a significantly better upper bound for minimal blocking sets of theproblem as a function ofinstead of. As the proof technique is also different, we believe that this result might be of independent interest.




 Finally, let us mention that in several earlier papers on kernelization using structural parameterizations, it was also crucial to understand the maximum size of an inclusion-minimal set with additional requirements on the solution to a vertex-deletion problem, for which no optimal solution can satisfy all additional requirements; these correspond to variations on the notion of blocking sets.  They were explored for the problems of hitting forbidden connected minors in graphs of bounded treedepth <cit.>, and for hitting cycles in graphs of bounded elimination distance to a forest <cit.>, both of which lead to super-exponential bounds in terms of the graph parameter.




§ PRELIMINARIES FOR THE ANALYSIS OF BLOCKING SETS AND THE KERNEL


In this section we provide the definitions and the preliminary results needed in the next two sections, namely in <ref> where we provide upper bounds on the sizes of minimal blocking set as a function of the considered parameter(s), and in <ref> where we formally describe our kernelization algorithm.


We start with several definitions. A graphGis biconnected if it remains connected after the removal of any vertex, and it is 2-connected if it is biconnected and has at least three vertices (hence, an edge is biconnected but not2-connected.


Given a graphGand a setof subsets ofV(G), we say that a setS ⊆V(G)is a hitting set of  if for anyZ ∈,S ∩Z ≠∅.


  Given a graph G, two disjoint sets  A,B ⊆ V(G), and an integer t ≥ 3, we denote by ^t_A(B)= {K ∩ B | K is  a t-clique in G[A ∪ B] and K ∩ A ≠∅ and K ∩ B ≠∅}.

Given a graph G and an integer t ≥ 3, we say that N ⊆ V(G) is a set of non-K_t-vertices if for any t-clique K of G, K ∩ N = ∅, and we denote by N^t(G) the inclusion-wise maximal set of non-K_t-vertices of G.



Let us introduce the following variant of.



13.5cm (for  Extended K_t- Hitting)
Input:  A pair (G,) where G is a graph and  is a set of subsets of V(G) such that for any Z ∈, 1 ≤ |Z| ≤ t-1 and G[Z] is a clique.
Objective:  Find a set S⊆ V(G) of minimum size such that for any t-clique Z of G or any Z ∈, S ∩ Z ≠∅.


We denote by^t(G,)the optimal value for(G,), or simply(G,)whentis clear from the context.
We say that(G,)is clean if(G,)=(G).






  Given a graph G and a partition  of V(G), we say that  is an additive partition of G if (G)=∑_C ∈(G[C]) (where  is the optimal value when considering the  problem).


For any set of positive realsc_1,…,c_ℓ, we useØ_c_1,…,c_ℓto denote the usual theØ-notation where the hidden multiplicative constants may depend onc_1,…,c_ℓ, and given two functionsf,g: ℕ →ℕwe denote byf=Ø^⋆(g)that there exists a polynomialp: ℕ →ℕsuch thatf(n)=Ø(p(n)·g(n)).
We denoteℕ^⋆=ℕ ∖{0}.



  
*Definitions and properties related to the parameter .


In the following observation, the setsC(v)have been defined in <ref> in <ref>.


Let G be a graph and  be a root of G.
Then V(G) is partitioned into {C(v) | v ∈ V()}.

Let u ∈ V(G) and let  P be a shortest path from u to V(). This implies that  P=(u_1,…,u_ℓ) for some ℓ∈ℕ^⋆ such that u_1 = u, u_ℓ∈ V(), and u_ℓ'∉ V() for any ℓ' < ℓ. Then, we can prove by induction starting from u_ℓ that for any u_i ∈ P, u_i ∈ C(u_ℓ).
Thus, u ∈ C(u_ℓ), and moreover, by <ref>, u ∉ C(v) for any v ≠ u_ℓ.

Let G be a graph, N be a set of non-K_t-vertices of G, and  be a root of G-N.
For any t-clique K of G, there exists v ∈ V() such that
K ⊆ C(v).

Let G' = G - N and let K be a t-clique of G. By definition of N, we know that K ⊆ V(G'). According to <ref>, V(G') is partitioned into {C(v) | v ∈ V()}, so let v ∈ V() such that K ∩ C(v) ≠∅. As by definition of a root G'[V()] is K_t-free, we cannot have K ⊆ V(). Thus, there exists u ∈ V() such that K ∩ (C(u) ∖{u}) ≠∅. If u ≠ v, then there would be an edge between (C(u) ∖{u}) and C(v), contradicting <ref>. Thus, we get that K ∩ (C(v) ∖{v}) ≠∅. By <ref> again, this implies that K ⊆ C(v).
Let G be a graph and let  be a root of G.
For any partition  of V(), we define the corresponding pending partition of  as ^p={C(Z), Z  ∈}.

Let G be a graph, N be a set of non-K_t-vertices of G, and  be a root of G-N.
For any partition  of V(), ^p ∪{N} is an additive partition of G.

For any v ∈ V(), let S_v be an optimal solution of G[C(v)], and let S = ⋃_v ∈ V()S_v.
According to <ref>, S is a solution of G, leading
to (G) = ∑_v ∈ V()(C(v))=∑_Z ∈∑_v ∈ Z(C(v)) ≤∑_Z ∈(C(Z))=∑_Z ∈(C(Z))+(G[N]).
As we also have (G) ≥∑_Z ∈(C(Z))+(G[N]), we get the desired equality.


It is worth pointing out that the following lemma applies to any graphH.


Let H be a fixed graph, not necessarily complete or connected. If G' is an induced subgraph of G, then (G') ≤(G).


We prove the statement by induction on |V(G')| + |V(G)|. Consider the defining case for the value of (G') in <ref>.

  *  If V(G') = ∅, then (G') = 0 ≤(G).
    
  *  If G' has a vertex v that is not in any copy of H, then (G') = (G'-v). Since G' - v is an induced subgraph of G on strictly fewer vertices, by induction we find that (G'-v) ≤(G).
    
  *  If G' has multiple connected components C_1, …, C_m, then each is an induced subgraph of G with strictly fewer vertices. By induction, each component C_i therefore has (G[C_i]) ≤(G). Since the value for G' is the maximum over its components, it is at most (G).
    
  *  If none of the cases above hold, then G' is connected and all its vertices belong to a copy of H. If G has a vertex v that does not belong to any copy of H, then v ∉ G' and therefore G' is an induced subgraph of G-v, from which the claim follows by induction. Similarly, if G is disconnected then G' is an induced subgraph of a connected component of G and again we may apply induction. In the remainder, we may assume that both G' and G' are connected and all their vertices occur in some copy of H. Let T be a root of G with (G - T) < (G). Define T' := T ∩ V(G'). We consider three cases.
    
  *  If T' = ∅, then G' is an induced subgraph of G - T. Hence by induction, we have (G') ≤(G - T) < (G). In the remainder, we assume T' ≠∅.
        
  *  If G'[T'] is connected, then we claim T' is a root of G'. For this we have to show that each component of G'-T' is adjacent to exactly one vertex of T'. Consider the connected components of G' - T'. We can think of these components as having been obtained from G by removing T and then removing the vertices of V(G) ∖ V(G'). Hence each component is an induced subgraph of a component of G-T. Since the latter components have at most one neighbor in T, the former also have at most one neighbor in T. Since G' is connected by assumption, each component of G'-T' has exactly one neighbor in T'.

        So T' is a root and we find (G') ≤ 1 + (G' - T') ≤ 1 + (G - T), where the last step follows from induction using the fact that G' - T' is an induced subgraph of G-T.
        
  *  If G'[T'] is disconnected, we derive a contradiction as follows. Consider two distinct vertices u,v ∈ T' which are in different connected components C_u, C_v of G[T']. Since G' is connected by assumption, there is a path from u to v in G'. Consider a minimal path P in G' which starts in C_u, ends in C_v, and has all its interior vertices outside G'[T']. Then P has at least one interior vertex w. The interior vertices of P belong to a single connected component of G' - T', and therefore also belong to a single connected component of G-T. But this component is adjacent to at least two distinct vertices of T' ⊆ T, one in C_v and one in C_u. This contradicts the fact that T is a root of G.
    
As the cases are exhaustive, this concludes the proof.














  Let G be a graph with (G) > 0.
  We say   is a -root of G if  is a root of G  and (G - V()) = (G)-1.

Let G be a graph such that N^t(G)=∅,  be a -root of G. Then, for any v ∈ V(), (G[C(v)]-v) < (G).

As for any v ∈ V(), G[C(v)]-v is a subgraph of G-V(),
<ref> implies the claimed inequality.



§ BLOCKING SETS AND THEIR PROPERTIES


In this section we provide upper bounds on the size of minimal blocking sets as a function of the parameters that we consider. In <ref> we start by defining (minimal) blocking sets and prove several useful properties. In <ref> we prove the main result of this section, namely <ref>, which provides an upper bound on minimal blocking sets as a function of the parameter. In <ref> we use a completely different technique to obtain upper bounds on the size of minimal blocking sets in graphs of bounded treedepth, which substantially improve those given in <ref> in graphs of bounded(G),t).




 §.§ Preliminaries


We start with the definitions of (minimal) blocking set that we need for our purposes.



  Given an instance (G,) of , a blocking set of (G,) is a set of subsets of V(G) such that

  
  *  for any B ∈, 1  ≤ |B| ≤ t-1, G[B] is a clique, and
  
  * (G,∪) > (G,).
  

  We define _t(G,)=max{|| such that  is a blocking set of (G,), and for any B ∈, ∖ B is not a blocking set of (G,)}, which can be rephrased as the maximum size of an inclusion-wise minimal blocking set of (G,).
  Given a graph G, we denote by _t(G)=max{_t(G,) }.
  We denote by _t^⋆(G) the maximum value, over any subgraph  G' of G,  of _t(G').
Finally, given an instance G of , a blocking set  of G  is a blocking set of (G,∅).




Note that the above definition also defines blocking sets forby setting= ∅, and that_t^⋆(G)may be strictly greater than_t(G). Informally,_t(G)is the function that we are interested in,
and_t(G,)and_t^⋆(G)are defined for technical reasons.
Note also that, even if the notion of blocking set is defined for any (not only clean) instance(G,)of,_t(G)is defined by restricting to clean instances. The reason is that our objective (see <ref>)
is to prove that there exists a functionβsuch that_t(G) ≤β((G),t), and as discussed in <ref> (see <ref>),
such a function does not exists is_twere defined without restricting to clean instances.

The following property (already used in previous results involving blocking sets, for example in <cit.>) states that small_tis equivalent to the property of extracting a small blocking set from a given large one.


 Let (G,) be an instance of  and β∈ℕ.
  Then, the two following items are equivalent:
  
  *  For any  blocking set of (G,), there exists ⊆ such that  is a blocking set of (G,) and || ≤β.
  
  * _t(G,) ≤β.
  
  To prove the forward implication,
  let  be an inclusion-wise minimal blocking set of (G,). If by contradiction || > β, there would exist ⊆ such that  is a blocking set of (G,) and || ≤β < ||, contradicting the inclusion-wise minimality of .

  TO prove the backward implication,
  Let  be a blocking set of (G,). We simply define ⊆ as an inclusion-wise minimal blocking set of (G,).

  Given an instance (G,) of , v ∈ V(G), and denoting (G,) the set of optimal solutions of (G,), we define the type of v as t^(G,)(v)=
    {v,v̅}   , 
    {v}   , 
    {v̅}   .
 Given a graphG, a setof subsets ofV(G), andV' ⊆V(G), we denote


  * ∩ V' = {B ∈| B ⊆ V'},

  * _|V' = {B ∩ V'| B ∈},

  * - V' = ∩ (V(G) ∖ V'), and

  * V()=⋃_B ∈B.


Note that given a setof subsets ofV(G), and a partition={P_i |i ∈[||]}ofV(G), we may not have= ⋃_i ∈[||](∩P_i)as anyZ ∈such thatZ ∩P_i ≠∅andZ ∩P_j ≠∅is not contained in⋃_i ∈[||](∩P_i).



 §.§ Graphs with bounded  have bounded minimal blocking sets


We start with three technical lemma whose objective is indicated beside their statement.



  Let  (G,) be an instance of  and let  be a blocking set of (G,).
  
  *  Let X^⋆⊆ V(G) such that there exists an optimal solution S^⋆ of (G,) with X^⋆⊆ S^⋆. Then
    
  * (G,)=|X^⋆|+(G- X^⋆,  - X^⋆), and
    
  * - X^⋆ is a blocking set of (G- X^⋆,  - X^⋆).
    
  *  Let v ∈ V(G) such that v̅∈ t^(G,) and {v}∉. Then
 
  * (G,)=(G-v, _|V(G)∖ v∪^t_v(V(G)∖ v)), and
    
  * _V(G)∖ v is a blocking set of (G-v, _|V(G)∖ v∪^t_v(V(G)∖ v)).
 


Let  (G,) be an instance of .
 
  * For any X ⊆ V(G), any blocking set  of (G-X, -X) and any optimal solution S^⋆ of (G,)
      such that X ⊆ S^⋆, there exists B ∈ such that S^⋆∩ B=∅, and
     
  * For any v ∈ V(G) such that {v}∉, blocking set  of (G-v, _|V(G)∖ v∪^t_v(V(G)∖ v)), and any optimal solution S^⋆ of (G,)  such that v ∉ S^⋆, there exists B ∈ such that S^⋆∩ B=∅.
 
  Proof of  <ref>.
  By the existence of S^⋆ we get (G,)=|X^⋆|+|S ∖ X^⋆|. As S ∖ X^⋆ has to intersect any t-clique of G-X^⋆ and any set of - X^⋆,
  it is a solution of (G- X^⋆,  - X^⋆), implying |S ∖ X^⋆| ≥(G- X^⋆,  - X^⋆) and (G,) ≥ |X^⋆|+  (G- X^⋆,  - X^⋆).
  As the other inequality is true by definition, we get the first property of <ref>.
  Assume now by contradiction that - X^⋆ is a not a blocking set of (G- X^⋆,  - X^⋆), implying the existence of an optimal solution S^⋆ of
  (G- X^⋆,  - X^⋆) intersecting any B ∈ - X^⋆. Let S=X^⋆∪ S^⋆. We get that S is a solution of (G,) intersecting , and
  |S|=|X^⋆|+(G- X^⋆,  - X^⋆)=(G,), a contradiction.


  In the remaining of the proof, we denote by I=(G-v, _|V(G)∖ v∪^t_v(V(G)∖ v)).

  Proof of <ref>.
  As v̅∈ t^(G,), there exists an optimal S^⋆ of (G,) with v ∉ S^⋆. This implies in particular that there is no set Z ∈ with Z={v},
  and thus that _|V(G)∖ v does not contain ∅ (as required in the definition of ).
  We get (G,)=|S^⋆∖ v|. As S^⋆∖ v has to intersect any t-clique of G-v, any set of _|V(G)∖ v (as S^⋆ intersects any Z ∈
  and v ∉ S^⋆), and any set of ^t_v(V(G)∖ v) (as S^⋆ intersects any t-clique of G and v ∉ S^⋆), we get that S^⋆ is a solution of
  I, leading to (G) ≥(I).
   As the other inequality is true by definition, we get the first property of <ref>.
   Assume now by contradiction that _V(G)∖ v is a not a blocking set of I, implying the existence of an optimal solution S^⋆ of
   I intersecting any B ∈_V(G)∖ v. As {v}∉, S^⋆ intersects all B ∈,
   and as there is no set Z ∈ with Z={v}, S^⋆ also intersects all Z ∈. Finally, S^⋆ intersects all t-cliques K ⊆ G-v by definition,
   and any t-clique K containing v, as K ∖ v ∈^t_v(V(G)∖ v). Thus, S^⋆ is a solution of (G,) intersecting , and |S^⋆|=(I)=(G,), a contradiction.



  Proof of <ref>.
  We have (G,)=|X|+|S^⋆∖ X|, and S^⋆∖ X is a solution of (G-X,-X), implying |S^⋆∖ X| ≥(G-X,-X) and (G,) ≥ |X|+(G-X,-X).
  As taking an optimal solution S^⋆ of (G-X,-X) and defining X ∪ S^⋆ is a solution of (G,), we get (G,) ≤ |X|+(G-X,-X), and thus (G,)=|X|+(G-X,-X)
  and |S^⋆∖ X|=(G-X,-X). As  is a blocking set of (G-X,-X),
there exists B ∈ such that (S^⋆∖ X) ∩ B = ∅. As B ⊆ V(G)∖ X, this implies S^⋆∩ B = ∅, and thus  is indeed a blocking set.

  Proof of <ref>.
  We have (G,)=|S^⋆|, and as v ∉ S^⋆, S^⋆ is a solution of I, implying |S^⋆| ≥(I) and (G,) ≥(I).
  As an optimal solution S^⋆ of I is also a solution of (G,) (as {v}∉), we get (G,) ≤(I), so (G,)=(I),
  and thus |S^⋆|=(I). As  is a blocking set of I, there exists B ∈ such that S^⋆∩ B = ∅.

  Let (G,) be a clean instance of .

  *  Let  be an additive partition of G. Then, for any C ∈, (G[C],∩ C) is a clean instance.
  
  *  Let v ∈ V(G) such that v ∈ t^(G,). Then, (G-v,-v) is a clean instance.
 


  Proof of <ref>.
  Suppose by contradiction that there exists C_0 ∈, such that (G[C_0],∩ C_0)>(G[C_0]).
  Let S^⋆ be an optimal solution of (G,). For any C ∈, S^⋆∩ C must a a solution of (G[C],∩ C), implying
  |S^⋆∩ C| ≥(G[C],∩ C) ≥(G[C]) for C ≠ C_0, and |S ∩ C_0|>(G[C_0]). Thus, we get |S^⋆|=∑_C ∈|S ∩ C|>∑_C ∈(G[C]).
  As (G,) is clean and  is additive, we get (G,)=(G)=∑_C ∈(G[C]), implying |S^⋆|>(G), a contradiction.

  Proof of <ref>.
  As v ∈ t^(G,), by <ref> of <ref>  with X^⋆={v}, we get (G,)=1+(G-v,-v).
  Moreover, we have (G) ≤ 1+(G-v). As (G,) is clean, we get (G-v,-v) ≤(G-v), leading to the claim as the other inequality is always true.
  
  
  
  

  Let (G,) be an instance of  such that (G,)=(G)+1 and  be a blocking set of (G,).
  There exists ⊆ such that  is a blocking set of (G,) and || ≤ 2^(t-1)_t(G)_t^⋆(G).

To prove the lemma, we will prove that there exists c ≤ 2^(t-1)_t(G), _i ⊆, G_i ⊆ G, _i ⊆ for i ∈ [c], such that

  *  for any i ∈ [c], (G_i,_i) is a clean instance,
  
  *  for any i ∈ [c], _i is a blocking set of (G_i,_i), with |_i| ≤_t(G_i), and
  
  * ⋃_i ∈ [c]_i is a blocking set of (G,).

Then, the lemma will immediately follow by setting =⋃_i ∈ [c]B_i.

  As (G,)=(G)+1, we get that  is a blocking set of (G,∅), and thus by definition there exists ⊆ (recall that  is a set of subset of vertices, and thus each Z ∈ is either entirely chosen and present in , or not in ) such that
  || ≤_t(G) and  is a blocking set of (G,∅).
  Let ^⋆ = {V() ∩ S | S}.
  Observe that for any X^⋆∈^⋆, X^⋆ is a hitting set of , and that  |^⋆| ≤ 2^(t-1)_t(G) as any B ∈ has size at most t-1.


  Let us now establish the following property p_1: for any X^⋆∈^⋆, (G,)=(G- X^⋆)+|X^⋆|.
  Let us start with (G,) ≥(G- X^⋆)+|X^⋆|. Let S be an optimal solution of (G,) such that X^⋆ = S ∩ V().
  We have (G,)=|S|=|X^⋆|+|S∖ X^⋆|. As S ∖ X^⋆ is a solution of (G-X^⋆), we get |S∖ X^⋆| ≥(G-X^⋆), and the desired inequality follows.
  Let us now prove that (G,) ≤(G- X^⋆)+|X^⋆|.
  Suppose by contradiction that (G,) ≥(G- X^⋆)+|X^⋆|+1.
  As (G,)=(G)+1, we deduce (G) ≥(G- X^⋆)+|X^⋆| and thus (G) = (G- X^⋆)+|X^⋆|.
  Let S_1 be an optimal solution of (G-X^⋆) and S = X^⋆∪ S_1. We get that |S|=(G) and X^⋆⊆ S, and thus S is
  an optimal solution of (G,), as X^⋆ is a hitting set of . This implies (G,)=(G), contradicting that
   is a blocking set of (G,∅).

  Let us now establish the following property p_2: for any X^⋆∈^⋆, (G-X^⋆,-X^⋆) is a clean instance, and there exists _X^⋆⊆ such that
  _X^⋆ is a blocking set of (G-X^⋆,-X^⋆) with |_X^⋆| ≤_t(G-X^⋆).
  Let X^⋆∈^⋆. By <ref> of <ref>, (G,)=|X^⋆|+(G-X^⋆,-X^⋆), and _X^⋆=-X^⋆ is a blocking set
  of (G-X^⋆,-X^⋆).
  According to property p_1, (G,)=(G- X^⋆)+|X^⋆|, leading to (G-X^⋆,-X^⋆)=(G-X^⋆), implying that (G-X^⋆,-X^⋆) is clean.
  By definition, there exists _X^⋆⊆_X^⋆ as claimed.

  Let us now prove the lemma. We define c= |^⋆| and {B_i}={_X^⋆| X^⋆∈^⋆}. Property p_2 above corresponds to <ref> and <ref> of the lemma.
  It remains to prove that =⋃_X^⋆∈^⋆_X^⋆ is a blocking set of (G,).
  Let S be an optimal solution of (G,), and X^⋆=S ∩ V(). <ref> (<ref>) implies that (G,)=|X^⋆|+(G-X^⋆,-X^⋆),
  and as (G,)=|X^⋆|+|S ∖ X^⋆|, we deduce that |S ∖ X^⋆|=(G-X^⋆,-X^⋆). Since _X^⋆ is a blocking set of (G-X^⋆,-X^⋆),
  there exists B ∈_X^⋆ such that (S ∖ X^⋆) ∩ B = ∅. As B ⊆ V(G)-X^⋆, it follows that S ∩ B = ∅, and thus  is indeed a blocking set.


In the next two lemmas we study how blocking sets behave when we remove one vertex from a graph.

  Let (G,) be a clean instance of , v ∈ V(G), and  be a blocking set of (G,) such that {v}∉.
 
 

  
There exists a blocking set ⊆ of (G,) with || ≤ (2^(t-1)_t(G-v)+1) ·_t^⋆(G-v).

Let I=(G-v,_V(G)∖ v∪^t_v(V(G)∖ v)).
We distinguish three cases depending on t^(G,)(v).

Case 1: Suppose t^(G,)(v)={v}.
According to <ref> (<ref>) we get that (G,)=1+(G-v,-v) and -v is a blocking set of
(G-v,-v).
According to <ref> (<ref>), (G-v,-v) is a clean instance, and thus there exists ⊆-v
such that  is a blocking set of (G-v,-v) and || ≤_t(G-v).



According to <ref> (<ref>),  is a blocking set of (G,).






Case 2: Suppose t^(G,)(v)={v̅}. Note first that this implies {v}∉.








Case 2a) Suppose I is a clean instance. By <ref> (<ref>), _|V(G)∖ v is a blocking set of I. As I is clean, and by definition of _t, there exists _0 ⊆_|V(G)∖ v such that _0 is a blocking set of I and |_0| ≤_t(G-v).
Note that we cannot define =_0, as we have to output a set ⊆, but _0 may not be a subset of  (as a set B ∈ containing v becomes B∖ v in _|V(G)∖ v). Thus, we rather define  =(_0,v,), where (_0,v,)=⋃_B ∈_0f(B), where f(B) is any B' ∈ such that B' ∖{v} = B.
Let us prove that  is a blocking set of (G,).
Let S be an optimal solution of (G,). As t^(G,)(v)={v̅}, v ∉ S.
As v ∉, according to <ref> (<ref>), there exists B ∈_0 such that S ∩ B = ∅.
As S intersects all the K_t's containing v, we know that S ∩B̃≠∅ for any
B̃∈^t_v(V(G)∖ v). This implies that B ∉^t_v(V(G)∖ v), and thus either B'=B or B'=B∪ v is in . As v ∉ S, we get S ∩ B' = ∅, implying that  is indeed a blocking set. Moreover, ||=|_0|≤_t(G-v) ≤_t^⋆(G-v) and thus is smaller that the required size.


Case 2b) Suppose I is not a clean instance.
As (G)≤ 1+(G-v) and (G)=(G,)=(I), the last equality coming from <ref> (<ref>), we get that (I) ≤ 1+(G-v), and thus (I)=1+(G-v) as I is not clean.
Thus, we can apply <ref> on I and _|V(G)∖ v, and thus there exists
_0 ⊆ such that _0 is a blocking set of I, and |_0| ≤ 2^(t-1)_t(G-v)_t^⋆(G-v).
In this case, we define =(_0,v,). For the same arguments than in case 2a) we get that  is a blocking set, whose size is upper-bounded by the claimed bound.


Case 3: Suppose t^(G,)(v)={v,v̅}. Note first that this implies {v}∉.
In this case we use both small blocking sets defined in cases 1) and 2b).
As in case 1), according to <ref> (<ref>) we get that (G,)=1+(G-v,-v) and -v is a blocking set of
(G-v,-v).
According to <ref> (<ref>), (G-v,-v) is a clean instance, and thus there exists _1 ⊆-v
such that _1 is a blocking set of (G-v,-v) and |_1| ≤_t(G-v).






According to <ref> (<ref>),  we get that (G,)=(I) and _|V(G)∖ v is a blocking set of I.
As v∈ t^(G,)(v) and (G,) is clean we get (G)=(G,)=1+(G-v,-v) ≥ 1+(G-v), leading to (G)= 1+(G-v).
On the other hand, we also have (G,)=(I), and we get that (I) = 1+(G-v).
Thus, we can apply <ref> on I and _|V(G)∖ v, and thus there exists
_0 ⊆ such that _0 is a blocking set of I, and |_0| ≤ 2^(t-1)_t(G-v)_t^⋆(G-v).
Let us now conclude the proof of the lemma by showing that =(_0,v,) ∪_1 satisfies the claim.
The bound of || is immediate, and thus it remains to prove that  is a blocking set of (G,).
Let S be an optimal solution of (G,).
If v ∈ S, then according to <ref> (<ref>), there exists B ∈_1 such that S ∩ B = ∅ and we are done.
If v ∉ S, then as v ∉, according to <ref> (<ref>),  there exists B ∈_0 such that S ∩ B = ∅.
By the same arguments than in case 2a) we get that there exists B' ∈(_0,v,) such that S ∩ B' = ∅, and thus that  is a blocking set of (G,).

  Let (G,) be a clean instance of , v ∈ V(G),
  and  a blocking set of (G,) such that {v}∈.
  Let ' such that = ' ∪{v}.
There exists ⊆' such that ∪{v} is a blocking set of (G,) with || ≤_t(G-v).

If t^(G,)(v)={v̅}, then =∅ satisfies the claim.
Otherwise, as v ∈ t^(G,)(v), according to <ref> (<ref>), we get that (G,)=1+(G-v,-v) and ' is a blocking set of
(G-v,-v).
According to <ref> (<ref>), (G-v,-v) is a clean instance, and thus there exists ⊆-v
such that  is a blocking set of (G-v,-v) and || ≤_t(G-v).
Let us prove that ∪{v} is a blocking set of (G,).
Let S be an optimal solution of (G,). If v ∉ S, we are done. Otherwise, according to <ref> (<ref>),
there exists B∈ such that S ∩ B = ∅, concluding the proof.


The next lemma shows how, given a blocking set, we can “zoom” in a few pending components. It relies on <ref> that will be proved in <ref>.

  Let (G,) be a clean instance of . Let  be a  root of G-N^t(G) (which exists by <ref>).
  Suppose that N^t(G)=∅ and that G is connected, and let = {T}.
  
  *  Let  be a blocking set of (G,). Then, either
  
  *  there exists v ∈ T such that ∩ C(v) is a blocking set of (G[C(v)],∩ C(v)), or
  
  *  there exists Z ∈∪ such that Z ⊆ T, and for any v ∈ Z, (∩ C(v)) ∪{v} is a blocking set of (G[C(v)],∩ C(v)).
  
  *  For any v ∈ T and  blocking set  of (G[C(v)],∩ C(v)),  is a blocking set of (G,).

  *  For any Z ∈∪ such that Z ⊆ T, and for any blocking sets _v of (G[C(v)],∩ C(v)) (with _v='_v ∪{v}) for any v ∈ Z, it holds that
  
  *  if Z ∈, then Z ∪⋃_v ∈ Z'_v is a blocking set of (G,), and
  
  *  if Z ∈, then ⋃_v ∈ Z'_v is a blocking set of (G,).
  
Note first that using the trivial partition ={v | v ∈ T}, <ref> implies that the pending partition ^P={C(v) | v ∈ T} is additive,
  and <ref> implies that for any v ∈ T, (G[C(v)],∩ C(v)) is clean.
  Thus, we get property p_1: (G,)=(G)=∑_v ∈ T(G[C(v)])=∑_v ∈ T(G[C(v)],∩ C(v)).

  Proof of <ref>.
  Let us proceed by contradiction. For any Z ∈∪ such that Z ⊆ T, let v_Z ∈ Z and S_v_Z such that S_Z is an optimal solution of (G[C(v_Z)],∩ C(v_Z))
  intersecting all sets of (∩ C(v_Z)) ∪{v_Z} (implying that v_Z ∈ S_Z).
  Let V_1 = {v_Z | Z ∈∪} and V_2 = T ∖ V_1.
  For any v ∈ V_2, let S_v be an optimal solution of (G[C(v_Z)],∩ C(v_Z)) intersecting all sets of ∩ C(v).
  Let S = ⋃_v ∈ TS_v. Let us now prove that S is an optimal solution of (G,) intersecting all sets of , which is a contradiction to the hypothesis that  is a blocking set of (G,).

  First, we get |S|=∑_v ∈ T(G[C(v)],∩ C(v))=(G) = (G,) by property p_1.
  Moreover, for any t-clique K in G, <ref> implies that there exists v ∈ T such that K ⊆ C(v), and thus S_v ∩ K ≠∅.
  Let us now verify that for any Z ∈∪, S ∩ Z ≠∅.
  Let Z ∈∪. If there exists v ∈ T such that Z ⊆ C(v), then Z belongs to ∩ C(v) or ∩ C(v), and thus S_v ∩ Z ≠∅.
  Otherwise, <ref> implies that Z ⊆ T as G[Z] is a clique. Thus, as v_Z ∈ S_v_Z, we get S_v_Z∩ Z ≠∅.

  Before proving the last two items, let us prove property p_2: for any  optimal solution S of (G,), it holds that for any v ∈ T,  |S ∩ C(v)| is an optimal solution of (G[C(v)],∩ C(v)).
  Let S be an optimal solution of (G,). As by property p_1 we have (G,)=∑_v ∈ T(G[C(v)],∩ C(v)), and as for any v ∈ T, S ∩ C(v) is a solution of (G[C(v)],∩ C(v)),
  and thus |S ∩ C(v)| ≥(G[C(v)],∩ C(v)), we get that for any v ∈ T,  S ∩ C(v) is an optimal solution of (G[C(v)],∩ C(v)).

  Proof of <ref>.
  Let S be an optimal solution of (G,). By property p_2, S ∩ C(v) is an optimal solution of (G[C(v)],∩ C(v)), and thus, there exists B ∈ such that (S ∩ C(v)) ∩ B = ∅, implying S ∩ B = ∅.

  Proof of <ref>.
  Let ' = ⋃_v ∈ Z'_v.
  Let S be an optimal solution of (G,). Suppose first that Z ∈. If S ∩ Z = ∅ then we are done, otherwise let v ∈ S ∩ Z.
  By property p_2, S ∩ C(v) is an optimal solution of (G[C(v)],∩ C(v)), and thus, as _v is a blocking set of (G[C(v)],∩ C(v)), there exists B ∈_v
  such that (S ∩ C(v)) ∩ B = S ∩ B = ∅. As v ∈ S, we obtain that B ∈'_v, as required.
  Suppose now that Z ∈. As S must intersect , we again consider v ∈ S ∩ Z, and we can follow the same arguments.




The three next “cleaning” lemmas will help us in the main result of this section to reduce the proof to the most interesting case.

  Let (G,) a clean instance of .
  Let ' = {Z ∖ N^t(G) | Z ∈}. Then, (G,')  is well-defined (that is, ∅∉') and clean, and _t(G,) ≤_t(G,').

  Let S be an optimal solution of (G,). As (G,) is clean, we get |S|=(G,)=(G).
  By definition of N^t(G), no optimal solution of G contains a vertex in N^t(G), and thus S ∩ N^t(G) = ∅.
  As for any Z ∈, S ∩ Z ≠∅, this implies that ∅∉', and that for any Z ∈', S ∩ Z ≠∅.
  Thus, S is also a solution of (G,'), leading to (G,') ≤ |S|=(G,). As the other inequality is true by definition, we get that (G,')=(G,)=(G),
  and thus (G,') is clean.

  Let us now prove _t(G,) ≤_t(G,') using Property <ref>.
  Let  be a blocking set of (G,). Note that  is also a blocking set of (G,'). Indeed, if there existed an optimal solution S of (G,') intersecting all sets of ,
  then S is also a solution of (G,), and |S|=(G,) by the previous equalities, leading to a contradiction.
  Thus, as  is a blocking set of (G,') and (G,') is clean, there exists ⊆ such that || ≤_t(G,') and  is a blocking set of (G,).

  Let (G,) a clean instance of  and   such that for any Z ∈, Z ⊆ V(G) ∖ N^t(G).
  Then, (G-N^t(G),) is clean, and _t(G,) ≤_t(G-N^t(G),).

  Note that, as for any Z ∈, Z ⊆ V(G) ∖ N^t(G), (G-N^t(G),) is well-defined. By definition of N^t(G) and as (G,) is clean,
  we have property p_1: (G-N^t(G),)=(G,)=(G)=(G-N^t(G)).
  This property implies that (G-N^t(G),) is clean.
  We also have property p_2: for any S, S is an optimal solution of (G,) if and only if S is an optimal solution of (G-N^t(G),).


  Let us now prove _t(G,) ≤_t(G-N^t(G),) using Property <ref>.
  Let  be a blocking set of (G,).

  If there exists B ∈ such that B ⊆ N^t(G), then let us prove that ={B} is a blocking set.
  Let S be an optimal solution of (G,). By definition of N^t(G), and as for any Z ∈, Z ⊆ V(G) ∖ N^t(G), we get S ∩ N^t(G) = ∅, implying S ∩ B = ∅.

  Otherwise, we can define ' = {B ∖ N^t(G) | B ∈} while ensuring that ∅∉'.
  Let us show that ' is a blocking set of (G-N^t(G),). Let S be an optimal solution of (G-N^t(G),). By property p_2, S is also an optimal solution of (G,),
  and thus there exists B ∈ such that S ∩ B = ∅, implying (B ∖ N^t(G)) ∩ S = ∅, and thus that ' is a blocking set of
  (G-N^t(G),). As (G-N^t(G),) is clean, there exists a blocking set ' ⊆' of (G-N^t(G),) such that |'| ≤_t(G-N^t(G),).
  We define =(',N^t(G),), where (',N^t(G),)=⋃_B ∈'f(B), where f(B) is any B' ∈ such that B' ∖ N^t(G) = B.
  Let us finally check that  is a blocking set of (G,). Let S be an optimal solution of (G,). By property p_2, S is an optimal solution of (G-N^t(G),), and
  thus there exists B ∈' such that S ∩ B = ∅. As S ∩ N^t(G) = ∅, we also have S ∩ f(B)= ∅.

  Let (G,) be a clean instance of .
  Suppose N^t(G)=∅, and let {C_i | i ∈ [c]} be the connected components of G.
  Then, _t(G,) ≤max_i ∈ [c]_t(G[C_i],∩ C_i).

Let us prove the inequality using Property <ref>, and let us consider  a blocking set  of (G,).
As the partition given by the connected components is additive, <ref> implies that for any i ∈ [c], (G[C_i], ∩ C_i) is clean. Moreover,
as  are cliques, we get that = ⋃_i ∈ [c](∩ C_i), and thus by additivity of the partition we get property p_0:
for any set of vertices S, S is an optimal solution of (G,) if and only if S ∩ C_i is an optimal solution of (G[C_i],∩ C_i) for any i ∈ [c].


Let us first prove that there exists i ∈ [c] such that ∩ C_i is a blocking set of (G[C_i], ∩ C_i). Suppose by contradiction that there is no such i, and for any i ∈ [c] let S_i be an optimal solution of (G[C_i],∩ C_i) intersecting all sets of ∩ C_i, and S = ⋃_i ∈ [c]S_i. By property p_0, we get that S is an optimal solution of (G,).
As all sets of  are cliques, we get that = ⋃_i ∈ [c](∩ C_i), implying that S also intersects all sets of . This contradicts the fact that  is a blocking set of (G,).

Thus, there exists i ∈ [c] such that ∩ C_i is a blocking set of (G[C_i], ∩ C_i), and as (G[C_i], ∩ C_i) is clean, there exists ⊆∩ C_i such that  is a blocking set of (G[C_i], ∩ C_i), and |B| ≤_t(G[C_i], ∩ C_i). As  has the claimed size, in only remains to check that  is a blocking set of (G,). Let S be an optimal solution of (G,).
By property p_0, S ∩ C_i is an optimal solution of (G[C_i], ∩ C_i),
implying that there exists Z ∈B such that (S ∩ C_i) ∩ Z = ∅, implying also that S ∩ Z = ∅, and thus that B is a blocking set of (G,).


We are now ready to prove the main theorem of this section.
[<ref> restated]
  For any graph G  and any integer t ≥ 3, we have _t(G) ≤β((G),t), where β(x,t)=
^2^t2^t2^⋯^t_x times
(i.e.,β(1)=2^t, β(2)=2^t2^t, etc.)

  For the sake of readability, let us consider that t is fixed, and let f:ℕ→ℕ such that f(0)=1, and for any integer x ≥ 1, f(x)=(2^(t-1)f(x-1)+1)f(x-1).
  The proof is by induction on (G). If (G)=0, G is a (possibly empty) collection of K_t-free components, implying (G)=0,
  and thus that for any clean instance (G,), = ∅, and thus that any inclusion-wise minimal blocking set of a clean instance (G,∅) has at most one element.

  Let us now turn to the induction case.
  Let (G,) be a clean instance of  and  be a blocking set of (G,).
  Let  be a  root of G-N^t(G) (which exists according to <ref>). Let us prove that _t(G,) ≤ f((G)).
  By Lemmas <ref>, <ref>, and <ref>, we can assume that N^t(G)=∅ and that G is connected.
  This implies that ={T} for some subset T ⊆ V(G).
  By <ref> (<ref>), we get the following two cases:
 
  *  There exists v ∈ T such that ∩ C(v) is a blocking set of (G[C(v)],∩ C(v)).
  
  *  There exists Z ∈∪ such that Z ⊆ T, and for any v ∈ Z, (∩ C(v)) ∪{v} is a blocking set of (G[C(v)],∩ C(v)).
  


 Note first that using the trivial partition ={v | v ∈ T}, <ref> implies that the pending partition ^P={C(v) | v ∈ T} is additive,
 and <ref> implies that for any v ∈ T, (G[C(v)],∩ C(v)) is clean.
 Moreover, by <ref>, for any v ∈ T, (G[C(v)]-v) ≤(G)-1.

 

    Case 1.
 If v ∉, then by <ref>, there exists a blocking set _v ⊆∩ C(v) of (G[C(v),∩ C(v))
   satisfying that |_v| ≤ (2^(t-1)_t(G[C(v)]-v)+1) _t^⋆(G[C(v)]-v) ≤ (2^(t-1)f((G)-1)+1) f((G)-1) = f((G)).
   Moreover, by <ref> (<ref>),  _v is also a blocking set of (G,).

 If v ∈, then by <ref>, there exists a blocking set _v ∪{v}⊆∩ C(v) of (G[C(v),∩ C(v))
   with |_v ∪{v}| ≤_t(G[C(v)]-v)+1 ≤ f((G)-1)+1 ≤ f((G)).
   Again, by <ref> (<ref>),  _v ∪{v} is also a blocking set of (G,).

   

    Case 2.
 Since for any  v ∈ Z,  (∩ C(v)) ∪{v} is a blocking set of (G[C(v)],∩ C(v)), by <ref>,
   there exists a blocking set _v ∪{v} of (G[C(v),∩ C(v)) where _v ⊆ (∩ C(v)) and |_v| ≤_t(G[C(v)]-v) ≤ f((G)-1).
     If Z ∈, then by <ref> (<ref>), Z ∪⋃_v ∈ Z_v is a blocking set of (G,) of size at most (t-1)f((G)-1)+1 ≤ f((G)).
     Otherwise, Z ∈, and by <ref> (<ref>), ⋃_v ∈ Z_v is a blocking set of (G,) of size at most (t-1)f((G)-1) ≤ f((G)).

     Thus, we obtained that _t(G) ≤ f((G)).
     Let us prove that f(x) ≤β(x).
     The result is clear for x=1. 
      For x ≥ 2, f(x) ≤ (2^(t-1)f(x-1)+1)f(x-1) ≤ (2^(t-1)f(x-1)+1)f(x-1) ≤ 2^(t-1)f(x-1)+1+log(f(x-1)), and as 1+log(y) ≤ y for y ≥ 3 and f(x-1) ≥ f(1) ≥ 3, we get f(x) ≤ 2^tf(x-1)≤ 2^tβ(x-1,t)=β(x,t).


 §.§ Minimal blocking sets in graphs of bounded treedepth


In this subsection we obtain upper bounds on the size of minimal blocking sets in graphs of bounded treedepth, which substantially improve those given in <ref> in graphs of bounded(G).

For the following argument, recall that an elimination forest of a graphGis a rooted treeTon vertex setV(G)such that for each edge{u,v} ∈E(G), vertexuis an ancestor of vertexvinT, or vice versa. For a nodexin an elimination forestT, we useanc_T(x)to denote the set of ancestors ofx, which includesxitself. It is well-known that the treedepth of a connected graphGis equal to the minimum, over all elimination forestsTofG, of the maximum number of nodes on a root-to-leaf path inT. For a nodexin an elimination forestTof a graphG, we useG_xto denote the subgraph ofGinduced by the descendants ofxinT.


Observe that, unlike <ref>, the following bound does not depend ont.

For any graph G and integer t ≥ 3, _t(G) ≤(G)^(G)· 2^(G)^2.

Let G be a graph of treedepth η and let  be a set of cliques in G, each of size less than t.
Let  be a blocking set of G, and let us show that there exists a subset ⊆ of size at most η^η· 2^η^2 such that
 is still a blocking set of G.

Let us recall that given a graph G and  a set of cliques in G, we denote by (G) (resp. (G,)) the minimum size of a subset of vertices intersecting all t-cliques (resp. and all sets in ).

We may assume that G is connected, since a blocking set forms a blocking set for at least one connected component, and any blocking set for a component is a blocking set for G. Let ⊆ be an inclusion-minimal subset such that (G,) >  (G). Consider an optimal elimination forest T of G, of depth η. We now prove the following:


For each node x∈ V(T), there are at most η· 2^η distinct child subtrees of x that contain a vertex of V().

Assume for a contradiction that there exists x∈ V(T) such that more than η· 2^η distinct subtrees rooted at children c_1,…, c_m of x contain a vertex u_1,…, u_m of V(), and let B_1,…, B_m ∈ such that u_i∈ B_i for each i. Note that B_i ≠ B_j for i ≠ j because the subgraphs in ⊇ are cliques and a clique cannot contain vertices from two incomparable subtrees of an elimination forest

Since  is inclusion-minimal with respect to (G,) >  (G), we have (G,∖{B_i}) =  (G) for each i, meaning there is a vertex set S_i of size (G) which hits all t-cliques in G and all graphs ∖{B_i}.

Since m > η· 2^η, there are more than η children c_i for which the corresponding solutions S_i make exactly the same selection from the ancestors anc_T(x) of x in T. Let c_1,…, c_η+1 be such children, for which there exists a set C of ancestors of x such that S_i ∩anc_T (x) = C for each i. Consider the solution S_1. For at least one of the η remaining involved children c_2,…, c_η+1, we have |S_1 ∩ V(G_c_i)| =  (G_c_i), where G_c_i is the subgraph of G induced by c_i and its descendants.

The reason for this is as follows: S_1 trivially contains at least opt_t(G_c_i) vertices from G_c_i for each 2 ≤ i ≤η+1. If it picks strictly more in each of them, then (since |anc_T(x)| < η since x itself has a child and the number of vertices on a root-to-leaf path is η) there is a solution for K_t- Subgraph Hitting which is smaller than |S_1| = (G): replace the solutions inside those η children by locally optimal solutions, and then add x and all its ancestors. Since all cliques of G appear on a single root-to-leaf path of any elimination forest, the replacement gives a valid solution whose size is strictly smaller than |S_1|; but this contradicts |S_1| = (G). Hence there is indeed a child c_i with i>1 for which S_i ∩ G_c_j has size (G_c_j).

Now consider S^* := (S_j ∖ V(G_c_j)) ∪ (S_1 ∩ V(G_c_j)). In other words, we take the solution S_j, but replace what it chooses from G_c_j with how S_1 chooses from G_c_j. This cannot increase the size since S_j pays at least (G_c_j) inside G_c_j and S_1 pays (G_c_j). This also does not cause any K_t to become unhit. Each K_t is on a single root-to-leaf path of the decomposition. The new solution S^* still hits all of them, since for each root-to-leaf path, the choices S^* makes on that path agree with the choices made by some valid solution (either S_1 or S_j) on that path; here we exploit that S_1 and S_j agree on their choices from the ancestors of x.

Now comes the key point. By assumption, S_1 hits all of  except B_1, so in particular it hits B_j. We knew that S_j hits all of  except for B_j, and that B_j contains a vertex in the child subtree rooted at c_j; hence the entire clique B_j is contained in the subtree of c_j together with its ancestors. From this, it is straightforward to verify that replacing what S_j does inside G_c_j with what S_1 does there, yields a solution that hits all of ; but that is a contradiction to the choice of  since |S^*| = (G).


The claim proves the lemma, because it effectively shows that the vertices of V() and their ancestors form a subtree of T of depth η and branching factor η· 2^η, which proves the total number of vertices is bounded by η^η· 2^η^2; this clearly bounds the number of subgraphs in .


§ A POLYNOMIAL KERNEL FOR Λ



















In this section we provide a polynomial kernel forλ. 
 Recall that given any input(G,)of theproblem, we use the notation(G,)to denote the minimum size of a vertex subset ofGintersecting allt-cliques ofGand all the sets in.
Let us first define the crucial notion of chunk. Informally, a chunk is a small part ofXthat is a small subset ofXwhich is candidate to be avoided by a solution.

  Given an input (G,X) of ^λ, a chunk is a set X' ⊆ X such that |X'| ≤ c(λ,t), where c(λ,t)=(t-1)β(λ,t) and β is defined in <ref>, and X' contains no t-clique.
 The set of chunks of (G,X) is denoted by .


We are now ready to define the notion of conflict.


  Given a graph G and two disjoint subsets of vertices S_1,S_2 such that S_1 does not contain a t-clique, we define the conflict function as ^t_S_1(S_2)=(G[S_2],^t_S_1(S_2))-(G[S_2]).







Informally,^t_S_1(S_2)corresponds to the number of vertices we have to overpay inS_2when we do not take any vertex fromS_1into the solution, compared to(G[S_2]).





The following is a corollary of  <ref> presented in <ref>.

Given a graph G, S_2 ⊆ V(G) such that (G[S_2]) ≤λ, and S_1 ⊆ V(G) disjoint from S_2 such that S_1 does not contain a t-clique, we can compute if ^t_S_1(S_2)>0 in time p_0^(λ,t)(n), where n=|V(G)| and p_0^(λ,t) is defined in <ref>.


The following lemma, saying that in a graph with small_tit is possible, given any setS_1inducing some conflict, to extract a small subsetS_1that still “certifies” the conflict, has also been used in previous work, for example in <cit.>. However, as the problem considered here is different, we prefer to include the proof for the sake of completeness.


  Let G be a graph, let S_1,S_2 be two disjoint subsets of vertices of G such that S_1 does not contain a t-clique, and let β be an integer such that _t(G[S_2]) ≤β.
  Then, ^t_S_1(S_2)=0 if and only if for any subset S_1 ⊆ S_1 such that |S_1| ≤ (t-1)β, ^t_S_1(S_2)=0.

The forward implication holds as for any subset S_1 ⊆ S_1, we have that (G[S_2],^t_S_1(S_2)) ≤(G[S_2],^t_S_1(S_2)) = (G[S_2]).
  Let us prove the backward implication by contrapositive.
  Suppose that ^t_S_1(S_2)>0, implying that (G[S_2],^t_S_1(S_2)) > (G[S_2]) and thus that ^t_S_1(S_2) is a blocking set of G[S_2].
  As _t(G[S_2]) ≤β, by Property <ref> there exists ⊆^t_S_1(S_2) such that (G[S_2],) >(G[S_2]) and || ≤β.
  Note that for any Z ∈, there exists f(Z) ⊆ S_1 such that Z ∪ f(Z) is a t-clique.
  Thus, we define S_1 =⋃_Z ∈f(Z), and we have that ⊆^t_S_1(S_2), implying
  (G[S_2],^t_S_1(S_2))>(G[S_2],) > (G[S_2]), and thus that ^t_S_1(S_2)>0.
  Moreover, |S_1| ≤ ||(t-1) ≤ (t-1)β.



 
 
 



 Let(G,X)be an input of^λ, letNbe a set of non-K_t-vertices ofG-X,  and letbe a root ofG-X-N.
For any={(V_i,N_i) |i ∈[||]}, where fori ∈[||],V_i ⊆V()andN_i ⊆N, we denote byN^=⋃_(V_iN_i) ∈N_iand^=⋃_(V_iN_i) ∈V_i.

Let us start by defining the following marking algorithm, which will be used as a subroutine in the kernelization algorithm. See <ref> for an illustration.


  Let (G,X) be an input of ^λ.
  We define an algorithm  mark(,N,X',c,N',M') which returns a subset of vertices of V(), and whose parameters are such that

  * N is a set of non-K_t-vertices of G-X and  is a root of G-X-N,
  
  * X' ∈,
  
  * X' ∪ N' does not contain a t-clique ,
     
  * N' ⊆ N such that |N'| ≤ c(λ,t)-c,
    
  * c is an integer with -1 ≤ c ≤ c(λ,t), and
    
  * M' ⊆ V(), |M'| ≤ t-2, and M' is a clique.
  

  Given such a tuple (,N,X',c,N',M'), we say that a pair (V_i,N_i) is a (,N,X',c,N',M')-part if

  
  * N_i ⊆ N ∖ N', |N_i| ≤ c, X' ∪ N' ∪ N_i does not contain a t-clique, and
  
  * V_i ⊆ V(), |V_i ∪ M'| ≤ t-1, and V_i ∪ M' is clique, and
  
  * ^t_X'(M' ∪ C(V_i) ∪ N' ∪ N_i) > 0

  We are now ready to define  mark(,N,X',c,N',M'):

  
  *  If c=-1, return ∅.
  
  *  Otherwise:
    
  *  Construct a packing  (meaning that V_i's are pairwise disjoint and N_i's are pairwise disjoint) of (,N,X',c,N',M')-parts (V_i,N_i) until ||=|X|+1 or  is inclusion-wise maximal.
    
  *  If || = |X|+1, return ^.
    
  *  Otherwise, return ⋃_g ∈ N^ mark(,N,X',c-1,N' ∪{g},M') ∪^.
    

For any X' ∈ and M' ⊆ V() such that |M'| ≤ t-2 and M' is a clique, let 
(,N,X',M')= mark(,N,X',c(λ,t),∅,M').

Any recursive call of the above algorithm satisfies the required condition as, in particular, for any g ∈ N^, X' ∪ N' ∪{g}⊆ X' ∪ N' ∪ N_i for some (,N,X',c,N',M')-part
(V_i,N_i), and by definition of a part, X' ∪ N' ∪ N_i does not contain a t-clique.


In the following lemma we prove several properties of the above marking algorithm. Informally, <ref> of <ref> tells us that if a part(V_i,N_i)has not been marked, then
we have marked|X|+1other parts.


  Let (G,X) be an input of ^λ, N be a set of non-K_t-vertices of G-X, and  be a root of G-X-N.
  Let X' ∈ and M' ⊆ V() such that |M'| ≤ t-2 and M' is a clique.
 Then,
  
  * (,N,X',M') runs in time p_1^(λ,t)(n)=(n^t+c(λ,t)+Ø(1)c(λ,t)p_0^(λ,t)(n))^c(λ,t)+1, where p_0^(λ,t) is defined in <ref>.
    
  * |(,N,X',M')| ≤ p^λ(|X|) where p_2^(λ,t)(|X|)=2t|X|(2c(λ,t)|X|)^(c(λ,t)+1).
    
  *  If there is a (,N,X',c(λ,t),∅,M')-part (V_i,N_i) such that  V_i ∩(,N,X',M') = ∅,
      then there exists N' ⊆ N_i, and a packing ^⋆ of (,N,X',c(λ,t)-|N'|,N',M')-parts such that |^⋆|=|X|+1 and ^^⋆⊆(,N,X',M').

  
  Proof of <ref>.
  For any c ≥ 0, let f_1(c)=(α_2n^t+c(λ,t)+α_1+1c(λ,t)p_0^(λ,t)(n))^c+1 where α_1 and α_2 are constants defined later.
  Let us prove by induction on c ≥ 0 that for any input  (,N,X',c,Ñ,M'),  mark(,N,X',c,Ñ,M') runs in at most f_1(c) steps.
  Observe that for any input, a naive implementation of  mark consists in listing in Ø(n^t+c(λ,t)) all possible subsets V_i and N_i with properties <ref> and <ref>,
  checking for each of them in time p_0^(λ,t)(n) using <ref> if <ref> holds, and then given the set of all parts, construct in time Ø(n^α_1) a maximal packing (where α_1 is a constant).
  Thus, property is true for c=0, for any c > 0, as  mark makes |N^| ≤ |X|c ≤ nc(λ,t) recursive calls, we get that  mark(,N,X',c,Ñ,M') runs in time Ø(n^t+c(λ,t)+α_1p_0^(λ,t)(n)) · nc(λ,t) · f_1(c-1). Choosing α_2 as the multiplicative factor of the previous Ø-notation, we get that  mark(,N,X',c,Ñ,M') runs in time f_1(c).

  Proof of <ref>.
  For any c ≥ 0, let f_2(c)=t∑_ℓ=0^c c(λ,t)^ℓ(|X|+1)^ℓ+1.
  Let us prove by induction on c ≥ 0 that for any input  (,N,X',c,Ñ,M') of  mark, | mark(,N,X',c,Ñ,M')| ≤ f_2(c).
  For c=0, | mark(,N,X',0,Ñ,M')|=|^| ≤ (|X|+1)t.
  Suppose now that the claim is true for c-1 and let us prove it for c.
  Let (,N,X',c,Ñ,M') be an input of  mark. As |N^| ≤ |X|c ≤ (|X|+1)c(λ,t), and using induction hypothesis, we have | mark(,N,X',c,Ñ,M')| ≤ (|X|+1)t+(|X|+1)c(λ,t)f_2(c-1)=f_2(c). As f_2(c) ≤ t(|X|+1)(c(λ,t)(|X|+1))^c+1, we get the claimed bound.

  Proof of <ref>.
  Let us first prove the following property p_1: for any input (,N,X',c,Ñ,M') of  mark (thus satisfying the requirements in <ref>) where c ≥ 0,
  if there exists a (,N,X',c,Ñ,M')-part (V_i,N_i) such that V_i ∩ mark(,N,X',c,Ñ,M') = ∅, then there exists N^⋆⊆ N and ^⋆ such that

  
  * (,N,X',c-|N^⋆|,Ñ∪ N^⋆,M') satisfies the condition required by an input of  mark, and
  
  * ^⋆ is a packing of (,N,X',c-|N^⋆|,Ñ∪ N^⋆,M')-parts with |^⋆|=|X|+1 and ^^⋆⊆ mark(,N,X',c,Ñ,M').
  

  We prove this property by induction on c.
  Consider first the case where c=0.
  Suppose there is a (,N,X',0,Ñ,M')-part (V_i,N_i) such that V_i ∩ mark(,N,X',0,Ñ,M') = ∅.
  Let  be the packing of (,N,X',0,Ñ,M')-parts found by  mark(,N,X',0,Ñ,M'). Let us prove that ^⋆= and N^⋆=∅ satisfy the required properties.
  The first one is trivial. Let us prove that ||=|X|+1, implying the second property. Suppose by contradiction that ||≤ |X|. As (V_i,N_i)
  is a (,N,X',0,Ñ,M')-part such that V_i ∩ mark(,N,X',0,Ñ,M') = ∅, it implies that V_i ∩^ = ∅, implying that for any (V_j,N_j) ∈,
  V_i ∩ V_j = ∅. However, as c=0, all the N_j are empty, and thus for any (V_j,N_j) ∈, we have V_j ∩ V_i = ∅ and N_j ∩ N_i = ∅,
  contradicting the maximality of .

  Suppose now that the claim is true for c-1 and let us prove it for c.
  Suppose there exists a (,N,X',c,Ñ,M')-part (V_i,N_i) such that V_i ∩ mark(,N,X',c,Ñ,M') = ∅.
  Let  be the packing of (,N,X',c,Ñ,M')-parts found by  mark(,N,X',c,Ñ,M').
  If ||=|X|+1, then ^⋆= and N^⋆=∅ satisfy the claim.
  Let us now assume that || ≤ |X|. As V_i ∩ mark(,N,X',c,Ñ,M') = ∅, this implies that for any (V_j,N_j) ∈, V_j ∩ V_i = ∅.
  Thus, as (V_i,N_i) was not added in the maximal packing , it implies that there exists (V_j,N_j) ∈ such that N_j ∩ N_i ≠∅.
  Let g ∈ N_j ∩ N_i. Observe that  mark(,N,X',c-1,Ñ∪{g},M') ⊆ mark(,N,X',c,Ñ,M'), and that (V_i, N_i ∖{g}) is a (,N,X',c-1,Ñ∪{g},M')-part
  such that V_i ∩ mark(,N,X',c-1,Ñ∪{g},M') = ∅. Thus, by induction hypothesis, there exists N^⋆_r ⊆ N and  ^⋆_r such that

  
  * (,N,X',c-1-|N^⋆_r|,Ñ∪{g}∪ N^⋆_r,M') satisfies the condition required by a input of  mark, and
  
  * ^⋆_r is a packing of (,N,X',c-1-|N^⋆_r|,Ñ∪{g}∪ N^⋆_r,M')-parts with |^⋆_r|=|X|+1 and ^^⋆_r⊆ mark(,N,X',c-1,Ñ∪{g},M').
  

  Let us check that N^⋆ = N^⋆_r ∪{g} and ^⋆ = ^⋆_r satisfy the two required conditions.
  For the first one, the only non-trivial one is to prove that X' ∪Ñ∪ N^⋆ does not contain a t-clique.
  As (,N,X',c-1-|N^⋆_r|,Ñ∪{g}∪ N^⋆_r,M') satisfies the condition required by an input of  mark, we get that X' ∪ (Ñ∪{g}∪ N^⋆_r) does not contain a t-clique,
  and X' ∪ (Ñ∪{g}∪ N^⋆_r) = X' ∪Ñ∪ N^⋆.
  The second one is direct as any (,N,X',c-1-|N^⋆_r|,Ñ∪{g}∪ N^⋆_r,M')-part is also a (,N,X',c-|N^⋆|,Ñ∪ N^⋆,M')-part.
  This concludes the inductive proof of p_1.

  Now, the proof of <ref> follows from property p_1 with c=c(λ,t) and Ñ=∅.


We are now ready to define the steps that will be performed by the kernel.


   Let (G,X) be an input of ^λ, N be a set of non-K_t-vertices of G-X, and  be a root of G-X-N.
   Let M^0 = ∅.
   For ℓ from 1 to t-1 compute the following objects:
   
  * ^ℓ = {M' | (|M'| ≤ t-2 )}∪∅.
   
  * M^ℓ = (⋃_X' ∈, M' ∈^ℓ(,N,X',M')) ∖⋃_ℓ' ∈ [ℓ-1]M^ℓ'.
   

  Let M(,N,G,X) = ⋃_ℓ∈ [t-1]M^ℓ be the set of marked vertices.
   For any J ⊆ V(), we let J(M(,N,G,X))=J ∩ (⋃_ℓ∈ [ℓ(J,M(,N,G,X))]M^ℓ), where ℓ(J,M(,N,G,X))=max{ℓ| J ∩ M^x ≠∅ for any 1 ≤ x ≤ℓ} (if J ∩ M(,N,G,X) = ∅ then J(M(,N,G,X))=∅).
  
   
   When (,N,G,X) is clear from the context, M(,N,G,X) is simply denoted by M.

  Let (G,X) be an input of ^λ, N be a set of non-K_t-vertices of G-X, and  be a root of G-X-N.
  
  * |M(,N,G,X)| ≤ p_3^(λ,t)(|X|), where p_3^(λ,t)(|X|)=(t-1)((t-2)||p_2^(λ,t)(|X|))^(t-1)^(t-1).
  
  *  Step 1 can be done in time Ø(p_4^(λ,t)(n)), where p_4^(λ,t)(n)=(t-1)((t-2)||p_1^(λ,t)(n))^(t-1)^(t-1).
  
  Let x=|| and p=p_2^(λ,t)(|X|).
  Let us prove by induction on ℓ∈ [t-1] that |M^ℓ|  ≤ ((t-2)xp)^(t-1)^(ℓ-1).
  Observe that for any ℓ, |M^ℓ| ≤ |^ℓ|· xp ≤ |M^<ℓ|^(t-2)xp where M^<ℓ=⋃_i < ℓM^i.
  The result is immediate for ℓ≤ 2, so let us consider ℓ≥ 3.
  We have
  
    |M^ℓ|    ≤    |M^<ℓ|^(t-2)xp 
       ≤   ((t-2)((t-2)xp)^(t-1)^(ℓ-2))^(t-2)xp 
       =      (t-2)^((t-1)^ℓ-2+1)(t-2)(xp)^(t-1)^(ℓ-2)(t-2)+1
       ≤    (t-2)^(t-1)^ℓ-1(xp)^(t-1)^(ℓ-1),

  concluding the inductive proof, and leading to the claimed bound for |M(,N,G,X)|.
 The running time can be bounded using the same analysis, using p=p_1^(λ,t)(n).


For the next lemma we refer the reader to <ref>.
Informally, in this lemma we consider a vertexv ∈V() ∖M(,N,G,X)that has not been marked in Step 1, even if there exists a “dangerous” setJsuch thatJ ∪{v}is a clique, and^t_X'(J(M(,N,G,X)) ∪(C(J∖J(M(,N,G,X)) ∪v) ∪N') > 0. We show that, in this case, the marking algorithm necessarily found
a large packing.

  Let (G,X) be an input of ^λ, N be a set of non-K_t-vertices of G-X,  be a root of G-X-N, and M(,N,G,X) as computed in <ref>.
 If there exist

 
  * X' ∈, N' ⊆ N with |N'| ≤ c(λ,t) and X' ∪ N' does not contain a t-clique, v ∈ V() ∖ M(,N,G,X), and
   
  * J ⊆ V() such that |J| ≤ t-2, J ∪{v} is a clique, and ^t_X'(J(M(,N,G,X)) ∪ (C(J∖ J(M(,N,G,X)) ∪ v) ∪ N') > 0,
 

then there exist Ñ⊆ N' and a packing ^⋆ of (,N,X',c(λ,t)-|Ñ|,Ñ,J(M(,N,G,X)))-parts such that |^⋆|=|X|+1 and ^^⋆⊆ M(,N,G,X). 
Let us denote by M=M(,N,G,X).
  Let U = ⋃_ℓ∈ [ℓ(J,M)]M^ℓ and S = (J ∖ J(M)) ∪{v}. 
  We have that:
  
  * (S, N') is a (,N,X',c(λ,t),∅,J(M))-part. Note that <ref> is true as X' ∪ N' does not contain a t-clique,
    <ref> is true as (S ∪ J(M)) = J ∪ v, and thus it has size at most t-1 and it is a clique, and <ref> is true
    as  ^t_X'(J(M) ∪ (C(J∖ J(M) ∪ v) ∪ N') > 0.
  
  * S ∩(,N,X',J(M)) = ∅. Indeed, as (J∖ J(M)) ∩ M^ℓ(J,M)+1 = ∅ (recall that ℓ(J,M) is defined in <ref>, with ℓ(J,M) ≤ |J| ≤ t-2) and v ∉ M,
    we have S ∩ M^ℓ(J,M)+1=∅, and by definition S ∩ U = ∅.
    Thus, if by contradiction there exists w ∈(,N,X',J(M)) ∩ S, then as M^ℓ(J,M)+1⊇ ((,N,X',J(M)) ∖ U) and w ∉ U,
    we would have w ∈ M^ℓ(J,M)+1∩ S, a contradiction.
  

  Thus, by <ref>,  there exist Ñ'̃⊆ N' and a packing ^⋆ of (,N,X',c(λ,t)-|Ñ'̃|,Ñ'̃,J(M))-parts such that |^⋆|=|X|+1 and ^^⋆⊆(,N,X',J(M)).
    


































  Let (G,X,k) be an input of λ, N be a set of non-K_t-vertices of G-X, and  be a root of G-X-N.
  Let M(,N,G,X) as computed in Step 1.
  If there exists v ∈ V() ∖ M(,N,G,X), let G' = G-C(v) and k'-(G[C(v)]).

Step 2 can be done in Ø^⋆(p_0^(λ,t)(n)), where
p_0^(λ,t) is defined in <ref>.

  Step 2 can be done in polynomial time, as in particular we can compute (G[C(v)]) as according to
  <ref>(G[C(v)]) ≤(G-X) ≤λ, and using  <ref>.



Before proving the safeness of Step 2, we need the following technical lemma.


  Let (G,X) be an input of ^λ (recall that R = V(G)∖ X) and N be a set of non-K_t-vertices of G[R].
  For any X' ⊆ X, N' ⊆ N, R' ⊆ R such that R' ∩ N' = ∅ and X' ∪ N' does not contain a t-clique,
  ^t_X' ∪ N'(R') = 0  ⇔ ^t_X'(R' ∪ N') = 0.
  Note first that, by definition of N' and N, (G[R' ∪ N'])=(G[R']).

We first prove the forward implication.  As (G[R'],^t_X' ∪ N'(R'))=(G[R']), there exists an optimal solution S of G[R] that intersects any Z ∈^t_X' ∪ N'(R'))
  Let us prove that S is an optimal solution of G[R' ∪ N'] that intersects any Z ∈^t_X'(R' ∪ N')).
  Firstly, |S|=(G[R'])=(G[R' ∪ N']).
  Secondly, as any t-clique K of G[R' ∪ N'] is such that K ⊆ R', we deduce that S intersects all t-cliques of G[R' ∪ N'].
  Finally, let Z ∈^t_X'(R' ∪ N')). As X' ∪ N' does not contain a t-clique, we deduce that Z ∩ R' ≠∅, implying that Z ∖ N' ∈^t_X' ∪ N'(R')
  and that S ∩ (Z ∖ N') ≠∅.

  We now turn to the proof of the backward implication.  As (G[R' ∪ N'],^t_X'(R' ∪ N'))=(G[R' ∪ N']), there exists an optimal solution S of G[R' ∪ N'] that intersects any Z ∈^t_X'(R' ∪ N')).
  Let us prove that S is an optimal solution of G[R'] that intersects any Z ∈^t_X' ∪ N'(R')).
  Firstly, |S|=(G[R' ∪ N'])=(G[R']).
  Secondly, S intersects any t-clique of G[R' ∪ N'], and thus any t-clique of G[R'].
  Finally, let Z ∈^t_X' ∪ N'(R')). By definition of ^t, there exists a t-clique K such that K ∩ (X' ∪ N') ≠∅,
  and K ∩ R' = Z. By definition of N, we know that K ∩ X' ≠∅. This implies that Z ∪ (K ∩ N') ∈^t_X'(R' ∪ N')), and thus
  S ∩ (Z ∪ (K ∩ N')) ≠∅. Moreover, as S is an optimal solution of G[R' ∪ N'], and no vertex of N' belongs to a t-clique in G[R' ∪ N'],
  we get that S ∩ N' = ∅. Thus, we obtain S ∩ Z ≠∅.
  
    Let (G,X,k) be an input of λ, N be a set of non-K_t-vertices of G-X,   be a root of G-X-N, v and (G',k') as computed in <ref>.
   Then, the instances (G,X,k) and (G',X,k') of λ are equivalent.
 
  Let us denote by M=M(,N,G,X) and recall that  R=V(G)-X.
  Let us assume that (G',X,k') is a -instance and prove that (G,X,k) is a -instance as the other implication is direct.
  Let Z' be a solution of (G',X,k'). Note that (X ∪ N)∖ Z' does not contain any t-clique. Let R'=R-C(v). Let us distinguish the following two cases.

 

  
*Case 1: there exists J ⊆ V() such that |J| ≤ t-2, J ∪{v} is a clique, ^t_(X ∪ N)∖ Z'(J(M) ∪ C((J ∖ J(M)) ∪{v}))>0  and Z' ∩ J(M) = ∅.

Let us prove the following “overpay property”p_1: |Z' ∩ R' | > (G[R'])+|X|.

By <ref>, we have (G[J(M) ∪ C((J ∖ J(M)) ∪{v})]) ≤(G[R]) ≤λ, implying by <ref> that _t(G[J(M) ∪ C((J ∖ J(M)) ∪{v})]) ≤β(λ,t).
By <ref>, there exists S⊆ (X ∪ N)∖ Z' such that  ^t_S(J(M) ∪ C((J ∖ J(M)) ∪{v}))>0 and |S| ≤ (t-1)β(λ,t)=c(λ,t). Let X' = S∩ X and N' = S∩ N. By <ref>, we get ^t_X'(J(M) ∪ C((J ∖ J(M)) ∪{v}) ∪ N')>0.

By <ref>, there exist Ñ⊆ N' and a packing ^⋆ of (,N,X',c(λ,t)-|Ñ|,Ñ,J(M))-parts such that |^⋆|=|X|+1 and ^^⋆⊆ M.
Informally, the idea is that Z' will overpay at least one in each part of ^⋆, implying p_1. Let us formalize this idea.

  By definition, ^⋆={(V_i,N_i)} is such the V_i's and N_i's are pairwise disjoint, and for any i, ^t_X'(J(M) ∪ C(V_i) ∪Ñ∪ N_i)>0.
  As Z' ∩ X' = ∅, this implies that for any i, |Z' ∩ (J(M) ∪ C(V_i) ∪Ñ∪ N_i)| > (G[J(M)∪ C(V_i) ∪Ñ∪ N_i]).
  Moreover, as Ñ∪ N_i ⊆ N and N is the set of non-K_t-vertices of G[R], we get that Ñ∪ N_i are still non-K_t-vertices of
  G[J(M)∪ C(V_i) ∪Ñ∪ N_i], implying (G[J(M)∪ C(V_i) ∪Ñ∪ N_i])= (G[J(M)∪ C(V_i)]).
  In addition, by definition of a part, |V_i|+|J(M)| ≤  t-1, and by <ref>, J(M) also belongs to the set of non-K_t-vertices of G[J(M)∪ C(V_i)],
  implying (G[J(M)∪ C(V_i)])=(G[C(V_i)]).
  As Z' ∩Ñ = ∅ (because Z' ∩ N' = ∅ and Ñ⊆ N') and Z' ∩ J(M) = ∅, Z' ∩ (J(M) ∪ C(V_i) ∪Ñ∪ N_i)=Z' ∩ (C(V_i) ∪ N_i).
  Thus, we get property p_2: for any (V_i,N_i) ∈^⋆, |Z' ∩ (C(V_i) ∪ N_i)| > (G[C(V_i)]).

  Let us now define an appropriate partition of R'.
  Note that G[(V() ∖{v}) ∪ N] is also K_t-free in R' and that for any (V_i,N_i) ∈^⋆, we have V_i ⊆ V() ∖{v}.
  As there is a partition R'= {(V() ∖{v}) ∖^^⋆,  N}∪{C(V_i), (V_i,N_i) ∈^⋆}, <ref> implies that the corresponding  pending partition is additive, leading to (G[R']) = (G[C((V() ∖{v}) ∖^^⋆)]) + ∑_(V_i,N_i) ∈^⋆(G[C(V_i)]).


  
  
  
  
  

  On the other hand, we have:
  
    |Z' ∩ R'|    ≥    |Z' ∩ (C((V() ∖{v}) ∖^^⋆))| + |Z' ∩ (C(^^⋆∪ N^^⋆))|
       ≥   (G[C((V()∖{v}) ∖^^⋆)]) + ∑_(V_i,N_i) ∈^⋆(G[C(V_i)])+|^⋆| 
       ≥   (G[C((V()∖{v}) ∖^^⋆)])+ ∑_(V_i,N_i) ∈^⋆(G[C(V_i)])+|X|+1 
       ≥   (G[R'])+|X|+1.

  This leads to the overpay property p_1.

  This property will now help us to define an appropriate solution Z̃'̃ of G' which, unlike Z', is easy to complete into a solution in G of size at most k.
  Now, let us define Z̃'̃=X ∪ Z^⋆_R', where Z^⋆_R' is an optimal solution of G[R'].
  We have |Z̃'̃|=|X|+(G[R']) ≤ |Z' ∩ R'| ≤ |Z'| ≤ k'. Let Z = Z̃'̃∪ Z^⋆_i, where Z^⋆_i is an optimal solution of G[C(V_i)].
  We get hat |Z| ≤ k. Moreover, Z is a solution of G as, in particular, for any t-clique K of G such that K ∩ C(V_i) ≠∅,
  either K ∩ X ≠∅ or K ⊆ C(v_i) (according to <ref>), and in both cases Z ∩ K ≠∅.



  

  
*Case 2: for any J ⊆ V() such that |J| ≤ t-2, J ∪{v} is a clique, ^t_(X ∪ N)∖ Z'(J(M) ∪ C((J ∖ J(M)) ∪{v}))=0  or Z' ∩ J(M) ≠∅.

  In order to construct a solution Z of (G,k), let us prove the following properties p_3 and p_4 that assert the existence of “good” local solutions.
    


   Property p_3: there exists Z^⋆_v⊆ C(v) such that
  
  * |Z^⋆_v|=(G[C(v)]) and
  
  *  for any t-clique K' ⊆ C(v) ∪ ((X ∪ N) ∖ Z'), K' ∩ Z^⋆_v ≠∅.
  Proof of property p_3.
  The hypothesis of Case 2 applied with J = ∅ gives us  ^t_(X ∪ N)∖ Z'(C(v))=0.
  By the definition of ^t, this is equivalent to
  (G[C((v)])=(G[C(v)],pr^t_(X ∪ N)∖ Z'(C(v)).
  Thus, we define Z^⋆_v as an optimal solution of (G[C(v)],pr^t_(X ∪ N)∖ Z'(C(V)).
  We have |Z^⋆_v|=(G[C(v)]). Let K' be a t-clique with K' ⊆ C(v) ∪ ((X ∪ N) ∖ Z'). If K' ⊆ C(u_K), then as Z^⋆_v is a solution of G[C(v)],
  we get K' ∩ Z^⋆_v ≠∅. Otherwise, as K' ∖ (X ∪ N) ∈ pr^t_(X ∪ N)∖ Z'(C(v)), we know that Z^⋆_v ∩ (K' ∖ (X ∪ N)) ≠∅. This concludes the proof of property p_3.


 Property p_4: for any t-clique K of G such that K ∩ Z' = ∅ and v ∈ K, there exists u_K ∈ V()  and Z^⋆ r_u_K such that
  
  * u_K ∈ Z^⋆ r_u_K∩ K,
  
  * |Z^⋆ r_u_K|=(G[C(u_K)]), and
  
  *  for any t-clique K' ⊆ C(u_K) ∪ ((X ∪ N) ∖ Z'), K' ∩ Z^⋆ r_u_K≠∅.
  Proof of Property p_4.
  Let K be a t-clique as stated in p_4.
  Let J^K = K ∩ (V() ∖{v}).

  

  As G[V()] is K_t-free, |J^K| ≤ t-2. Moreover, as J^K ∪{v} is a clique,
  and Z' ∩ J^K(M) ⊆ Z' ∩ K = ∅, property of Case 2 applied with J = J^K  gives us  ^t_(X ∪ N)∖ Z'(Ṽ)=0 where Ṽ=J^K(M) ∪ C((J^K ∖ J^K(M)) ∪{v}).
  By the definition of ^t, this is equivalent to
  (G[Ṽ])=(G[Ṽ],pr^t_(X ∪ N)∖ Z'(Ṽ)).
  Let Z^⋆ be an optimal solution of (G[Ṽ],pr^t_(X ∪ N)∖ Z'(Ṽ)).
  Note that according to <ref>, vertices of J^K(M) are non-K_t-vertices of G[Ṽ], implying that (G[Ṽ])=(G[C((J^K ∖ J^K(M)) ∪{v})]),
 and by <ref> that (G[Ṽ])=∑_v' ∈ (J^K ∖ J^K(M)) ∪{v}(G[C(v')]).
  This equality implies that for any v' ∈ (J^K ∖ J^K(M)) ∪{v}, |Z^⋆∩ C(v')|=(G[C(v')]), and that Z^⋆∩ J^K(M) = ∅.
  Moreover, as K ∩ R ∈ pr^t_(X ∪ N)∖ Z'(Ṽ), we have that Z^⋆∩ (K ∩ R) ≠∅.
  As K ∩ R = J^K ∪{v} = J^K(M) ∪ (J^K ∖ J^K(M)) ∪{v} and Z^⋆∩ J^K(M) = ∅, we deduce that there exists u_K ∈ (J^K ∖ J^K(M)) ∪{v}
  such that u_K ∈ Z^⋆∩ K. Now, define Z^⋆ r_u_K = Z^⋆∩ C(u_K). The first two items of property p_4 are directly true, and let us prove the last one.
  Let K' be a t-clique with K' ⊆ C(u_K) ∪ ((X ∪ N) ∖ Z'). If u_K ∈ K' then we directly have K' ∩ Z^⋆ r_u_K≠∅, so let us suppose that
  u_K ∉ K'. If K' ⊆ C(u_K), then as Z^⋆ r_u_K is a solution of G[C(u_K)],
  we get K' ∩ Z^⋆ r_u_K≠∅. Otherwise, as K' ∖ (X ∪ N) ∈ pr^t_(X ∪ N)∖ Z'(Ṽ), we know that Z^⋆∩ (K' ∖ (X ∪ N)) ≠∅.
  As K' ∖ (X ∪ N) ⊆ C(u_K), we get  Z^⋆∩ (K' ∖ (X ∪ N)) = Z^⋆ r_u_K∩ (K' ∖ (X ∪ N)), and thus the third item follows. This concludes the proof of property p_4.


  We are now ready to define a solution Z of (G,k) be restructuring Z' in the following way.
  Let I = {u_K |}.
  We define Z such that
  
  * Z ∩ (X ∪ N) = Z' ∩ (X ∪ N), and
  
  *  for any u ∈ V(), Z ∩ C(u) is defined as follows:
    
  *  If u ∈ I, then Z^⋆ r_u.
    
  *  If u ∉ I: if u = v then Z^⋆ _v and otherwise Z' ∩ C(u).
    

  Observe that we may have v ∈ I, and that we have property p_5: for any u ∈ V() ∖{v}, if u ∈ Z', then  u ∈ Z.
  This property holds as either u ∈ I and then Z ∩ C(u) = Z^⋆ r_u, which contains u_K by property p_4,
  or u ∉ I and then Z ∩ C(u) = Z' ∩ C(u).

  Let us first bound |Z|. Note that for any u ∈ V(), u ≠ v, we always have |Z ∩ C(u)| ≤ |Z' ∩ C(u)|.
  Thus, |Z|=|Z ∩ (X ∪ N)| + |Z ∪ R| ≤ |Z' ∩ (X ∪ N)| + ∑_u ∈ V()∖{v}|Z' ∩ C(u)| + (G[C(v)])=|Z'|+(G[C(v)]) = k.

  Let us now check that Z is a solution of G.
  Let K' be a t-clique. If K' ∩ (X ∪ N) ∩ Z' ≠∅, then K' ∩ Z ≠∅, so
  let us suppose that K' ∩ (X ∪ N) ⊆ (X ∪ N) ∖ Z'. As Z' is a solution of G', we cannot have K' ⊆ (X ∪ N), implying K' ∩ R ≠∅.

  Suppose first that there exists u ∈ V() such that K' ∩ R ⊆ C(u).
  Then, if u ∈ I then u ∈ Z^⋆ r_u and we are done.
  Otherwise, if u = v then by the second item of property p_3 we get Z^⋆_v ∩ K' ≠∅.
  Finally, if u ∈ V() ∖ (I ∪{v}), then Z ∩ C(u) = Z' ∩ C(u), and as K' ⊆ V(G'), we get Z' ∩ C(u) ∩ K' ≠∅.

  Assume that there is no u ∈ V() such that K' ∩ R ⊆ C(u).
  Let J̃^̃K̃ = K' ∩ R. By <ref>, we know that J̃^̃K̃⊆ V().
  If K' ∩ Z' ≠∅, then there exists u ∈ K' ∩ Z' with u ∈ V(), and by property p_5 we get K' ∩ Z ≠∅.
  Otherwise, we know that v ∈J̃^̃K̃ (as  otherwise K' ⊆ V(G') and  we could not have K' ∩ Z' = ∅), and thus let us write
  K' ∩ R = J^K ∪{v}. Therefore, we get that u_K'∈ I, and Z ∩ C(u_K')=Z^⋆ r_u_K' where u_K'∈ Z^⋆ r_u_K'∩ K' by property p_4.
  






































KwDataInputKwResultOutput


We are now ready to define the pseudo-code of the kernel.
In what follows we denote by  kernel-size(G,k,t)the polynomial kernel forK_t- Hitting Set parameterized by the solution size of sizeØ(tk^t-1)by Abu-Khzam <cit.>. We need the following observation.

  Given an input (G,X,k,λ) of λ where λ=0, as (G-X)=0 implies that G-X is K_t-free,
  we can answer  if k ≥ |X|. Thus, when k < |X| kernel-size(G,k,t) of <cit.> provides a kernel of size 3t|X|^t-1.








We are now ready to prove the main theorem of this section, whose statement here is an extended version of <ref> claimed in the introduction.
<ref> is a polynomial kernel for λ running in time Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2)) and whose output has size Ø_λ,t(|X|^δ(λ,t)), where
  δ(λ,t)=(t-1)(2c(λ,t)+2)^λ, and c(λ,t) is the upper bound on the size of chunks coming from <ref>.

  Let us start with the correctness.
  Let  be the -root of G-X-N^t(G-X) computed by the algorithm.
  We claim that, during the while loop of <ref>, the following invariant remains true (where informally each loop adds one vertex v to V'):
  for any (G',',k') computed during the while loop, there exists V' ⊆ V() such that
  
  * G'=G - C(V'),
  
  * k'=k-∑_v ∈ V'(G[C(v)]),
   
  * (G,k) and (G',k') are equivalent,
  
  * V(') = V() - V', and
   
  * N is a set of non-K_t-vertices of G'-X and ' is a root of G'-X-N.
  


 Notice first that <ref>, <ref>, and <ref> trivially hold.
 Then, <ref> holds according to <ref> and the second part of <ref> holds by definition of a root.
Note that <ref> implies that (',X,G',X) respects conditions required in <ref> to compute M(',N,G',X).

Let us now prove that at the end of the while loop, (G'-X') ≤λ-1.
(we use ⊆_i to denote induced subgraph in the next equation)


    G'-X'     =  G'-(V(') ∪ X) 
        = G-{C(V') ∪ V(') ∪ X}       by <ref>
       ⊆_i  G-{V' ∪ V(') ∪ X}      as V' ⊆ C(V')
        =  G-{V() ∪ X}       by <ref>.




Thus, using <ref> we get (G'-X') ≤(G-{V() ∪ X}).
Moreover,

    (G-{V() ∪ X})    ≤(G-{V() ∪ X ∪ N^t(G-X)}) 
        <   (G-{X ∪ N^t(G-X)}) 
        =  (G-X) = λ.

Where inequality (2) holds as N^t(G-X) is still a set of non-K_t-vertices in G-{V() ∪ X},
and (3) as  is a -root of G-X-N^t(G-X).

Thus, we get the claimed property that, at the end of the while loop, (G'-X') ≤λ-1, and thus by using <ref> and a straightforward induction on λ we get
that <ref> is correct.

Let us analyze the size of the kernel.
  For any t ≥ 3, let p_3^(0,t)(x)=3tx^t-1 and
  f^(λ,t)(x)=p_3^(0,t)(2p_3^(1,t)(…(2p_3^(λ,t)(x))…)).
  Let us show by induction on λ that for any input (G,X,k,λ), A(G,X,k,λ) returns a subset of vertices of G of size f^(λ,t)(|X|).
  The result is clear for λ=0 by <ref>, and given λ≥ 1, by induction hypothesis A(G,X,k,λ) returns a subset of vertices of size
  f^(λ-1,t)(|X|+p_3^(λ,t)(|X|))≤ f^(λ-1,t)(2p_3^(λ,t)(|X|)) = f^(λ,t)(|X|).

  Now, there exists constants α_2 and α_3,
  depending on t and λ, such that
  
  * p_2^(λ,t)(x)=α_2x^δ_2 where δ_2=c(λ,t)+2, and
  
  * p_3^(λ,t)(x)=α_3x^δ_3 where δ_3=δ_2+c(λ,t)=2c(λ,t)+2.
  

  Thus, as f^(λ,t)(x)≤ p_3^(0,t)(2p_3^(λ,t)(…(2p_3^(λ,t)(x))…)), we get that there exists a constant α_4
  such that f^(λ,t)(x)≤α_4x^(t-1)δ_3^λ.

  Finally, let us analyze the running time.
  Let r(n,λ) be the upper bound on complexity to any call of kernel algorithm with input (G,X,k,λ), where |V(G)|=n.
  Let us first prove that there exists f^(λ,t)(n)=Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2)) such that r(n,λ)=f^(λ,t)(n)+r(n,λ-1), leading to the claimed complexity.

Before starting the analysis, notice that polynomials p_0, p_1 and p_4 defined respectively in <ref>, <ref>, and <ref> are such that:
  
  * p_0^(λ,t)(n)=n^Ø_t(λ^2),
      
  * p_1^(λ,t)(n)=(n^t+c(λ,t)+Ø(1)c(λ,t)p_0^(λ,t)(n))^c(λ,t)+1=Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2)), and
      
  * p_4^(λ,t)(n)=(t-1)((t-2)||p_1^(λ,t)(n))^(t-1)^(t-1)=Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2)).
  

 Now, consider a call with input (G,X,k,λ). Let f^(λ,t)(n) be the complexity of all operations performed before the recursive call.
  One can observe that f^(λ,t)(n) can be bounded by Ø^⋆(n^t) (to compute N^t(G-X)), plus n^Ø_t(λ) (to compute a -root using <ref>), plus n(p_4^(λ,t)(n)+p_0^(λ,t)(n)) (for the while loop).

 This leads to
 
    f^(λ,t)(n)     =    Ø^⋆(n^t)+n^Ø_t(λ)+n(Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2))+n^Ø(λ^2)) 
        =    Ø_λ,t(n^Ø_t(λ^2c(λ,t)^2)).


To conclude this section, we would like to observe that, by our hardness results (<ref> and <ref>), the kernelization algorithm that we have presented needs to exploit the fact that the graphHthat we want to hit is a clique. In particular, the following lemmas of the previous section about upper-bounding the size of minimal blocking sets do not hold anymore as soon asHis not a clique, and thus (see the discussion before <ref>) when “a set of two isolated vertices can be a part of blocking set". In particular,  <ref> fails as there is no reason than we can zoom in oneC(v), and <ref> fails as we no longer have= ⋃_i ∈[c](∩C_i). Also, another place where we exploit thatHis a clique is in the proof of <ref> to obtain the improved bound in graphs of bounded treedepth.



§ COMPUTING A -ROOT AND AND AN OPTIMAL SOLUTION IN GRAPHS WITH BOUNDED 


In this section we present some results for graphs where the parameteris bounded by a constant, and which are needed in our kernelization algorithm. Namely, in <ref> we show (<ref>) how to compute a-root of a graphGwith(G) ≤λin polynomial time for fixedtandλ. We need this ingredient in the kernel where we recursively call it with decreasing values ofλ.  This algorithm is in fact a byproduct of an -algorithm (<ref>) to computewith the natural parameterization.



Then, in <ref> we present an algorithm (<ref>) that computes in polynomial time, again for fixedtandλ, an optimum solution ofK_t- Subgraph Hitting in graphs with bounded, and that decides whether  an instance(G,)ofis clean. These ingredients are crucially used in the kernelization algorithm to compute optimal solutions in the pending componentsC(v)considered by the algorithm, and for deciding whether a conflict is positive.




For the sake of readability, in this section we use self-contained notation for the annotated problem that we consider.

Let$̋ be a collection of subgraphs of a graph G. For an integer t, define 
    _t(G, )̋ = {S ⊆ V(G) | G-S  is K_t-free and S ∩ V(H) ≠∅ for each H ∈$̋}.
    Forv ∈ V(G), we additionally define 
        _t(G,,̋v) = {S ∈_t(G,)̋| v ∈ S}.
    
    Let(G,)̋ = min _S ∈_t(G,)̋ |S|and_t(G,)̋ = {S ∈_t(G,)̋| |S| = (G,)̋}. We define(G) = (G,∅), and similarly let_t(G) = _t(G,∅)and_t(G) = _t(G,∅).
    
    For a collection$̋ of subgraphs of G and a subset of vertices V' of G, we denote by ∩̋V' the collection of subgraphs H ∈$̋ which are fully contained inV'.
    
    
     §.§ Computing a -root
    
    
    In this section we show that for fixedλ, we can compute a-root for a graphGwith(G) ≤λandN^t(G) = ∅in polynomial time (recall thatN^t(G)is the set of non-K_t-vertices ofG). It is a byproduct of an -algorithm to computewith the natural parameterization. Before presenting that algorithm, we give some structural lemmas about the behavior of roots.
    
    
    Let G be a connected undirected graph and let T be a vertex set such that each connected component of G-T is adjacent to exactly one vertex of T. For each biconnected component F of G on at least three vertices, the following holds: if |T ∩ F| > 1, then F ⊆ T.
    
    Suppose for a contradiction that T contains more than one, but not all, vertices of a biconnected component F on at least three vertices. Let u ∈ F ∖ T and consider the connected component C of G-T that contains u. By the stated assumption on T, the component C has exactly one neighbor t ∈ T. Let r ∈ (F ∩ T) ∖{t} be another vertex from T inside the biconnected component F. Since F is biconnected and has at least three vertices, it is 2-connected. Hence, by Menger's theorem, there are two internally vertex-disjoint paths P_1, P_2 from u to r. At least one of these paths, say P_1, does not visit vertex t. Now consider the first time that P_1, which starts in u ∉ T and ends in T, visits a vertex t' ∈ T. We have t' ≠ t as t does not lie on P_1. Since the prefix of P_1 consisting of the subpath until reaching t' is disjoint from T, the prefix is contained entirely inside one connected component of G-T. That component also contains u and is therefore C. But this shows that component C is adjacent to at least two distinct vertices of T, namely t and t'; a contradiction to our assumption on T.
    
    Let G be a connected undirected graph and let T_1, T_2 be vertex sets such that for each i ∈ [2], the graph G[T_i] is connected and each connected component of G-T_i is adjacent to exactly one vertex of T_i. If T_1 ∩ T_2 ≠∅, then each connected component of G - (T_1 ∪ T_2) is adjacent to exactly one vertex of (T_1 ∪ T_2).
    
    Note that since G is connected, each component of G - (T_1 ∪ T_2) is adjacent to at least one vertex of T_1 ∪ T_2. We argue that it cannot be adjacent to more. Assume for a contradiction that C is a connected component C of G - (T_1 ∪ T_2) that is adjacent to two distinct vertices t_1, t_2 ∈ T_1 ∪ T_2. If t_1, t_2 belong to a common set T_i, then in G - T_i there is a connected component containing C, and it would be adjacent to both t_1, t_2 ∈ T_i; this would contradict our assumption on T_i. Hence we may assume that t_1 ∈ T_1 and t_2 ∈ T_2. Since T_1 ∩ T_2 ≠∅ and the subgraph G[T_i] is connected for each i, there is a simple path P from t_1 to t_2 in G whose edges are contained in E(G[T_1]) ∪ E(G[T_2]); such a path can be obtained by combining a path from t_1 to T_1 ∩ T_2 with a path from t_2 to T_1 ∩ T_2 and trimming repetitions. Since t_1 ∉ T_2 and t_2 ∉ T_1, while the path is confined to edges that belong to some E(G[T_i]), path P uses at least one third vertex t_12∈ T_1 ∩ T_2. Since component C is connected and adjacent to both t_1 and t_2, there is a path Q in C from a neighbor of t_1 to a neighbor of t_2, and P ∪ Q form a simple cycle D on at least three vertices. Let c be a vertex on the cycle D which is contained in component C. The cycle witnesses that t_1, t_2, t_12, and c are part of a common biconnected component F of G, with F ⊇ V(D). We use it to derive a contradiction: the set T_1 contains at least two vertices from the biconnected component F, but it does not contain a third vertex c ∈ F; a contradiction to <ref>.
    
    Let t ≥ 3 be an integer and let H := K_t. Let G be a connected graph with N^t(G) = ∅. Let G' be the subgraph of G consisting of the union of the biconnected components of G which are K_t-free. Then for each connected component T_i of G', the set T_i is a root of G. Furthermore, one of the following holds:
    
      *  There is a vertex v ∈ V(G) with (G - v) < (G).
        
      *  There is a connected component T_i of G' for which (G - T_i) < (G), so that T_i is a -root of G.
    
    
    We first establish that for each biconnected component F of G, if G[F] is H-free then F is a root of G. Since G[F] is trivially connected, it suffices to argue that each connected component of G-F is adjacent to exactly one vertex of F. Connectivity of G ensures a component cannot be adjacent to fewer than one. If C is a connected component of G-F that is adjacent to two distinct vertices u,v of F, then F is not a biconnected component (inclusion-maximal connected subgraph without a cutvertex): the subgraph obtained from F by extending it with an edge from u to a neighbor in C, a path within C to a neighbor of v, and an edge to v, is again biconnected and a strict supergraph of F; a contradiction.
    
    The preceding paragraph shows that for each H-free biconnected component F of G, the set F is a root of G. If two roots T_1, T_2 of G share a vertex, then T_1 ∪ T_2 is also a root of G: the graph G[T_1 ∪ T_2] is connected since each part is connected and they share a vertex; by <ref> the removal of T_1 ∪ T_2 leaves components that each see exactly one vertex of T_1 ∪ T_2. It remains to argue that G[T_1 ∪ T_2] is H-free. This follows from the fact that H is biconnected and has at least three vertices. Hence any occurrence of H as a subgraph of G is contained within a single biconnected component of G on at least three vertices. If a copy of H is contained in a single biconnected component F of G[T_1 ∪ T_2]. Since H has at least three vertices, at least two vertices of H belong to a common set T_i for some i ∈ [2]. The fact that F is a biconnected component of G[T_1 ∪ T_2] implies that F is a subgraph of a biconnected component F' of G. Since T_i contains at least two vertices of F', by <ref>, the set T_i contains all vertices of F'; but then G[T_i] contains a copy of H, which is a contradiction.
    
    We have now established that for each H-free biconnected component F of G, the set F is a root of G; and that the union of two intersecting roots of G is itself a root. Note that for each connected component C of the graph G' defined in the lemma statement, the vertex set of C can obtained by repeatedly taking the union of two intersecting H-free biconnected components of G. If follows that for each connected component T_i of G', the set T_i is a root of G.
    
    To complete the proof of the lemma, we show that if no single vertex v ∈ V(G) has the property that (G-v) < (G), then there is a connected component T_i of G' for which (G-T_i) < (G). We argue as follows. Since G is connected and N^t(G) = ∅, by <ref> there is a root T such that (G) = 1 + (G-T). Since we assumed no single vertex has this property, we have |T| ≥ 2.
    
    
    There is a connected component T_i of G' such that T ⊆ T_i.
    
    Recall that the biconnected components of a graph partition its edge set. Hence for each edge e of G[T], some biconnected component F_e of G contains e. We argue that F_e ⊆ T. If |F_e| = 2 then this is trivial since e was an edge of G[T]. If |F_e| ≥ 3, then the fact that T contains both endpoints of e implies by <ref> that T contains all vertices of F_e. Since G[T] is H-free, the biconnected component F_e is H-free. So for each e ∈ G[T], G[F_e] is a subgraph of G', with G' as defined in the lemma statement. Since G[T] is connected, this implies that there is a connected component T_i of G' that contains all edges e of G[T]. Since |T| ≥ 2, this implies that T ⊆ T_i.
    
    
    Using the claim, we now prove the last part of the lemma statement: there exists a component T_i such that (G) = 1 + (G - T) ≤ 1 + (G - T_i), where the last inequality follows from <ref>. It follows that (G - T_i) ≤(G) - 1, which completes the proof.
    
    
    With these ingredients, we can now give an -algorithm algorithm to compute(G).
    
    
    Let t ≥ 3 be an integer and let H := K_t. There is an algorithm that, given a graph G and integer λ≥ 0, determines whether or not (G) ≤λ in time n^_t(λ).
    
    We first present the algorithm and then analyze it. The algorithm is recursive and proceeds as follows.
    
    
    
        Base case: V(G) = ∅.
     In this case we have (G) = 0 ≤λ and therefore the algorithm outputs 𝗍𝗋𝗎𝖾.
    
    
    
        Base case: λ = 0.
     If λ = 0, then we output 𝗍𝗋𝗎𝖾 if and only if G is K_t-free, which can be determined in time n^(t)∈ n^_t(1).
    
    
    
        Step case: V(G) ≠∅.
     The algorithm considers the following cases.
    
      *  If G is disconnected, with connected components C_1, …, C_m, we recursively run the algorithm on (C_i, λ) for each i ∈ [m] and return the disjunction of the resulting values.
        
      *  If G is connected, then we compute the set N^t(G), which can be done in time n^(t)∈ n^_t(1).
        
      *  If N^t(G) is nonempty, then we return the result of the recursive call on (G - N^t(G), λ).
            
      *  If N^t(G) is empty, then we make a sequence of recursive calls.
            
      *  For each vertex v ∈ V(G) we recurse on (G - v, λ-1).
                
      *  Let G' be the subgraph of G consisting of the union of the biconnected components of G which are K_t-free. For each connected component T_i of G', we recurse on (G - T_i, λ - 1).
            
            If at least one recursive call returns 𝗍𝗋𝗎𝖾, then we return 𝗍𝗋𝗎𝖾; otherwise we return 𝖿𝖺𝗅𝗌𝖾.
        
    This concludes the description of the algorithm.
    
    
    
        Running time.
     We prove the algorithm runs in time n^_t(λ). Towards that purpose, we analyze the recursion tree generated by the algorithm.
    
    We first bound the depth of the recursion tree. The value of λ never decreases. After every three successive levels of recursion, the value of λ has strictly decreased. To see this, note that the only recursive calls which do not decrease λ are those where we split on connected components, or remove the vertices of N^t(G). Recursive calls in which we split in components cannot be consecutive, since each call it generates is for a connected graph. If we recurse by removing N^t(G), then the graph on which we recurse has all vertices in a copy of K_t (but may be disconnected). After possibly recursing one more level on the connected components (which preserves the fact that all vertices occur in a copy of K_t), the graph under consideration is connected and has all its vertices in a copy of K_t. Hence after those two recursive calls that do not decrease λ, the next call either terminates the algorithm or leads to a decrease of λ by recursing on G-v or G-T_i. Since the algorithm terminates once λ = 0, the recursion depth is indeed bounded by (λ).
    
    The branching factor of the algorithm is (n): it either recurses once for each component, or it recurses once for each vertex and once for each of the at most n choices for T_i.
    
    The total number of nodes in the recursion tree is bounded by the branching factor raised to the power depth, which is therefore n^(λ). Since the running time per call is n^_t(1), the algorithm runs in time n^_t(λ), as required.
    
    
    
        Correctness.
     Correctness in the base cases is trivial; the same goes for the step case in which G is connected or N^t(G) ≠∅. For the case that G is connected and N^t(G) = ∅, if (G) ≤λ then by <ref> the algorithm makes a recursive call on an induced subgraph G^* with (G^*) < λ. Using induction on the recursion depth, we may assume that the recursive call is correct and reports that (G^*) ≤λ-1, which leads the algorithm to conclude that (G) ≤λ. Since the algorithm only reports (G) ≤λ when it has found a connected K_t-free vertex set whose removal yields a graph G^* with (G^*) ≤λ - 1, the algorithm is correct when it concludes that (G) ≤λ.
    
    This concludes the proof.
    
    
    Using the previous algorithm to compute(G)and <ref>, we can now derive an algorithm to compute a-root of a graph.
    
    
    Let t ≥ 3 be fixed and H := K_t. There is an algorithm that, given a graph G and integer λ such that (G) ≤λ and N^t(G)=∅, outputs a -root  of G in time n^_t(λ).
    
    
    
    
    We first prove the statement for the case that G is connected. Using <ref>, we can compute (G) in time n^_t(λ) and store it as λ^*. For each v ∈ V(G), we invoke <ref> again on G-v. If we find a vertex for which (G-v) < λ^*, we terminate with the -root v as output.
    
    Suppose now that no choice of v causes the algorithm to terminate. We compute the graph G' consisting of the union of the H-free biconnected components of G, in time n^_t(1). For each connected component T_i of G', we invoke <ref> on the graph G - T_i. The lemma guarantees that each set T_i is a root of G. Since no single vertex formed a -root of G, the lemma also guarantees that (G - T_i) < (G) for at least one such choice of T_i; then we give T_i as the output of the algorithm. This concludes the proof for the case that G is connected. Note that the algorithm runs in time n^_t(λ) since it performs (n) calls to a subroutine with running time n^_t(λ)), and additionally spends n^_t(1) time computing G'.
    
    Now suppose G has multiple connected components. Since the forbidden graph H is connected, a -root  for a disconnected graph G can be obtained by selecting a -root for each connected component: since the removal of V() decreases the  value of each component, by <ref> the removal of V() also decreases (G). If N^t(G) = ∅, then as each copy of H is contained in a single connected component, we also have N^t(C_i) = ∅ for each connected component C_i of G. Hence it suffices to run the algorithm for connected graphs described above and take the union of the computed roots.
    
    
    
    
    
    
    
     §.§ Computing an optimal solution
    
    
    Before presenting the algorithm, we give the following lemma which will be useful in its analysis. The lemma roughly says that if we have a connected graphGwith a rootTwith respect to a forbidden subgraphK_t, then in any optimal solutionU ∈_t(G,)̋we can replace the intersection ofUwith a pending componentC(v)(<ref>) by a solution from_t(C(v), ∩̋C(v))to obtain a new optimal solution; we just need to ensure to replace it by a solution to the smaller problem that contains the attachment vertexv, if there is an optimal solution doing so. We will use the lemma to later prove the correctness of an algorithmic strategy that solves the problem onGby separately solving it on pending components of the rootT, testing for eachv ∈ Twhether there is an optimal solution that contains the attachment point.
    
    
    Let H = K_t for some constant t ≥ 3. Let T ⊆ V(G) be a root of a connected graph G and let $̋ be a collection of complete subgraphs ofG, each having less thantvertices. LetU ∈_t(G,)̋. For eachv ∈ T, the following holds.
    
      *  If _t(C(v), ∩̋C(v), v) ≠∅, then for each set U^+ ∈_t(C(v), ∩̋C(v), v) we have (U ∖ V(C(v)) ∪ U^+ ∈_t(G,)̋.
        
      *  If _t(C(v), ∩̋C(v), v) = ∅, then for each set U^- ∈_t(C(v), ∩̋C(v)) (note that v ∉ U^-) we have (U ∖ (V(C(v)) ∖{v})) ∪ U^- ∈_t(G,)̋.
    
    Assume first that U^+ ∈_t(C(v), ∩̋C(v), v), so that the set of such optimal solutions is not empty. Define U^* := (U ∖ V(C(v)) ∪ U^+; our goal is to show U^* ∈_t(G,)̋.
    
    We first argue that |U^*| ≤(G,)̋. This follows from the fact U^+ ∈_t(C(v), ∩̋C(v)), so U^+ is an optimal choice of vertices to hit the copies of K_t in C(v) together with those graphs in $̋ which are fully contained inC(v), while the setU ∩ C(v)also hits all copies ofK_tinC(v)and all graphs of$̋ fully contained in C(v). Hence replacing the latter by the former does not yield an increase in size, and |U| = (G,)̋ by definition.
    
    Now we argue that U^* ∈_t(G,)̋. Since U ∈_t(G,)̋ and we obtain U^* by replacing U ∩ C(v) with U^+, it suffices to argue that any copy of K_t or H ∈$̋ that is hit byU ∩ C(v), is also hit byU^+. By definition of pending component, any complete subgraph ofGis either contained fully inC(v), or disjoint fromC(v) ∖{v}. Sincev ∈ U^+and the setU^+hits allK_t-subgraphs inC(v)and all subgraphs of∩̋C(v), we concludeU^* ∈_t(G,)̋. Together with the previous paragraph, this yieldsU^* ∈_t(G,)̋as desired.
    
    The proof of the second part is similar. So assume_t(C(v), ∩̋C(v), v) = ∅and letU^- ∈_t(C(v), ∩̋C(v)). DefineU^** := (U ∖ (V(C(v)) ∖{v})) ∪ U^-, so it is effectively obtained by replacing the choices ofUin the interior of the pending component by the solutionU^-. By this definition, ifv ∈ Uthen it remains inU.
    
    We argue that|U^**| ≤(G,)̋. Ifv ∉ U, then the argument is identical to the one given for the first case. So assumev ∈ U. Since_t(C(v), ∩̋C(v), v) = ∅, while it is easy to see thatU ∩ C(v) ∈_t(C(v), ∩̋C(v)), we derive that|U ∩ C(v)| > (C(v), ∩̋C(v)), which implies that|U ∩ (C(v) ∖{v})| ≥(C(v), ∩̋C(v)). Hence the number of vertices inserted intoU^**during the replacement is at most as large as the number we remove, which proves that|U^**| ≤(G,)̋.
    
    To complete the proof, it suffices to establish thatU^**∈_t(G,)̋. Ifv ∉ U, then this follows analogously to the first case of the lemma. Ifv ∈ U, then since it is not replaced we havev ∈ U^**, which therefore hits all copies ofK_torH ∈$̋ that contain v. All remaining forbidden subgraphs either live fully in C(v) and are therefore hit by U^-, or are disjoint from C(v) and are therefore hit by U ∖ C(v). It follows that U^**∈_t(G, )̋.
    
    
    The following technical lemma will also be useful when analyzing the algorithm. It says that the number of verticesvthat a solutionU ∈_t(G,)̋picks from a rootT, but for which the subinstance(C(v), ∩̋C(v))does not have an optimal solution containingv, is bounded in terms of the difference(G,)̋ - (G).
    
    
    Let H = K_t for some constant t ≥ 3. Let T ⊆ V(G) be a root of a connected graph G and let $̋ be a collection of complete subgraphs ofG, each having less thantvertices. DefineT' := {v ∈ T |_t(C(v), ∩̋C(v), v) ≠∅}, and letU ∈_t(G,)̋. Then|U ∩ (T ∖ T')| ≤(G, )̋ - (G).
    
    Consider a vertex v ∈ U ∩ (T ∖ T'). By definition of T', the set _t(C(v), ∩̋C(v), v) is empty: no solution that hits the K_t-subgraphs of C(v) and the subgraphs of $̋ fully contained inC(v), containsv. Since the setU ∩ C(v)hits both types of subgraphs and containsv, we have|U ∩ C(v)| > (C(v), ∩̋C(v)) ≥(C(v)).
    
    We can now analyze the global situation as follows. It is easy to see that for eachv ∈ Twe haveU ∩ C(v) ≥(C(v)); we just argued that forv ∈ U ∩ (T ∖ T')we have a strict inequality. Hence we find: 
        (G,)̋ = |U| ≥( ∑_v ∈ T(C(v)) ) + |U ∩ (T ∖ T')|.
     On the other hand, by definition of root, no vertex ofTbelongs to aK_t-subgraph inG. Hence the edges withinG[T]can be removed from the graph without changing the set ofK_t-subgraphs and thereby without changing. Since the connected components of the resulting graph are exactly the subgraphsC(v)forv ∈ T, it follows that: 
        (G) = ∑_t ∈ T(C(v)).
    
    
    Subtracting the second equation from the first proves the lemma.
    
    For each constant t ∈ℕ with t ≥ 3, there is an algorithm with the following specifications.
    
      *  The input consists of a graph G, a collection $̋ of complete subgraphs ofGhaving less thant-vertices each, and integersλ, κ≥ 0.
        
      *  The output is a vertex setS ⊆ V(G)such thatS ∈_t(G,)̋.
        
      *  When(G) ≤λand(G,)̋≤(G) + κ, the algorithm guarantees that|S| = (G,)̋, so thatS ∈_t(G,)̋.
    
    The algorithm runs in timen^_t((λ + κ)^2).
    
    We first present the algorithm and then its analysis. The algorithm is recursive, with a setup similar (but more complicated) than the one in <ref>. Before the recursion starts, we run the algorithm from <ref> to test whether (G) ≤λ. If this is not the case, we may simply output V(G). Hence in the remainder we may assume (G) ≤λ. We now describe the recursion.
    
    
    
      
    *Base case: V(G) = ∅. In this case we simply return the empty set as the unique optimal solution.
    
    
    
      
    *Base case: λ = 0. By definition, if (G) = λ = 0 then G is K_t-free.
    
      *  If G contains a K_t, then we can be sure that (G) > λ and return the trivial solution V(G).
        
      *  If G is K_t-free and =̋∅, we return the empty set which belongs to _t(G,)̋.
        
      *  If G is K_t-free, ≠̋∅, and κ = 0, then we conclude that (G,)̋ > (G) + κ = 0 + 0 and return the trivial solution V(G).
        
      *  If G is K_t-free, ≠̋∅, and κ > 0, then we consider one arbitrary H_1 ∈$̋. For each vertexv_i ∈ V(H_1)we recurse on the instance(G-v_i, ∩̋(V(G)∖ v_i), λ, κ-1). LetS_1, …, S_|V(H)|be the results of the recursive calls. We output a minimum-size set among{{v_i}∪ S_i | i ∈ [|V(H_1)|]}. (Steps of this type mimic the behavior of a bounded-depth search tree algorithm for$̋-hitting set parameterized by solution size κ.)
    
    This concludes the description of the base case, which is easily seen to be correct.
    
    
    
      
    *Step case: λ > 0. The step case consists of various subcases, depending on how the recursive definition of (G) (<ref>) attains its minimum value. The algorithm considers the vertex set that would be eliminated by the recursive definition and guesses how an optimal solution intersects that set.
    
    
      *  If G is disconnected with connected components C_1,…, C_m, then we recurse on the instance (C_i, ∩̋C_i, α, κ) for each i ∈ [m] and return the union S of the obtained vertex sets. Note that S ∈_t(G, )̋ since each graph H_j ∈$̋ is complete and is therefore contained fully within some componentC_i.
        
      *  IfGis connected, then letZ ⊆ V(G)be the subset of vertices which are not contained in anyK_t-subgraph ofG. We distinguish two cases.
        
      *  If Z ≠∅, then proceed as follows. For each subset Z'⊆ Z of size at most κ, which will be our guess for how the solution intersects Z, we define:
    
            
        _̋Z' = { H ∩ (G - Z) | H ∈∧̋V(H) ∩ Z' = ∅.}
    
            In other words, we take those subgraphs of $̋ which are disjoint fromZ'and project them onto the remaining graphG-Z. If_̋Z'contains the empty subgraph on vertex set∅, then our guess ofZ'was incorrect. Otherwise, we recurse on(G - Z, _̋Z', κ - |Z'|, λ), resulting in a subsetS_Z'⊆ V(G - Z). If at least one recursive call was made, we output a minimum-size subset among{S_Z'∪ Z' | Z' ⊆ Z ∧ |Z'| ≤κ∧∅∉_̋Z'}. If all choices ofZ'lead to∅∈_̋Z', we outputV(G)as a trivial solution. (Below we will argue that(G,)̋ > (G) + κwhen this happens.) 
      *  Now supposeZ = ∅. If the algorithm reached this point, thenV(G) ≠∅, the graphGis connected, and all its vertices belong to someK_t. Hence we have(G) = 1 + min _T ⊂ V(G)(G-T), whereTranges over all roots ofG. Since have(G) ≤λbased on the opening step of the algorithm, we can invoke <ref> to compute a-rootTofGin timen^_t(λ).
            
    
            LetT = {v_1, …, v_m}. For eachj ∈ [m], recall (<ref>) thatC^T(v_j)coincides with the subgraph ofGinduced by the union of the connected components ofG-Tfor whichv_jis the unique vertex ofTto which they are adjacent, together withv_jitself. Let_̋j := ∩̋C(v_j). We want to compute a good solutionS^+_j ∈_t(C^T(v_j), _̋j)that containsv_j. To do this, we proceed as follows. We recursively call the algorithm on(C^T(v_j) - v_j, ∩̋C(v_j)-v_j, λ - 1, κ)and defineS^+_jas the union of{v_j}with the obtained result.
    
            Additionally, we want to compute a good solutionS^-_j ∈_t(C^T(v_j), _̋j)that avoidsv_j. To that end, we let'̋_jcontain the graphH ∩ (C^T(v_j) - v_j)for eachH ∈$̋ with H ⊆ C^T(v_j), together with the graph F - v_j for each copy F of K_t in C^T(v_j) that contains v_j; hence we project the annotated subgraphs contained in the extended component C^T(v_j) onto the component C^T(v_j) - v_j, thereby omitting the vertex v_j from H if it was contained in H, and in addition we ensure that the K_t subgraphs containing v_j are hit by inserting new annotations that enforce they are hit at a vertex other than v_j. If no graph in '̋_j has an empty vertex set, we recursively call the algorithm on (C^T(v_j) - v_j, '̋_j, λ - 1, κ + 1), resulting in a set S^-_j ∈_t(C^T(v_j) - v_j, '̋_j); note that κ increases in the recursive call. If '̋_j contains a graph on the empty vertex set, then set S^-_j := V(C^T(v_j) - v_j).
    
            Note that S^+_j and S_j^- both belong to _t(C^T(v_j), _̋j) and that S^+_j contains v_j but S^-_j does not (assuming there is any solution that does not contain v_j). When |S^+_j| ≤ |S_j^-|, it effectively tells us we can find a solution to (C^T(v_j), _̋j) that contains v_j (thereby potentially hitting subgraphs of $̋ that intersectT_jin multiple vertices) without additional cost. We will therefore treat the verticesv_jfor which|S^+_j| ≤ |S_j^-|differently from the vertices where we get|S^+_j| > |S_j^-|.
    
            We now proceed as follows. Intuitively, whenever it is possible for a solution in an extended componentC^T(v_j)to contain the attachment pointv_jwithout using more vertices than needed without being forced to contain the attachment point, we do so. LetT'beTminus all verticesv_jfor which|S^+_j| ≤ |S^-_j|. Using a bounded-depth branching algorithm, find a minimum vertex setS_TofG[T']that hits all subgraphs∩̋T'which were not yet hit byT ∖ T', if there is such a vertex set if size at mostκ. (To find such a set, it suffices to run a bounded-depth search tree algorithm with a recursion depth ofκand a branching factor ofmax_H ∈ |V(H)| < t ∈_t(1).)
    
            We now define the output of the algorithm as follows. If the bounded-depth search tree does not find any solution of size at mostκ, we output the trivial solutionV(G). Otherwise, we output the union ofS_T, the setsS^+_jfor the componentsC^T(v_j) - v_jwhere|S^+_j| ≤ |S^-_j|, and the setsS^-_jfor the remaining components. Intuitively, the setsS^+_jandS^-_jtogether hit all the copies ofK_tinG(sinceG[T]isK_t-free) and also hit those subgraphs in$̋ which are fully contained in some C^T(v_j), while the set S_T hits the remaining subgraphs of $̋.
        
    
    This concludes the description of the algorithm.
    
    
    
        Running time.
     We argue that the algorithm runs in timen^_t(λ + κ)^2by analyzing the recursion tree generated by the algorithm.
    
    To bound the depth of the recursion tree, first note that the value ofλ + κnever increases in the algorithm: we decreaseλwhenever we increaseκ. The value of ofλ + κstrictly decreases after every three successive levels of recursion: if we have an iteration in whichλ + κdoes not decrease, it is either because we split on connected components or because we remove the verticesZwhich do not belong to anyK_t-subgraph and make a guess ofZ' = ∅. There cannot be three such recursive calls in a row: after splitting on connected components, the graph is connected; when removing verticesZwhich do not belong to anyK_t-subgraph and splitting on connected components, in the next call the graph will be connected with every vertex in aK_t-subgraph so that we will trigger Case <ref> which decreasesλas it recurses. Since the value ofλ + κdecreases every three successive levels and neither parameter can become negative, the depth of the recursion tree is bounded by(λ + κ).
    
    The branching factor of the algorithm is bounded byn^(κ), since the setsZ' ⊆ Zwe branch on in Case <ref> have size at mostκ; trivially, the number of connected components for which we recurse cannot exceedn. The number of nodes in the recursion tree is bounded by the branching factorn^(κ)raised to the power depth(λ + κ), and is thereforen^((λ + κ)^2).
    
    The time per iteration of the described algorithm is bounded byt^λ + κ· n^(1) + n^_1(λ)⊆ n^_t(λ + κ): the expensive steps are running a bounded-depth search tree algorithm with a recursion depth ofκand branching factor less thant, and invoking <ref>. Multiplying the time spent per node with the total number of nodes, we get a total running time ofn^((λ + κ)^2).
    
    
    
        Correctness.
     Correctness in the base cases is trivial. Below, we treat the various step cases and argue for their correctness. For this argument we use induction on the depth of the recursion tree generated by the recursive call; this is valid since the running time analysis establishes that this depth is finite. Hence we may assume inductively that all recursive calls performed by the algorithm result in an output consistent with the specification of the algorithm.
    
    
      *  When G is disconnected, the algorithm returns the union of recursive calls for the connected components C_1, …, C_m. Note that (C_i) ≤(G) by <ref>. Since each forbidden subgraph is contained entirely within one connected component, we have (G) = ∑_i ∈ [m](C_i) and (G, )̋ = ∑_i ∈ [m](G, _̋C_i). From this, it follows that (C_i, _̋C_i) - (C_i) ≤(G, )̋ - (G). What we have derived so far shows that whenever (G) ≤λ and (G,)̋≤(G) + κ (which requires the algorithm to output an optimal solution), we will have (C_i) ≤λ and (C_i, _̋C_i) ≤(C_i) + κ (which ensures that the recursive call outputs an optimal solution). It follows that the union of the recursively obtained sets is indeed an optimal solution whenever the conditions require the algorithm to output an optimal solution, which proves correctness for this case.
        
      *  We consider the two subcases separately.
        
      *  Suppose first that Z ≠∅. We claim that the vertex set S^* given as output satisfies S^* ∈_t(G,)̋. This is trivial if S^* = V(G). If not, then it is the union of a solution S_Z'∈_t(G - Z, _̋Z') with the set Z'. Since no vertex of Z occurs in any K_t-subgraph by definition, this union trivially hits all copies of K_t. For each forbidden subgraph H ∈$̋ that is not hit byZ', we add the subgraphH ∩ (G-Z)to the collection_̋Z'. SinceS_Z'hits all subgraphs of_̋Z', it follows thatS_Z'∪ Z' ∈_t(G,)̋.
    
            We now argue for optimality in case(G) ≤λand(G,)̋≤(G) + κ. The algorithm considers all subsetsZ' ⊆ Zof size at mostκ. Under the stated condition, for anyS ∈_t(G, )̋we will have|S ∩ Z| ≤κ: we haveS ∖ Z ∈_t(G)since no vertex ofZis contained in aK_t-subgraph, so if|S ∩ Z| > κthen(G) < (G, )̋ - κ, a contradiction. The algorithm therefore considers a choice ofZ'that matches with the intersection of an optimal solution withZ, which is easily seen to lead to a solution of size_t(G,)̋.
    
            
      *  We now deal with the last case, thatZ = ∅. To prove correctness, we first establish that the outputS^*satisfiesS^* ∈_t(G,)̋. This is trivial whenS^* = V(G), so consider the case that it is not. ThenS^*was defined as the union of some setsS^+_j ∈_t(C'_j, _̋j), some setsS^-_j ∈_t(C'_j, _̋j), and a setS_Tthat hits all subgraphs in$̋ which are disjoint from the chosen S^+_j, S^-_j. It is easy to see that S^* ∈_t(G,)̋ for each such union: each K_t-subgraph is fully contained in some component C'_j since G[T] is K_t-free, and hence each K_t-subgraph is hit by the solution S^+_j or S^-_j to the corresponding extended component C'_j. Each forbidden graph H ∈$̋ is either fully contained in someC'_j, or is fully contained inG[T]: since each suchHis a clique, it cannot intersect multiple connected components ofG - T. WhenH ∈$̋ is fully contained in C'_j it is hit by either S^+_j or S^-_j; when H is contained in G[T] and not hit by the chosen vertices, then it is hit by the solution S_T for _̋G[T'_i] that is included in the solution. Hence each candidate solution belongs to _t(G,)̋.
    
            As the last part of the argument, we prove that S^* ∈_t(G,)̋ whenever (G) ≤λ and (G,)̋≤(G) + κ. To do so, we first prove the following claim which says that the computation of S^+_j and S^-_j succeeds in a certain technical sense.
    
            
            If (G,)̋≤(G) + κ, then the sets S^+_j and S^-_j computed for each vertex v_1, …, v_m of T satisfy the following:
            
      *  If (C(v_j), ∩̋C(v_j), v_j) ≠∅, then S^+_j ∈_t(C(v_j), ∩̋C(v_j)).
                
      *  If (C(v_j), ∩̋C(v_j)) = ∅, then S^-_j ∈(C(v_j), ∩̋C(v_j)).
            
            Suppose first that (C(v_j), ∩̋C(v_j), v_j) ≠∅, so that there is an optimal solution to the subproblem that contains the attachment vertex v_j in the root. This means that removing vertex v_j (along with all the subgraphs from $̋ that it hits) from the subinstance, decreases the value of the optimum by one. Hence(C(v_j) - v_j, ∩̋(C(v_j)-v_j)) = (C(v_j), ∩̋(C(v_j)-v_j)) - 1. SinceC(v_j) - v_jis a subgraph ofG-Tand we computedTas a-root ofG, we have(G[C(v_j)] - v_j) ≤(G-T) ≤(G) - 1 ≤λ - 1. Hence the recursive call with parameters(C(v_j) - v_j, ∩̋(C(v_j)-v_j), λ-1, κ)and whose result is combined with{v_j}to obtainS^+_j, has the property that the third parameterλ-1indeed bounds the-value of the graph in the first parameter. Using the fact that(G) = ∑_v ∈ T C(v), it is not difficult to verify that(C(v), ∩̋C(v)) ≤(C(v)) + κusing the assumption(G,)̋≤(G) + κ. Together, this means that the preconditions are satisfied for the invoked recursive call to output an optimal solution. By the induction hypothesis, this means that the result of the recursive call a set belonging to(C(v_j) - v_j, ∩̋(C(v_j)-v_j)); sinceS^+_jwas obtained by taking the union withv_jwe therefore haveS^+_j ∈_t(C(v_j), ∩̋C(v_j)); the optimality of the computed solution follows from the fact that its size is one larger than an optimal solution for(C(v_j) - v_j, ∩̋(C(v_j)-v_j)), whose optimal solutions are in turn one smaller than those in for(C(v), ∩̋C(v_j)). This proves the first item in the statement of the claim.
    
            The argument for the second item uses similar ideas, but is somewhat more subtle: the reason for this is that the recursive call is for the graphC(v_j) - v_jfrom which vertexv_jhas been removed, while to capture the fact that we look for a solution withoutv_j, we have added the projections of allK_t-subgraphs ofC(v_j)intersectingv_jto the annotated set'̋_j. The main observation to handle this complication is the following: in the second case of the claim, we assume that_t(C(v_j), ∩̋C(v_j))is empty. Under this assumption, we have(C(v_j), ∩̋C(v_j)) = (C(v_j) - v_j, '̋_j), with'̋_jas defined during the algorithm. Note that adding the mentioned projections to the annotated set may increase the gap between the costs of optimal solutions for hittingK_t-subgraphs versus solutions that also hit all annotated graphs. However, this gap will increase by at most one, since removal ofv_jdecreases(C(v_j))by at most one. Since we increase the fourth parameter toκ + 1in the recursive call, this ensures that the parameters of the recursive call are such that the specification of the algorithm guarantees it outputs an optimal solution to the instance(C(v_j) - v_j, '̋_j). Due to the projection, this solution also belongs to_t(C(v_j), ∩̋C(v_j)), and since there is no optimal solution to that problem containingv_j, its size is((C(v_j), ∩̋C(v_j)). This completes the proof of the claim.
            
    
            Using <ref> and Lemmata <ref> and <ref> we now complete the correctness proof. Under the active assumption that(G) ≤λand(G,)̋≤(G) + κ, we prove that the computed solutionS^*belongs to_t(G,)̋. <ref> shows that the computed setS^+_jbelongs to_t(C^T(v_j), ∩̋C(v_j))when there is an optimal solution containingv_j; otherwise,S^-_jbelongs to_t(C^T(v_j), ∩̋C(v_j)). From this, together with the fact that the recursively computed sets are valid solutions to the respective subproblems, it follows that if_t(C^T(v_j), ∩̋C(v_j), v_j) ≠∅, thenS^+_jis such a solution and it has size at most|S^-_j|; if no optimal solution containsv_j, thenS^-_j ∈_t(C^T(v_j), ∩̋C(v_j)).
            By applying <ref> separately for each pending component ofT, we obtain that there is an optimal solution in_t(G,)̋that contains the union of all the setsS^+_jforj ∈ T', and the union of all setsS^-_jforj ∈ T ∖ T'. By <ref>, the remaining part of the solution consists of at mostκvertices. Since the only subgraphs which are not hit yet by the chosenS^+_jandS^-_jare those fully contained inG[T]and which are not hit byT', the remainder of an optimal  solution is formed by a hitting set of size at mostκfor these unhit subgraphs. Since the algorithm computes an optimal solution of size at mostκfor this hitting set instance, the union of the obtained sets is indeed an optimal solution.
        
    This concludes the proof.
    
      Let t ≥ 3. There is an algorithm that, given an input (G,) of  and integer λ such that (G) ≤λ, runs in time p_0^(λ,t)(n)=n^_t(λ^2) and outputs the following:
      
      *  the value (G), and
      
      *  whether the instance (G,) is clean.
      
    To compute (G) it suffices to apply <ref> to the tuple (G, :̋= ∅, λ, κ := 0) and take the size of the obtained solution. To determine whether the instance (G,) is clean, we run the algorithm once more on (G, :̋= , λ, κ := 0). If the output given in the second run is equally large as that in the first run, the instance is clean; otherwise it is not.
    
    
    
    § HARDNESS RESULTS
    
    
     In this section we present two  reductions from CNF-SAT, and to transfer the the non-existence of polynomial kernels (under reasonable complexity assumptions), we use the notion of polynomial parameter transformation, introduced by Bodlaender, Thomassé, and Yeo <cit.>.  A polynomial parameter transformation from a parameterized problemPto a parameterized problemQis an algorithm that, given an instance(x,k)ofP, computes in polynomial time an equivalent instance(x',k')ofQsuch thatk'is bounded by a polynomial depending only onk. It follows easily from the definition that ifPdoes not admit a polynomial kernel under some complexity assumption, then the same holds forQ.
    The complexity hypothesis in the following proposition builds on the results by  Fortnow and Santhanam <cit.>.
    
    
     CNF-SAT  does not admit a polynomial kernel parameterized by the number of variables of the input formula, unless NP⊆ coNP/ poly.
    
    
    We are ready to present our main hardness result, which is inspired by other reductions for related problems <cit.>. The crucial issue of this reduction, and its main conceptual novelty, is the following fact: whenHis not a clique, the intersection of an occurrence ofHwith (a subgraph of)G-Xmay be disconnected. We exploit this fact by creating clause gadgets with large minimal blocking sets whose elements are disconnected (in <ref>, each pair of consecutive non-adjacent verticesu,vis an element of a blocking set), and this results in clause gadgets behaving as “chains” where the propagation of information (that is, the vertices picked by the solution) is done without needing edges connecting the elements of the chain (thus, in a “wireless” fashion), easily implying that the corresponding parameter inG-Xis bounded by a constant.
    
    
    Let H be a biconnected graph that is not a clique. The H- Subgraph Hitting (resp. H- Induced Subgraph Hitting) problem does not admit a polynomial kernel parameterized by the size of a given vertex set X of the input graph G such that (G-X) ≤ 1 (resp. (G-X) ≤ 1), unless NP⊆ coNP/ poly.
    
        We present a polynomial parameter transformation from the CNF-SAT problem parameterized by the number of variables, which does not admit a polynomial kernel by <ref>, unless NP⊆ coNP/ poly. We present our reduction for the H-Subgraph Hitting problem, and at the end of the proof we observe that the same reduction applies to H-Induced Subgraph Hitting as well. 
    
        Given a CNF-SAT formula ϕ with n variables x_1,…,x_n and m clauses C_1,…,C_m, we proceed to construct in polynomial time an instance G of H-Subgraph Hitting, together with a set X ⊆ V(G) with (G-X) ≤ 1 and |X| = |V(H)|· n, such that ϕ is satisfiable if and only if G contains a solution of H-Subgraph Hitting of size at most n - m + ∑_j=1^m c_j, where c_j denotes the number of literals in clause C_j. Since |V(H)| is a constant, this would indeed define a polynomial parameter transformation from  CNF-SAT parameterized by the number of variables to  H-Subgraph Hitting  parameterized by the size of a given vertex set X of the input graph G such that (G-X) ≤ 1.
    
        For each variable x_i, we add a disjoint copy of H to G. We call such a copy of H the i-variable-copy of H. For each clause C_j, we add c_j - 1 disjoint copies of H to G, and we order them arbitrarily from 1 to c_j - 1. Moreover, we add two new vertices u_j^0 and v_j^c_j to G.  We call each of these c_j -1 copies of H a j-clause-copy of H. Note that, so far, we have introduced n - m + ∑_j=1^m c_j disjoint copies of H in G.
    
        We now proceed to interconnect these copies of H according to ϕ. Since H is a biconnected graph that is not a clique (hence, it is 2-connected), it follows that |V(H)| ≥ 4. Thus, in particular there exist two  non-adjacent vertices u,v ∈ V(H) and another vertex w ∈ V(H) distinct from u and v. Let H' = H - {u,v,w}. (Even if it is not critical for the proof, note that |V(H')| ≥ 1.) Let also z^+ and z^- be two distinct vertices of H (not necessarily different from u,v,w). We will use the copies of these vertices in the variable-copies and clause-copies of H to interconnect them in G. To this end, for three distinct vertices a,b,c ∈ V(G) and a subgraph F of G isomorphic to H' not containing any of a,b,c, by adding an (a,b,c,V(F))-copy of H to G we mean the operation of, starting from G[{a,b,c}∪ V(F)], adding the missing edges to complete a copy of H, where vertex a (resp. b, c) of G plays the role of vertex w (resp. u, v) of H, and F plays the role of H', with a fixed isomorphism that we suppose to have at hand.
    
        
        For each clause C_j of ϕ, consider an arbitrary ordering of its literals as ℓ_1, …, ℓ_c_j, and recall that G contains c_j - 1 ordered disjoint j-clause-copies of H together with two extra vertices u_j^0 and v_j^c_j. For i ∈ [c_j], we add a new copy of H' to G, which we denote by F_j^i. For i ∈ [c_j -1], let u_j^i and v_j^i be the copies of vertices u and v of H, respectively,  in the i-th j-clause-copy of H. For i ∈ [c_j], if literal ℓ_i of clause C_j corresponds to a positive (resp. negative) occurrence of a variable x_p, let z be the copy of vertex z^+ ∈ V(H) (resp. z^- ∈ V(H)) in the p-variable-copy of H. Then we add a (z,u_j^i-1,v_j^i,V(F_j^i))-copy of H to G, and we call such a copy of H a transversal-copy of H, denoted by H_j^i. We define X  ⊆ V(G) to be the union of the vertex sets of all the variable-copies of H, and note that |X| = |V(H)| · n. This completes the construction of G and X, which is illustrated in <ref>.
    
    
    
    
    
      
        < g r a p h i c s >
    
    
    Example of the construction of graph G in the proof of <ref> for H-Subgraph Hitting. In this example, H is the diamond (that is, K_4 minus one edge), u and v are the only pair of non-adjacent vertices in H, and w is any other vertex. The construction corresponds to a CNF-SAT formula ϕ consisting of two clauses C_1=(x_1 ∨ x_2) and C_2 = (x̅_1 ∨x̅_2 ∨x̅_3 ∨x̅_4), and the satisfying assignment α(x_1)=1, α(x_2)=0, α(x_3)=1, and α(x_4)=0. The variable-copies and clause-copies of H are depicted in blue,  the vertices in the copies of H' = H - {u,v,w} (which is a single vertex) are the white ones, and the vertices in the solution S are the large red ones. Note that clause C_2 is satisfied by both x̅_2 and x̅_4; in the example we have taken x̅_2 as the satisfying literal.
     
        
        
        In the next claim we prove one of the properties claimed in the statement of the theorem.  
    
    
        (G-X) = 1 and (G-X) = 1.
        
        
        Note that each connected component of G-X corresponds to the clause-copies of H associated with a clause C_j and isolated vertices, together with the copies of H' between those j-clause-copies of H and isolated vertices. By construction of G, each such a copy of H', say F_j^i, has at most two neighbors in G-X, namely vertices u_j^i-1 and v_j^i. If an occurrence of H as a subgraph in G-X, say F, contained a vertex of F_j^i, since |V(H')| = |V(H)| -3, necessarily F contains at least one of u_j^i-1 and v_j^i, and at least one more vertex in the (i-1)-th or i-th j-clause-copies of H. Thus, u_j^i-1 or v_j^i is a separator of size one of F, contradicting the hypothesis that H is biconnected.
    
         That is, we have proved that no vertex in a copy F_j^i of H' in G-X is contained in an occurrence of H as a subgraph, hence neither as an induced subgraphs. Therefore, those vertices can be removed while preserving the value of (G-X). Formally,
    
         (G-X) = (G - X - ⋃_j=1^m⋃_i=1^c_j V(F_j^i)),
         
         and the same holds for (G-X). To conclude the proof of the claim, it suffices to note that G - X - ⋃_j=1^m⋃_i=1^c_j V(F_j^i) consists of a disjoint union of clause-copies of H and isolated vertices, and using the fact that  (resp. ) of a disconnected graph is the maximum of  (resp. ) over its connected components, by removing one arbitrary vertex from each such a copy of H we get that (G-X)=1 and (G-X)=1.
        
        
        
        
        
         
        
    
    We now claim that ϕ is satisfiable if and only if G contains a solution S ⊆ V(G) of H-Subgraph Hitting of size at most n - m + ∑_j=1^m c_j. 
    
    
    Suppose first that ϕ is satisfiable and let α: {x_1,…,x_n}→{0,1} be a satisfying assignment of the variables. We define a set S ⊆ V(G) of size n - m + ∑_j=1^m c_j as follows (cf. the red vertices in <ref>). For each variable x_i, if α(x_i)=1  (resp. α(x_i)=0), we add to S the copy of z^+ (resp. z^-) in the i-variable-copy of H, which we denote by z_i^+ (resp. z_i^-). For each clause C_j, let ℓ_s_j be a literal in C_j that is satisfied by the assignment α. Recall that the c_j -1j-clause-copies of H are ordered (arbitrarily) from 1 to c_j - 1. We add to S the vertex set
        { v_j^i | 1 ≤ i ≤ s_j -1  }∪{u_j^i | s_j ≤ i ≤ c_j -1 }.
        In words, we add to S the  copy of vertex v in all the j-clause-copies of H from 1 to s_j -1, and the copy of vertex u in all the j-clause-copies of H from s_j to c_j -1. Note that |S| = n - m + ∑_j=1^m c_j, and it remains to prove that G - S does not contain H as a subgraph.  Note that each variable-copy and clause-copy of H contains exactly two vertices that have neighbors outside of that copy –let us call these vertices boundary vertices of that copy–, and that S contains exactly one of these two boundary vertices for each of these copies of H. Hence, since H is biconnected, no occurrence of H in G-S can contain a non-boundary vertex in a variable-copy or clause-copy of H.
    
    
        Moreover, there do not exist two pairs of integers (i_1,j_1) and (i_2,j_2), with i_1 ≠ i_2 or j_1 ≠ j_2, such that there exists an occurrence F of H in G-S with F ∩ (V(H^i_1_j_1) ∖ X) ≠∅ and F ∩ (V(H^i_2_j_2∖ X) ≠∅.
        
        Indeed, if such (i_1,j_1) and (i_2,j_2) existed, then,
        as |N(V(H^i_j)∖ X) ∩ X| = 1 for any two indices i,j, and as F cannot contain a non-boundary vertex of a variable-copy of H, there would exist z ∈ X such that F ∩ X = {z}, implying that z is a separator of F, contradicting the 2-connectivity of H.
    
    
     Thus, if an occurrence of H in G-S existed, say F, then the above discussion and the construction of G imply that F should be one of the transversal-copies of H. But such an F cannot exist in G-X by the choice of S: either S contains one of the boundary vertices in the two j-clause-copies intersected by F for some j ∈ [m] or, if it is not the case, then S contains the vertex in a variable-copy of H corresponding to the literal that satisfies clause C_j.
    
    
    
    Conversely, let S ⊆ V(G) be a solution of H-Subgraph Hitting of size at most n - m + ∑_j=1^m c_j. Since G contains |S| disjoint variable-copies and clause-copies of H, necessarily S consists of exactly one vertex in each of these copies. Since the boundary vertices in each of the variable-copies and clause-copies of H are the only vertices with neighbors outside of the corresponding copy, we may assume that all the vertices in S are boundary vertices. We define from S a satisfying assignment α of ϕ as follows. If S contains z_i^+ (resp. z_i^-) we set α(x_i)=1  (resp. α(x_i)=0). Let us verify that α indeed satisfies all the clauses of ϕ. Consider an arbitrary clause C_j with c_j literals, and note that S contains c_j - 1 vertices in the j-clause-copies of H. Therefore, there exists s_j ∈ [c_j] such that the s_j-th transversal-copy of H associated with C_j, say F, is  not hit by a vertex in a clause-copy of H. Thus, since S ∩ V(F) ≠∅, necessarily there exists an index i ∈ [n] such that S ∩ V(F) is equal to either z_i^+ or z_i^-, and thus the defined assignment of variable x_i satisfies clause C_j.One direction of the equivalence is proved in the next claim (such a solution S is illustrated by the red vertices in  <ref>).
    
    
    
    
    
    
    
    
    
        To conclude the proof, we claim that the same reduction presented above proves the hardness result for the H-Induced Subgraph Hitting problem. Indeed, in the proof of the equivalence between the satisfiability of ϕ and the existence of a solution S of H-Subgraph Hitting with the appropriate size, all that is relevant to the proof are the variable-copies, clause-copies, and transversal-copies of H. As all these occurrences of H in G occur as induced subgraphs,  the same reduction implies the non-existence of polynomial kernels for  H-Induced Subgraph Hitting.
    
    
    In <ref> we replace the condition “(G-X) ≤ 1” of <ref> with the condition that(G-X)is bounded by a constant.
     
    
    However, in the proof of <ref> we need an extra condition onHstronger than biconnectivity, namely the non-existence of a stable cutset.  The reduction in the proof of <ref>  follows essentially the same lines as the one described in <ref>, but in order to guarantee that(G-X)is bounded by a constant (depending onH), we need to be more careful. Namely, in the interconnection among the variable and clause gadgets, now we cannot afford to add a distinct gadget for each literal in a clause, as it was the case for the copies ofH'in the proof of <ref> (cf. the white vertices in <ref>). Indeed, these copies ofH'can be removed “for free” when dealing with, but it is not the case anymore when dealing with treedepth, as they may blow up the value of(G-X). In a nutshell, we overcome this issue by “reusing” these copies of a (now, carefully chosen) subgraphH' ⊆ Hfor all the literals of the same clause. However, having a single commonH'for each clause may create undesired occurrences ofH(other than the variable-copies, clause-copies, and transversal-copies, as we wish), and preventing the existence of these undesired copies is the reason why we need an assumption onHstronger than  biconnectivity. We now restate <ref> and provide its full proof. 
    
    
    Let H be a graph on h vertices that is not a clique and that has no stable cutset. None of the H- Subgraph Hitting and H- Induced Subgraph Hitting problems admits a polynomial kernel parameterized by the size of a given vertex set X of the input graph G such that (G-X) = Ø(h), unless NP⊆ coNP/ poly.
    
    We again present a polynomial parameter transformation from the CNF-SAT problem parameterized by the number of variables, which does not admit a polynomial kernel by <ref>, unless NP⊆ coNP/ poly. We also present the reduction for the H-Subgraph Hitting problem, and at the end of the proof we observe that the same reduction applies to H-Induced Subgraph Hitting as well. Let h = |V(H)|.
    
        Given a CNF-SAT formula ϕ with n variables x_1,…,x_n and m clauses C_1,…,C_m, we  construct in polynomial time an instance G of the H-Subgraph Hitting problem, together with a set X ⊆ V(G) with (G-X) = Ø(h) and |X| = h · n, such that ϕ is satisfiable if and only if G contains a solution of H-Subgraph Hitting of size at most t, where t will be defined later (cf. <ref>).
        
        
    
        The variable gadgets remain unchanged. Namely, for each variable x_i, we add a disjoint copy of H to G. We call such a copy of H the i-variable-copy of H. Let z^+,z^- be two distinct vertices of H. For i ∈ [n]. we denote the copy of z^+ (resp. z^-) in the i-variable-copy of H by z_i^+ (resp. z_i^-).
    
        Before defining the updated clause gadgets, we need an gadgets. Let A,B ⊆ V(H) be two disjoint non-empty vertex subsets such that there is no edge between A and B and such that |A| + |B| is maximized among all possible candidate pairs. Note that these sets A,B exists because H is not a clique, and let a = |A| and b = |B|. Let w ∈ V(G) ∖ (A ∪ B), and note that such a vertex w exists because H is, in particular, connected. Let H' = H - (A ∪ B ∪{v}). (The fact that H has no stable cutset implies that |V(H')| ≥ 1, but this is not relevant to the proof.)
    
        We now introduce a gadget whose objective is to mimic the behavior of the clause-copies of H in the proof of <ref>, but with the anticomplete sets A,B ⊆ V(H) playing the role of the non-adjacent vertices u,v ∈ V(H) (cf. <ref>). Let s,t be two arbitrary distinct vertices of H, and suppose  without loss of generality that max{a,b} = a. We define the (A,B)-gadget as the graph obtained from 2a disjoint copies of H by identifying, in a circular way, vertex s of a copy with vertex t of the next one. We call these 2a vertices s,t the attachment vertices of the (A,B)-gadget, consider a circular ordering of them from 1 to 2a, following the order of the copies of H, and denote them y_1, y_2, …, y_2a. We define the A-vertices of the (A,B)-gadget as the set {y_i | i ∈[2a], i odd}, and the B-vertices of the (A,B)-gadget as  the set {y_i | i ∈[2a], i even}. That is, the A-vertices consist of the a“even” attachment vertices of the (A,B)-gadget, and the B-vertices consist  the a“odd” attachment vertices. To conclude the construction of the (A,B)-gadget, we add the appropriate edges among the A-vertices so that they induce a graph isomorphic to H[A], and the appropriate edges among an arbitrary subset of size b of the B-vertices so that they induce a graph isomorphic to H[B] (note that it may hold that a >b, and in that case some of the B-vertices are not used to create a copy of H[B]). See <ref> for an illustration.
    
     
    
        < g r a p h i c s >
    
    On the left, a graph H together with two anticomplete disjoint sets A,B ⊆ V(H) with |A|=|B|=2, vertices w,s,t, and the subgraph H' of H. On the right, an (A,B)-gadget, where the two large black (resp. white) vertices correspond to the A-vertices (resp. B-vertices) of the gadget.
    
        The following claim formalizes the fact that any optimal solution of H-Subgraph Hitting in an (A,B)-gadget consists either all the A-vertices, or all the B-vertices.
    
        
         Let S be an optimal solution of H-Subgraph Hitting in an (A,B)-gadget. Then either S= {y_i | i ∈[2a], i odd} or S= {y_i | i ∈[2a], i even}.
        
        Since an (A,B)-gadget contains a disjoint copies of H (regardless of the subgraphs isomorphic to H[A] and H[B] added at end of the construction), necessarily |S| ≥ a. Since H is biconnected, it is easy to verify that either of the sets {y_i | i ∈[2a], i odd} or {y_i | i ∈[2a], i even} is an optimal solution. Finally, note that any solution S needs to contain at least one vertex from each of the a“even” copies of H in the (A,B)-gadget, and at least one vertex from each of the a“odd” copies of H in the (A,B)-gadget. The two sets above are the only ones of size a that hit all these copies of H. Indeed, the latter statement follows, for instance, from the fact that an even cycle has exactly two optimal vertex covers, each of them corresponding to a color class of a proper 2-coloring of the cycle.
        
    
        Equipped with the (A,B)-gadget, we can now define the clause gadgets. One should think of these gadgets as a generalized version of the clause gadgets in <ref> with the role of the vertices u,v ∈ V(H) replaced by the sets A,B ⊆ V(H). Namely,
       for each clause C_j with c_j literals, we add c_j - 1 disjoint (A,B)-gadgets. Let the A-vertices and B-vertices of these gadgets be denoted by {A_j^i | i ∈ [c_j -1]} and {B_j^i | i ∈ [c_j -1]}, respectively. Moreover, we add two graphs with vertex sets A_j^0 and B_j^c_j, both of size a, so that G[A_j^0] is isomorphic to H[A],  and G[B_j^c_j] consists of a subgraph isomorphic to H[B] plus isolated vertices. For i ∈ [c_j], we let B̅_j^i⊆ B_j^i be the subset of B_j^i that induces a graph isomorphic to G[B].
    
       So far, we have introduced n disjoint copies of H in the variable gadgets, and a · (c_j -1) disjoint copies of H for each clause C_j, which amounts to a total budget of
       
        t := n + ∑_j=1^m a · (c_j -1).
    
    
       To interconnect the variable and clause gadgets according to the formula ϕ, we need a generalization of the operation of “adding an (a,b,c,F)-copy of H” defined in the proof of <ref>. For a vertex t ∈ V(G) and three disjoint subgraphs F_1,F_2,F_3 of G not containing t, respectively isomorphic to H[A],H[B], H',
       by adding a (t,V(F_1),V(F_2),V(F_3))-copy of H to G we mean the operation of, starting from G[{t}∪ V(F_1) ∪ V(F_2) ∪ V(F_3)], adding the missing edges to complete a copy of H, where vertex t ∈ V(G) plays the role of vertex w ∈ V(H), and F_1 (resp. F_2,F_3) plays the role of H[A] (resp. H[B], H'), with fixed isomorphisms that we suppose to have at hand.
    
        For each clause C_j of ϕ, consider an arbitrary ordering of its literals as ℓ_1, …, ℓ_c_j, and recall that G contains c_j - 1 ordered disjoint (A,B)-gadgets along with two extra subgraphs isomorphic to H[A] and H[B]. We add a single copy of H' to G, which we denote by F_j (recall that in the proof of <ref> we added a distinct copy F_j^i for each literal in C_j). For i ∈ [c_j], suppose that literal ℓ_i of clause C_j corresponds to an  occurrence of a variable x_p.
        If x_p occurs positively (resp. negatively) in C_j, then
         we add a (z_p^+, A_j^i-1,B̅_j^i, V(F_j))-copy (resp. (z_p^-,A_j^i-1,B̅_j^i, V(F_j))-copy) of H to G, and we call such a copy of H a transversal-copy of H.
    
        We define X  ⊆ V(G) to be the union of the vertex sets of all the variable-copies of H, and note that |X| = h · n. This completes the construction of G and X. 
        
    
    We now prove one of the properties claimed in the statement of the theorem.
    
        (G-X) = Ø(h).
        
         We describe an elimination forest of G-X with the claimed depth. Note that each connected component of G-X corresponds to a clause gadget associated with a clause C_j, consisting of c_j-1 disjoint (A,B)-gadgets, isolated vertices, and two subgraphs isomorphic to H[A] and H[B], all these appropriately attached to the copy F_j of H'. In |V(H')| < h rounds, we can remove the vertices of F_j one by one, and then we are left with isolated vertices, disjoint (A,B)-gadgets and two subgraphs isomorphic to H[A] and H[B]. For each of the latter two graphs, we can terminate in at most (H) rounds. For each of the remaining (A,B)-gadgets, we can first remove its 2a < h attachment vertices, and then we are left with disjoint subgraphs of H, whose treedepth is at most (H). So overall, we have required 2(H) + h = Ø(h) rounds.
        
    
        We now claim that ϕ is satisfiable if and only if G contains a solution S ⊆ V(G) of H-Subgraph Hitting of size at most t.
    
    
        Suppose first that ϕ is satisfiable and let α: {x_1,…,x_n}→{0,1} be a satisfying assignment of the variables. We define a set S ⊆ V(G) of size t as follows. 
        For each variable x_i, if α(x_i)=1  (resp. α(x_i)=0), we add to S the vertex z_i^+ (resp. z_i^-). For each clause C_j, let ℓ_s_j be a literal in C_j that is satisfied by the assignment α. Recall that the c_j -1(A,B)-gadgets associated with C_j are ordered from 1 to c_j - 1. We add to S the vertex set
        { B_j^i | 1 ≤ i ≤ s_j -1  }∪{A_j^i | s_j ≤ i ≤ c_j -1 }.
        In words, we add to S the B-vertices in all the (A,B)-gadgets from 1 to s_j -1, and the A-vertices in all the (A,B)-gadgets from s_j to c_j -1. Note that |S| = t, and it remains to prove that G - S does not contain H as a subgraph. Suppose for contradiction that G - S contains a subgraph F isomorphic to H. The choice of S and  fact that H is biconnected implies that F cannot contain a vertex in a clause gadget that is neither an A-vertex nor a B-vertex, nor a vertex in an i-variable copy of H distinct from z_i^+ and z_i^-. Thus, necessarily F is a subgraph of the union of some (A,B)-gadgets, some copies F_j of H', and some copies of the vertices z^+ and z^- in the variable gadgets. We now distinguish two cases.
    
        Suppose first that F intersects only one clause gadget associated with a clause C_j. The definition of S implies that F cannot be a transversal-copy of H, as all these copies are intersected by S. Thus, F intersects more than one (A,B)-gadget associated with C_j or at least two variable gadgets (or maybe both). We proceed to define two disjoint vertex sets A',B' ⊆ V(F) with no edges between them and such that |A'| + |B'| > |A| + |B|, contradicting the choice of A,B ⊆ V(H). We start with A' (resp. B') being equal to the intersection of F with the A-vertices (resp. B-vertices). For every vertex z of F belonging to an i-variable-copy of H, if any, we proceed as follows. Since F is biconnected, necessarily z is either z_i^+ or z_i^-. We may clearly assume that variable x_i occurs in clause C_j, as otherwise z would not be adjacent to the clause gadget associated with C_j. By construction of S and because z ∉ S, necessarily either all the A-vertices or all the B-vertices associated with the transversal-copy of H containing z belong to S. Note that z is not adjacent to any of the A-vertices or B-vertices in other transversal-copies of H. Hence, z is anticomplete to A' or anticomplete to B'. In the former case, we add t to B', and in the latter we add it to A'. By construction, A' and B' and two disjoint anticomplete subsets of V(F), and they include all the vertices of F except those contained in F_j, the copy of H' associated the clause C_j. Thus,
        |A'| + |B'| ≥ |V(H)| - |V(H')| > |V(H)| - |V(H')| - 1 = |A| + |B|,
        a contradiction to the choice of A,B ⊆ V(H).
    
        It remains two deal with the case where F intersects more than one clause gadget. Since H is biconnected and distinct clause gadgets can be connected only through copies of z^+ and z^- in the variable gadgets, necessarily F contains some of the latter vertices. Let Z={z_1, …, z_q} be the set of copies of z^+ and z^- contained in F. Note that the definition of S implies that Z contains at most one vertex in each i-variable-copy of H, which implies that Z induces an independent set in G. Again by the biconnectivity of H, necessarily |Z| ≥ 2. Since F intersects more than one clause gadget, it follows that Z is a stable cutset of F, a contradiction to the hypothesis that H does not admit such a separator.
    
    
       Conversely, let S ⊆ V(G) be a solution of H-Subgraph Hitting of size at most t. Since G contains t disjoint copies of H in the variables and clause gadgets, necessarily S contains exactly one vertex in each of the variable-copies of H (which can be assumed to be a copy of z^+ or z^-) and, by <ref>, either all the A-vertices or all the B-vertices in each of the (A,B)-gadgets in the clause gadgets.  We define from S a satisfying assignment α of ϕ as follows. If S contains z_i^+ (resp. z_i^-) we set α(x_i)=1  (resp. α(x_i)=0). Let us verify that α indeed satisfies all the clauses of ϕ. Consider an arbitrary clause C_j with c_j literals, and note that S contains a · (c_j - 1) vertices in the clause gadget associated with C_j. Therefore, there exists s_j ∈ [c_j] such that the s_j-th transversal-copy of H associated with C_j, say F, is  not hit by a vertex in a clause gadget. Thus, since S ∩ V(F) ≠∅, necessarily there exists an index i ∈ [n] such that S ∩ V(F) is equal to either z_i^+ or z_i^-, and therefore the defined assignment of variable x_i satisfies clause C_j.
       
       
    
    To conclude the proof, we claim that the same reduction presented above proves the hardness result for the H-Induced Subgraph Hitting problem. Indeed, in the proof of the equivalence between the satisfiability of ϕ and the existence of a solution S of H-Subgraph Hitting with the appropriate size, all that is relevant to the proof are the variable-copies of H, copies of H in the (A,B)-gadgets belonging to the clause gadgets, and transversal-copies of H between the variable and clause gadgets. As all these occurrences of H in G occur as induced subgraphs,  the same reduction implies the non-existence of polynomial kernels for  H-Induced Subgraph Hitting.
    
    Finally, let us mention, even if it is not relevant to our results,  that deciding whether a graphGadmits a stable cutset is -hard, even ifGis assumed to be 2-connected <cit.>.
    
    
    
    § FURTHER RESEARCH
    
    
    In this paper we studied the existence of polynomial kernels for theH-Subgraph Hitting andH-Induced Subgraph Hitting problems under structural parameterizations, namely parameterized by the size of a modulator to a graph classthat has a “simple structure”. Our  main achievement is the identification of two arguably natural graph parametersand(orandfor the induced version) that allowed us to prove complexity dichotomies in terms of the forbidden graphH. Our results pave the way to a systematic investigation of this topic, where we identify the following avenues for further research.
    
    
    
    
        Getting rid of the hypothesis on H.
    
    In our hardness results we need additional assumptions onH, mainly thatHis biconnected in <ref>.
    Observe that the requirement thatHis connected is unavoidable. Indeed, whenHis the union of aK_5and aK_1,3, it is known <cit.> thatH-Subgraph Hitting is  para--hard, even for=0. Moreover, whenHis a non-edge,H- Induced Subgraph Hitting parameterized by vertex cover (which is a larger parameter than) is equivalent to maximum clique parameterized by vertex cover, which does not admit a polynomial kernel under standard complexity assumptions <cit.>.
    Thus, it is natural to wonder whether the biconnectivity hypothesis could be replaced by just connectivity.
    
    
    
    
    
        Improving the degree of the kernel.
     The degree of our polynomial kernel depends on the sizetof the excluded clique and on the valueλof the promised upper bound(G-X) ≤λ. Namely, as stated in <ref>, the kernel has sizeØ_λ,t(|X|^δ(λ,t)), where functionδmainly depends on the upper bound on_tgiven in <ref>. This function behaves as a tower of exponents intof heightλ. Hence, improving the bound on_tdirectly translates to an improvement of the kernel size. We did obtain such an improvement if instead of assuming that(G-X) ≤λ, one assumes that(G-X) ≤λ, namely with a functionλ^λ· 2^λ^2; see <ref>. We leave as an open problem to obtain improved upper bounds for_tin terms ofand. 
    
    
        Computing the modulator.
     In our kernelization algorithm we assume that we are  given a modulator, namely a setX ⊆ V(G)such that(G-X) ≤λ. Note that this hypothesis appears also in the related work dealing with Feedback Vertex Set <cit.>.
    Obtaining a constant factor or even poly(opt)-approximation of the modulator in polynomial time for fixedtandλ, which will be enough for our kernelization algorithm (note that minimizing its size is -hard <cit.>), remains an interesting direction. One may start with the probably simpler cases of a modulator to bounded_H̅-elimination distance or bounded.
    
    
        Finding the right measure.
     The focus of this article is on obtaining kernelization dichotomies as a function of the forbidden (induced) subgraphH. Of course, it is also relevant to characterize, for a fixed graphH, which is the most general (monotone or hereditary) target family_Hsuch thatH-(Induced) Subgraph Hitting admits a polynomial kernel parameterized by the size of a modulator to a graph in_H. Needless to say, solving this general problem seems quite challenging. Indeed, even the case of Vertex Cover, that is,H=K_2, is far from being well understood for monotone or hereditary target graph classes, as
    
    for instance the only known polynomial kernel for Vertex Cover parameterized by a modulator to a bipartite graph (i.e., an odd cycle transversal) is randomized and relies on quite powerful tools <cit.>. One may hope that larger cliques allow for simpler characterizations, the natural first candidate being the case whereHis a triangle. Let_Δbe the, say, hereditary target graph class that we want to characterize. Following the approach of <cit.> that characterized the target  minor-closed graph classes for Vertex Cover, one may hope thatK_3-Subgraph Hitting admits a polynomial kernel parameterized by a modulator to_Δif and only if the graphs in_Δhave bounded_3. With no extra assumption on_Δ, this property is probably false due to the results of Hols, Kratsch, and Pieterse <cit.>, but we conjecture that it is true if we ask_Δto be hereditary and closed under disjoint union, even for hittingK_tfor everyt ≥ 3, replacing_3by_t.
    
    Toward an eventual proof of this conjecture, having unbounded minimal blocking sets seems to permit a generic reduction to obtain the lower bound, in the spirit of the one of <ref> or any similar one in previous work <cit.>. Indeed, Hols, Kratsch, and Pieterse <cit.> show that for Vertex Cover, lower bounds on kernel sizes directly follow from lower bounds on_2.
    
    However, the opposite direction seems way more challenging. In <cit.>, this fact was established for Vertex Cover and minor-closed target classes via the notion of bridge-depth by proving, in particular, that there is a  single minor-obstruction for having large maximum minimal blocking sets, namely the chains of triangles (cf. left part of <ref>). Unfortunately, we cannot hope the same nice behavior forK_3-Subgraph Hitting and monotone or hereditary graph classes, as chains of triangles are still an obstruction in this setting, but there exist other incomparable ones, as depicted in <ref>.
    
    
    
      
        < g r a p h i c s >
    
    
    Two chains of length three incomparable with respect to the (induced) subgraph relation. In both graphs, it can be verified that the set of four red thicker edges is a minimal blocking set.
    
    Finally, in the ambitious quest for finding the appropriate measures that characterize the hereditary or monotone classes_tfor whichK_t-Subgraph Hitting admits a polynomial kernel parameterized by the size of a modulatorXto_t, we hope that the techniques we developed to provide  a polynomial kernel for the case(G-X) ≤λwill play an important role. A natural attempt to generalizeto a more powerful measure is to relax, or even drop, the “weak attachment” condition on the sets to be removed in every round of the elimination process. This raises new challenges for obtaining a polynomial kernel that do not seem easy to overcome, at least with the existing tools in this area.
