Early Earth:

A silicon memory of subduction Subduction processes may have operated very early in Earth history according to the heavy silicon isotope compositions of Archean igneous rocks. The silicon that precipitated out of the Archean oceans as chert was subducted and melted to yield seawater-like heavy isotope signatures in early granitic rocks.

Franck Poitrasson

The geodynamics of early Earth are challenging to decipher, because rock outcrops are limited and their metamorphic histories are complex. In this endeavor, the scientific community is constantly seeking reliable witnesses to the events of early Earth, such as the formation of continental crust from granitoid rocks. In this case, the witnesses are petrological and geochemical tracers that record the early geodynamic setting despite the multiple geological cycles the rocks have subsequently been subjected to. Writing in Nature Geoscience, André et al. 1 and Deng et al. 2 report independent analyses of silicon isotope compositions in igneous rocks from the Archean. They attribute their exceptionally heavy signatures to the recycling of ocean derived silicon, which indicates that silicified crust was subducted in the Archean.

Archean igneous rocks have lost most of their original texture and mineralogy in subsequent metamorphic and melting events through Earth's geological evolution. As a result, studies that attempt to reconstruct the geodynamical setting under which these rocks originally formed rely heavily on tracers, often their chemical and isotopic compositions 3,4 . However, geodynamic reconstructions based on rock chemistries can be misleading, on occasion, even for younger Proterozoic rocks, despite their simpler geological history 5 . As a result, the geodynamic context under which Archean granitoids, and therefore Archean continental crust, originated remains debated 3,6 . Stable isotope compositions of the major element silicon could be good candidates for robust tracers of this context, because they have been shown to be resistant to metamorphic and metasomatic processes 7 . This resistance sets silicon apart from a number of trace elements, and even from the isotope signature of the main rock-forming element, oxygen.

André et al. 1 and Deng et al. 2 build on the silicon isotope composition database of more recent, Phanerozoic magmatic felsic rocks 8,9 with bulk rock, silicon isotope analyses of 4.0 to 2.6 billion year old granitoid samples from South Africa 1 , Greenland, Canada, Siberia and Scandinavia 2 . Both studies find that Archean granitic igneous rocks have heavier silicon isotope compositions than any terrestrial magmatic rocks analyzed so far. Hence, a particularly heavy silicon isotope composition seems typical for granitoid rocks from that time. Such heavy silicon isotope compositions have not been recorded in modern igneous rocks; they are, however, found in present-day seawater and in cherts that represent aqueous silica precipitated from ancient seawater 7 . Therefore, both studies interpreted the heavy silicon isotope compositions of ancient granitoids as an indicator of a source that involved cherts precipitated from seawater, interspersed in the basaltic seafloor (Fig. 1).

An imprint of seawater-derived silica was previously hinted at by a small deviation towards heavy silicon isotope compositions in modern-style, subduction-derived Phanerozoic volcanic rocks 8 . For the early Earth, a previous study looked for heavy silicon enrichment through the study of zircons extracted from sedimentary rocks 10 which supported a seawater origin for silicon. However, the analytically less challenging, but more precise bulk-rock analyses of André et al 1 and Deng et al 2 required fewer interpretative steps. Furthermore, they revealed much larger isotopic deviations in Archean igneous rocks compared with the Phanerozoic samples 8 .

The large silicon deviation in the Archean probably reflects that the Earth differed in at least two important ways in the Archean when compared to more recent Phanerozoic times (Fig. 1). First, the Archean oceans were less affected by life. Biological activity decreased the dissolved silica content in the Phanerozoic oceans by at least one order of magnitude relative to the Archean ocean 11 . In the more ancient seawater, silica was therefore closer to its saturation, which led to more abundant silica precipitation and the formation of cherts on the seafloor. Secondly, Archean Earth was much hotter, with a stronger mantle geothermal gradient. As a result, if subduction was already in operation in Archean times, subductionrelated magmatic rocks could have been generated from the direct melting of the subducting oceanic lithosphere rather than from the partial melting of the mantle wedge thank to fluids exsolved from the subducting slab as is the case in modern, cooler subduction 4 . Indeed, Deng et al. 2 specifically argued that the heavy silicon isotope composition of Archean granitoids is a direct tracer of hot subduction acting as early as 4 Gy ago on Earth. Taken together, due to limited biological activity, the Archean oceanic crust was richer in seawater-derived cherts that carried the heavy, seawater-derived silicon into a hotter geotherm where it was directly melted to produce subduction-related magmas with isotopically heavier silicon isotope signatures than igneous rocks formed in modern-style subduction. By contrast, in modernstyle, subduction-related andesites, the small amount of seawater-derived silicon comes from fluids from the dehydrating subducted seafloor that contains less chert due to the biological removal of silicon from the oceans. day. In the Archean (left), limited biological activity meant the dissolved silicon content of the oceans was higher than today. As a result, a larger proportion of isotopically heavy marine silicon precipitated as cherts in the aging oceanic crust. Furthermore, hot subduction at that time would have faciliatated partial melting of the oceanic slab that contained the cherts, instead of just the mantle wedge above the subducting plate as in current times (Right).

Together, chert precipitation and hot subduction can explain the heavy silicon isotope composition of Archean igneous rocks measured by Andre et al. 1 and Deng et al. 2 who conclude that seawater was strongly involved in the formation of granitoids on early Earth.

The relative proportion of components and slopes are not to scale.

  André et al.1 and Deng et al.2 find that Archean seawater played an important role in the formation of granitoids on early Earth. Deng et al. specifically suggest that subduction of silicified crust generated the heavy silicon isotope imprint of seawater left in these samples. Silicon isotopes therefore provide a key argument in favor of the controversial geodynamic hypothesis that horizontal plate tectonics occurred as early in the Earth's history as the Archean. Franck Poitrasson is at the Géosciences Environnement Toulouse laboratory, UMR 5563 CNRS-UPS-IRD-CNES, France. Email: Franck.Poitrasson@get.omp.eu 11 Siever, R. Geochim. Cosmochim. Acta 56, 3265-3272 (1992).

Figure 1 :

 1 Figure 1: Comparison of the silicon geodynamic cycling between the Archean and present


Edouard Bonnet
email: edouard.bonnet@ens-lyon.fr

Nicolas Bousquet
email: nicolas.bousquet@grenoble-inp.fr

Pierre Charbit
email: charbit@irif.fr

Stéphan Thomassé
email: stephan.thomasse@ens-lyon.fr

Rémi Watrigant
email: remi.watrigant@ens-lyon.fr

Édouard Bonnet

Parameterized Complexity of Independent Set in H-free Graphs

Keywords: Parameterized Algorithms, Independent Set, H-Free Graphs

come   L'archive ouverte pluridisciplinaire

Introduction

Given a simple graph G, a set of vertices S ⊆ V (G) is an independent set if the vertices of this set are all pairwise non-adjacent. Finding an independent set with maximum cardinality is a fundamental problem in algorithmic graph theory, and is known as the MIS problem (MIS, for short) [START_REF] Garey | Computers and Intractability: A Guide to the Theory of NP-Completeness[END_REF]. In general graphs, it is not only N P -hard, but also not approximable within O(n 1-) for any > 0 unless P = N P [START_REF] Zuckerman | Linear degree extractors and the inapproximability of max clique and chromatic number[END_REF], and W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard parameterized by the solution size [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF] (unless otherwise stated, n always denotes the number of vertices of the input graph). Thus, it seems natural to study the complexity of MIS in restricted graph classes. One natural way to obtain such a restricted graph class is to forbid some given pattern to appear in the input. For a fixed graph H, we say that a graph is H-free if it does not contain H as an induced subgraph. Unfortunately, it turns out that for most graphs H, MIS in Hfree graphs remains N P -hard, as shown by a very simple reduction observed independently by Poljak [START_REF] Poljak | A note on stable sets and colorings of graphs[END_REF] and Alekseev [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]:

Theorem 1 ( [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF][START_REF] Poljak | A note on stable sets and colorings of graphs[END_REF]) Let H be a connected graph which is neither a path nor a subdivision of the claw. Then MIS is NP-hard in H-free graphs.

On the positive side, the case of P t -free graphs has attracted a lot of attention during the last decade. While it is still open whether there exists t ∈ N for which MIS is N P -hard in P t -free graphs, quite involved polynomial-time algorithms were discovered for P 5 -free graphs [START_REF] Lokshtanov | Independent set in P 5 -free graphs in polynomial time[END_REF], and very recently for P 6free graphs [START_REF] Grzesik | Polynomial-time algorithm for maximum weight independent set on p6-free graphs[END_REF]. In addition, we can also mention the recent following result: MIS admits a subexponential algorithm running in time 2 O( √ tn log n) in P t -free graphs for every t ∈ N [START_REF] Bacsó | Subexponential-time algorithms for maximum independent set in P t-free and broom-free graphs[END_REF].

The second open question concerns subdivisions of the claw. Let S i,j,k be a tree with exactly three vertices of degree one, being at distance i, j and k from the unique vertex of degree three. The complexity of MIS is still open in S 1,2,2free graphs and S 1,1,3 -free graphs. In this direction, the only positive results concern some subcases: it is polynomial-time solvable in (S 1,2,2 , S 1,1,3 , dart)free graphs [START_REF] Karthick | Independent sets in some classes of S i,j,k -free graphs[END_REF], (S 1,1,3 , banner)-free graphs and (S 1,1,3 , bull)-free graphs [START_REF] Karthick | Maximum weight independent sets in classes related to claw-free graphs[END_REF],

where dart, banner and bull are particular graphs on five vertices.

Given the large number of graphs H for which the problem remains N Phard, it seems natural to investigate the existence of fixed-parameter tractable (FPT) algorithms 1 , that is, determining the existence of an independent set of size k in a graph with n vertices in time f (k)n c for some computable function f and constant c. A very simple case concerns K r -free graphs, that is, graphs excluding a clique of size r. In that case, Ramsey's theorem implies that every such graph G admits an independent set of size Ω(n 1 r-1 ), where n = |V (G)|.

In the FPT vocabulary, it implies that MIS in K r -free graphs has a kernel with O(k r-1 ) vertices.

To the best of our knowledge, the first step towards an extension of this observation within the FPT framework is the work of Dabrowski et al. [START_REF] Dabrowski | Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number[END_REF] (see also Dabrowski's PhD manuscript [START_REF] Dabrowski | Structural solutions to maximum independent set and related problems[END_REF]) who showed, among others, that for any positive integer r, Max Weighted Independent Set is FPT in H-free graphs when H is a clique of size r minus an edge. In the same paper, they settle the parameterized complexity of MIS on almost all the remaining cases of H-free graphs when H has at most four vertices. The conclusion is that the problem is FPT on those classes, except for H = C 4 which is left open. We answer this question by showing that MIS remains W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard in a subclass of C 4 -free graphs. On the negative side, it was proved that MIS remains W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard in K 1,4 -free graphs [START_REF] Hermelin | Parameterized complexity of induced graph matching on claw-free graphs[END_REF] We can also mention the case where H is the bull graph, which is a triangle with a pending vertex attached to two different vertices. For that case, a polynomial Turing kernel was obtained [START_REF] Thomassé | A Polynomial Turing-Kernel for Weighted Independent Set in Bull-Free Graphs[END_REF] then improved [START_REF] Du Cray | Improved FPT algorithms for weighted independent set in bull-free graphs[END_REF].

Finally, a subset of this paper's authors recently settled several other cases [5], such as the cricket graph, the P graph, or the path of size four where all but one endpoint are replaced by a clique of fixed size.

Our results

In Section 2, we present three reductions proving W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hardness of MIS in graphs excluding several graphs as induced subgraphs, such as K 1,4 , any fixed cycle of length at least four, and any fixed tree with two branching vertices.

We actually show the stronger result that MIS remains W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard in graphs simultaneously excluding these graphs as induced subgraphs. We propose a definition of a graph decomposition whose aim is to capture all graphs which can be excluded using our reductions.

In Section 3, we extend the polynomial algorithm of Alekseev when H is a disjoint union of edges to an FPT algorithm when H is a disjoint union of cliques.

In Section 4, we present a general framework extending the technique of iterative expansion, which itself is the maximization version of the well-known iterative compression technique. We apply this framework to provide FPT algorithms when H is a clique minus a complete bipartite graph, when H is a clique minus a triangle, and when H is the so-called gem graph.

Finally, in Section 5, we focus on the existence of polynomial (Turing) kernels. We first strenghten some results of the previous section by providing polynomial (Turing) kernels in the case where H is a clique minus a claw.

Then, we prove that for many H, MIS on H-free graphs does not admit a polynomial kernel, unless N P ⊆ coN P/poly.

Our results allow to obtain the complete quatrochotomy polynomial/polynomial kernel (PK)/no PK but polynomial Turing kernel/W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard for all possible graphs on four vertices.

Notation

For classical notation related to graph theory or fixed-parameter tractable algorithms, we refer the reader to the monographs [START_REF] Diestel | Graph Theory, 4th Edition[END_REF] and [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF], respectively.

For an integer r 2 and a graph H with vertex set V (H) = {v 1 , . . . , v n H }

with n H r, we denote by K r \ H the graph with vertex set {1, . . . , r} and

edge set {ab : 1 a, b r such that v a v b / ∈ E(H)}. For X ⊆ V (G), we write G \ X to denote G[V (G) \ X].
For two graphs G and H, we denote by G H the disjoint union operation, that is, the graph with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H). We denote by G + H the join operation of G and H, that is, the graph with vertex set V (G) ∪ V (H) and edge set E(G) ∪ E(H) ∪ {uv : u ∈ V (G), v ∈ V (H)}. For two integers r, k, we denote by Ram(r, k) the Ramsey number of r and k, i.e. the number such that every graph with at least Ram(r, k) vertices contains either a clique of size r or an independent set of size k. We write for short Ram(k) = Ram(k, k).

Finally, for , k > 0, we denote by Ram (k) the minimum order of a complete graph whose edges are colored with colors to contain a monochromatic clique of size k. The following bounds are known: Ram(r, k)

r+k-2 r-1 = r+k-2 k-1 ,
and Ram (k) k k .

2 W [1]-hardness

Main reduction

We show the following:

Theorem 2 For any p 1 4 and p 2 1, MIS remains W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard in graphs excluding simultaneously the following graphs as induced subgraphs:

-K 1,4

-C 4 , . . . , C p1

any tree T with two branching vertices2 at distance at most p 2 .

Proof. Let p = max{p 1 , p 2 }. We reduce from Grid Tiling, where the input

is composed of k 2 sets S i,j ⊆ [m] × [m] (0 i, j k -1), called tiles, each Ti,j Ri,j Li,j Bi,j Gadget T Gi,j Li,j+1 Ri,j-1
Fig. 1 Gadget T G i,j representing a tile and its adjacencies with T G i,j-1 and T G i,j+1 , for p = 1. Each circle is a main clique on n vertices: dashed cliques are the cycle cliques (those of them connected to three other cliques are branching cliques), while others are path cliques. Black, blue and red arrows represent respectively type T h , Tr and Tc edges (bold arrows are between two gadgets). Figures 2 and3 represent some adjacencies in more details.

composed of n elements. The objective of Grid Tiling is to find an element s * i,j ∈ S i,j for each 0 i, j k -1, such that s * i,j agrees in the first coordinate with s * i,j+1 , and agrees in the second coordinate with s * i+1,j , for every 0 i, j k -1 (here and henceforth, i + 1 and j + 1 are taken modulo k). In such case, we say that {s * i,j , 0 i, j k -1} is a feasible solution of the instance.

It is known that Grid Tiling is W [1]-hard parameterized by k [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Marx | Parameterized complexity of independence and domination on geometric graphs[END_REF].

Before describing formally the reduction, let us give some definitions and ideas. Given s = (a, b) and s = (a , b ), we say that s is row-compatible (resp.

column-compatible) with s if a a (resp. b b ) 3 . Observe that a solution {s * i,j , 0 i, j k -1} is feasible if and only if s * i,j is row-compatible with s * i,j+1 and column-compatible with s * i+1,j for every 0 i, j k -1.

We will represent each tile by a gadget partitioned into a constant number of cliques of size n. The vertices of each clique are in one-to-one correspondence with the elements of the corresponding tile. Overall the cliques will be arranged in a grid-like structure with degree three. By that we mean that a clique will be linked to at most three other cliques. While most of the cliques will have only two neighboring cliques, a clique linked to three other cliques will be called branching clique. The row-compatibility (resp. column-compatibility) will be encoded with a relatively simple interaction between two adjacent cliques. The main difficulty will be to prevent the undesired induced subgraphs to appear in the vicinity of branching cliques. We now formally describe the reduction.

Fig. 2 Adjacencies between cycle cliques (represented by dashed circles in Figure 1).

Fig. 3 Two consecutive tiles and the representation of their adjacencies (representing type Tr adjacencies).

Tile gadget.

For every tile S i,j = {s i,j 1 , . . . , s i,j n }, we construct a tile gadget T G i,j , depicted in Figure 1. Notice that this gadget shares some ideas with the W Finally, the clique corresponding to the vertex of degree one in the path at-

tached to c 1 (resp. c p+2 , c 2p+3 , c 3p+4 ) is called the top (resp. right, bottom, left) clique of T G i,j , denoted by T i,j (resp. R i,j , B i,j , L i,j ). Let T i,j = {t i,j 1 , . . . , t i,j n }, R i,j = {r i,j 1 , . . . , r i,j n }, B i,j = {b i,j 1 , . . . , b i,j n }, and L i,j = { i,j 1 , . . . , i,j n }.
For the sake of readability, we might omit the superscripts i, j when it is clear from the context.

Lemma 1 Let K be an independent set of size 8(p + 1) in T G i,j . Then:

(a) K intersects all the cycle cliques on the same index x ∈ [n];

(b) if K∩T i,j = {t xt }, K∩R i,j = {r xr }, K∩B i,j = {b x b }, and K∩L i,j = { x }.

Then:

s i,j

x is row-compatible with s i,j x which is row-compatible with s i,j xr , and

-s i,j xt is column-compatible with s i,j
x which is column-compatible with s i,j x b .

Proof. Observe that the vertices of T G i,j can be partitioned into 8(p + 1) cliques (the main cliques), hence an independent set of size 8(p + 1) intersects each main clique on exactly one vertex. Let C 1 , C 2 and C 3 be three consecutive cycle cliques, and suppose

K intersects C 1 (resp. C 2 , C 3 ) on the x th 1 (resp. x th 2 ,
x th 3 ) index. By definition of the gadget, it implies x 1 x 2 x 3 . By applying the same argument from C 3 along the cycle, we obtain x 3 x 1 , which proves (a). The proof of (b) directly comes from the definition of the adjacencies between cliques of type T r and T c , and from the fact that K intersects all cycle cliques on the same index.

Attaching gadgets together.

For i, j ∈ {0, . . . , k -1}, we connect the right clique of T G i,j with the left clique of T G i,j+1 in a "type T r spirit": for every x, y

∈ [n], connect r i,j x ∈ R i,j with i,j+1 y ∈ L i,j+1 iff s i,j
x is not row-compatible with s i,j+1 y . Similarly, we connect the bottom clique of T G i,j with the top clique of T G i+1,j in a "type

T c spirit": for every x, y ∈ [n], connect b i,j x ∈ B i,j with t i+1,j y ∈ T i+1,j iff s i,j
x is not column-compatible with s i+1,j y (all incrementations of i and j are done modulo k). This terminates the construction of the graph G.

i,j . Moreover, if K ∩ R i,j = {r i,j x } and K ∩ L i,j+1 = { i,j+1 x },
then, by construction of G, s i,j

x is row-compatible with s i,j+1

x . Similarly, if

K ∩ B i,j = {b i,j x } and K ∩ T i+1,j = {t i+1,j
x }, then, by construction of G, s i,j

x is column-compatible with s i+1,j

x

. By Lemma 1, it implies that s i,j xi,j is rowcompatible with s i,j+1 xi,j+1 and column-compatible with s i+1,j xi+1,j (incrementations of i and j are done modulo k), thus {x i,j xi,j : 0 i, j k -1} is a feasible solution. Using similar ideas, one can prove that a feasible solution of the grid tiling instance implies an independent set of size k in G.

Structure of the obtained graph.

Let us now prove that G does not contain the graphs mentioned in the statement as an induced subgraph:

No K 1,4 . We first prove that for every 0 i, j k -1, the graph induced by the cycle cliques of T G i,j is claw-free. For the sake of contradiction, suppose that there exist three consecutive cycle cliques A, B and C containing a claw. No tree T with two branching vertices at distance at most p 2 .

Using the same argument as for the K 1,4 case, observe that the claws contained in G can only appear in the cycle cliques where the paths are attached.

However, observe that these cliques are at distance 2(p + 1) > p 2 , thus, such a tree T cannot appear in G.

As a direct consequence of Theorem 2, we get the following by setting

p 1 = p 2 = |V (H)| + 1:
Corollary 1 If H is not chordal, or contains as an induced subgraph a K 1,4

or a tree with two branching vertices, then MIS in H-free graphs is W [1]-hard.

Capturing Hard Graphs

We introduce two variants of the hardness construction of Theorem 2, which we refer to as the first construction. The second construction is obtained by replacing each interaction between two main cliques by an anti-matching, except the one interaction in the middle of the path cliques which remains a half-graph (see Figure 4, middle). In an anti-matching, the same elements in the two adjacent cliques define the only non-edges. The correctness of this new reduction is simpler since the propagation of a choice is now straightforward. Observe however that the graph C 4 appears in this new construction.

For the third construction, we start from the second construction and just add an anti-matching between two neighbors of each branching clique among the cycle cliques (see Figure 4, right). This anti-matching only constrains more the instance but does not destroy the intended solutions; hence the correctness.

To describe those connected graphs H which escape the disjunction of Theorem 2 (for which there is still a hope that MIS is FPT), we define a decomposition into cliques, similar yet different from clique graphs or tree decompositions of chordal graphs (a.k.a k-trees).

Fig. 4 A symbolic representation of the hardness constructions. To the left, only half-graphs (blue) are used between the cliques, as in the proof of Theorem 2. In the middle and to the right, the half-graphs (blue) are only used once in the middle of each path of cliques, and the rest of the interactions between the cliques are anti-matchings (red). The third construction (right) is a slight variation of the second (middle) where for each branching clique, we link by an anti-matching its two neighbors among the cycle cliques.

Definition 1 Let T be a graph on vertices t 1 , . . . , t . We say that T is a clique decomposition of H if there is a partition of V (H) into (C 1 , C 2 , . . . , C ) such that:

-

for each i ∈ [ ], H[C i ] is a clique, and
-for each pair i = j ∈ [ ], if H[C i ∪ C j ] is connected, then t i t j ∈ E(T ).
Observe that, in the above definition, we do not require T to be a tree. -

for each i ∈ [ ], H[C i ] is a clique, -for each t i t j ∈ E(T ), H[C i ∪ C j ] is a clique, and
for each t i t j / ∈ E(T ), there is no edge between C i and C j .

An equivalent way to phrase this definition is that H can be obtained from T by adding false twins. Adding a false twin v to a graph consists of duplicating one of its vertex v (i.e., v and v have the same neighbors) and then adding an edge between v and v .

We define almost strong clique decompositions which informally are strong clique decompositions where at most one edge can be missing in the interaction between two adjacent cliques.

Definition 3 Let T be a graph on vertices t 1 , . . . , t . We say that T is an almost strong clique decomposition of H if there is a partition of V (H) into (C 1 , . . . , C ) such that:

-

for each i ∈ [ ], H[C i ] is a clique, -for each t i t j ∈ E(T ), H[C i ∪ C j ] is a clique potentially deprived of a single
edge, and is connected, and for each t i t j / ∈ E(T ), there is no edge between C i and C j .

Finally, a nearly strong clique decomposition is slightly weaker than an almost strong clique decomposition: at most one interaction between two adjacent cliques is only required to be C 4 -free. Formally:

Definition 4 Let T be a graph on vertices t 1 , . . . , t with a special edge t a t b . We say that T is a nearly strong clique decomposition of H if there is a partition of V (H) into (C 1 , . . . , C ) such that:

-

for each i ∈ [ ], H[C i ] is a clique, -H[C a ∪ C b ] is C 4 -free, -for each t i t j ∈ E(T ) \ {t a t b }, H[C i ∪ C j ] is a clique potentially deprived of
a single edge, and is connected, and for each t i t j / ∈ E(T ), there is no edge between C i and C j .

Let P be the set of all the paths. Notice that T 1 \ P is the set of all the subdivisions of the claw.

Theorem 3 Let H be a fixed connected graph. If no P ∈ P is a nearly strong clique decomposition of H and no T ∈ T 1 \ P is an almost strong clique de-

composition of H, then MIS in H-free graphs is W [1]-hard.
Proof. The idea is to mainly use the second construction and the fact that MIS in C 4 -free graphs is W [1]-hard (due to the first construction). For every fixed graph H which cannot be an induced subgraph in the second construction,

MIS is W [1]-hard.
To appear in this construction, the graph H should have either a clique decomposition on a subdivision of the claw, such that the interaction between two adjacent cliques is the complement of a (non necessarily perfect) matching, or a clique decomposition on a path, such that the interaction between two adjacent cliques is the complement of a matching, except for at most one interaction which can be a C 4 -free graph.

We now just observe that in both cases if, among the interactions between adjacent cliques, one complement of matching has at least two non-edges, then In the strong clique decomposition, the interaction between two adjacent cliques is very simple: their union is a clique. Therefore, it might be tempting to conjecture that if H admits T ∈ T 1 as a strong clique decomposition, then

H
MIS in H-free graphs is FPT. Indeed, those graphs H appear in both the first and the second W [1]-hardness constructions. Nevertheless, we will see that

this conjecture is false: even if H has a strong clique decomposition T ∈ T 1 , it can be that MIS is W [1]-hard.
The simplest tree of T 1 \ P is the claw. We denote by T i,j,k the graph obtained by adding a universal vertex to the disjoint union of three cliques

K i K j K k .
The claw is a strong clique decomposition of T i,j,k (for every natural numbers i, j, k).

Theorem 4 MIS in T 1,2,2 -free graphs is W [1]-hard.
Proof. We show that T 1,2,2 does not appear in the third construction ( We first study how the cricket can appear in a path of cliques. Let C be the main clique containing the universal vertex of the cricket. This vertex is adjacent to three disjoint cliques K 1 K 1 K 2 . Due to the previous claim, the only way to distribute them is to put K 1 in the previous main clique, K 1 in the same main clique C, and K 2 in the next main clique. This is only possible if the interaction between C and the next main clique is a half-graph. In particular, this implies that the interaction between the previous main clique and C is an anti-matching. This situation corresponds to the left of Figure 5.

This also implies that the cricket cannot appear in a path of cliques without a half-graph interaction (anti-matchings only). We now turn our attention to the vicinity of a triangle of main cliques, which is proper to the third construction. By our previous remarks, we know that the universal vertex of Fig. 5 The two ways the cricket appears in the third construction. The red edges between two adjacent cliques symbolize an anti-matching, whereas the blue edge symbolizes a C 4free graph. In the left hand-side, one neighbor of the universal vertex with degree 2 could alternatively be in the same clique as the universal vertex.

the cricket has to be either alone in a main clique (by symmetry, it does not matter which one) of the triangle, or with exactly one of its neighbors of degree 2. Now, the only way to place K 1 K 1 K 2 is to put the two K 1 in the two other main cliques of the triangle, and the K 2 (or the single vertex rest of it) in the remaining adjacent main clique. Indeed, if the K 2 is in a main clique of the triangle, the K 1 in the third main clique of the triangle would have two nonedges towards to K 2 . This is not possible with an anti-matching interaction.

Therefore, the only option corresponds to the right of Figure 5.

To obtain a T 1,2,2 , one needs to find a false twin to one of the leaves of the cricket. This is not possible since, in both cases, the two leaves are in two adjacent cliques with an anti-matching interaction. Therefore, adding the false twin would create a second non-neighbor to the remaining leaf.

The graph T The toughest challenge towards the dichotomy is understanding MIS in the absence of paths of cliques 5 . In Theorem 11, we make a very first step in that direction: we show that for every graph H with a strong clique decomposition on P 3 , the problem is FPT. In the previous paragraphs, we dealt mostly with connected graphs H. In Theorem 6, we show that if H is a disjoint union of cliques, then MIS in H-free graphs is FPT. In the language of clique decompositions, this can be phrased as H has a clique decomposition on an edgeless graph.

5 Actually, even the classical complexity of MIS in the absence of long induced paths is not well understood 3 Positive results I: disjoint union of cliques For r, q 1, let K q r be the disjoint union of q copies of K r . The proof of the following theorem is inspired by the case r = 2 by Alekseev [START_REF] Alekseev | On the number of maximal independent sets in graphs from hereditary classes[END_REF].

Theorem 6 Maximum Independent Set is FPT in K q r -free graphs.

Proof. We will prove by induction on q that a K q r -free graph has an independent set of size k or has at most Ram(r, k) qk n qr independent sets. This will give the desired FPT-algorithm, as the proof shows how to construct this collection of independent sets. Note that the case q = 1 is trivial by Ramsey's theorem. We also assume r ≥ 3, since the case r = 2 corresponds to Alekseev's algorithm [START_REF] Alekseev | On the number of maximal independent sets in graphs from hereditary classes[END_REF].

Let G be a K q r -free graph and let < be any fixed total ordering of V (G) such that the largest vertex in this ordering belongs to a clique of size r (the case where G is K r -free is trivial by Ramsey's theorem). Since a clique of size r can be found in polynomial time, such an ordering can be found in polynomial time. For any vertex x, define x + = {y, x < y} and

x -= V (G) \ x + .
Let us first explain how we will generate independent sets. We will prove next that the algorithm generates all of them. Let C be a fixed clique of size r in G and let c be the largest vertex of C with respect to <. Let V 1 be the set of vertices of c + which have no neighbor in C. Note that V 1 induces a K q-1 r free graph, so by induction either it contains an independent set of size k, and so does G, or it has at most Ram(r, k) (q-1)k n (q-1)r independent sets. In the latter case, let S 1 be the set of all independent sets of G

[V 1 ]. Now in a
second phase we define an initially empty set S C and do the following. For each independent set S 1 in S 1 (including the empty set), we denote by V 2 the set of vertices in c -that have no neighbor in S 1 . For every choice of a vertex x amongst the largest Ram(r, k) vertices of V 2 in the order, we add x to S 1 and modify V 2 in order to keep only vertices that are smaller than x (with respect to <) and non adjacent to x. We repeat this operation k -1 times (or until V 2 becomes empty). At the end, we either find an independent set of size k (if V 2 is still not empty) or add S 1 to S C (when V 2 becomes empty). By doing so we construct a family of at most Ram(r, k) k independent sets for each S 1 , so in total we get indeed at most Ram(r, k) kq n (q-1)r independent sets for each clique C. Finally we define S as the union over all r-cliques C of the sets S C , so that S has size at most the desired number.

We claim that if G does not contain an independent set of size k, then S contains all independent sets of G. It suffices to prove that for every independent set S, there exists a clique C for which S ∈ S C . Let S be an independent set, and define C to be a clique of size r such that its largest vertex c (with respect to <) satisfies the conditions:

no vertex of C is adjacent to a vertex of S ∩ c + , and c is the smallest vertex such that a clique C satisfying the first item exists.

First remark that such a clique always exist, since we assumed that the largest vertex c last of < is contained in a clique of size r, which means that S ∩ c + last is empty and thus the first item is vacuously satisfied. Secondly, note that several cliques C might satisfy the two previous conditions. In that case, pick one such clique arbitrarily. This definition of C and c ensures that S ∩ c + is an independent set in the set V 1 defined in the construction above (it might be empty). Thus, it will be picked in the second phase as some S 1 in S 1 and for this choice, each time V 2 is considered, the fact that C is chosen to minimize its largest element c guarantees that there must be a vertex of S in the Ram(r, k) largest vertices in V 2 , otherwise we could find within those vertices an r-clique contradicting the choice of C (we can find an r-clique satisfying both points such that the maximum vertex is smaller than c). So it ensures that we will add S to the collection S C , which concludes our proof.

4 Positive results II

Key ingredient: Iterative expansion and Ramsey extraction

In this section, we present the main idea of our algorithms. It is a generalization of iterative expansion, which itself is the maximization version of the well-known iterative compression technique. Iterative compression is a useful tool for designing parameterized algorithms for subset problems (i.e. problems where a solution is a subset of some set of elements: vertices of a graph, variables of a logic formula...etc.) [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Reed | Finding odd cycle transversals[END_REF]. Although it has been mainly used for minimization problems, iterative compression has been successfully applied for maximization problems as well, under the name iterative expansion [7].

Roughly speaking, when the problem consists of finding a solution of size at least k, the iterative expansion technique consists of solving the problem where a solution S of size k -1 is given in the input, in the hope that this solution will imply some structure in the instance. In the following, we consider an extension of this approach where, instead of a single smaller solution, one is given a set of f (k) smaller solutions S 1 , . . . , S f (k) . As we will see later, we can further add more constraints on the sets S 1 , . . . , S f (k) . Notice that all the results presented in this sub-section (Lemmas 2 and 3 in particular) hold for any hereditary graph class (including the class of all graphs). The use of properties inherited from particular graphs (namely, H-free graphs in our case) will only appear in Sections 4.2 and 4.3.

Definition 5 For a function f : N → N, the f -Iterative Expansion MIS problem takes as input a graph G, an integer k, and a set of f (k) vertexdisjoint independent sets S 1 , . . . , S f (k) , each of size k -1. The objective is to find an independent set of size k in G, or to decide that such an independent set does not exist.

Lemma 2 Let G be a hereditary graph class. MIS is FPT in G iff f -Iterative Expansion MIS is FPT in G for some computable function f : N → N. Proof. Clearly if MIS is FPT, then f -Iterative Expansion MIS is FPT
for any computable function f . Conversely, let f be a function for which f -Iterative Expansion MIS is FPT, and let G be a graph with |V (G)| = n.

We show by induction on k that there is an algorithm that either finds an independent set of size k, or answers that such a set does not exist, in FPT time parameterized by k. The initialization can obviously be computed in constant time. Assume we have an algorithm for k -1. Successively for i from 1 to f (k), we construct an independent set S i of size k -1 in G \ (S 1 , . . . , S i-1 ). If, for some i, we are unable to find such an independent set, then it implies that any

independent set of size k in G must intersect S 1 ∪• • •∪S i-1 .
* (f (k) k (k -1) k A f (n, k)),
where the O * (.) suppresses polynomial factors.

We will actually prove a stronger version of this result, by adding more constraints on the input sets S 1 , . . . , S f (k) , and show that solving the expansion version on this particular kind of input is enough to obtain the result for

MIS.

Definition 6 Given a graph G and a set of k -1 vertex-disjoint cliques of G,

C = {C 1 , . . . , C k-1 }
, each of size q, we say that C is a set of Ramsey-extracted cliques of size q if the conditions below hold. Let C r = {c r j : j ∈ {1, . . . , q}} for every r ∈ {1, . . . , k -1}.

-For every j ∈ [q], the set {c r j : r ∈ {1, . . . , k -1}} is an independent set of

G of size k -1.
-For any r = r ∈ {1, . . . , k -1}, one of the four following case can happen:

(i) for every j, j ∈ [q], c r j c r j / ∈ E(G)

(ii) for every j, j ∈ [q], c r j c r j ∈ E(G) iff j = j (iii) for every j, j ∈ [q], c r j c r j ∈ E(G) iff j < j (iv) for every j, j ∈ [q], c r j c r j ∈ E(G) iff j > j

In the case (i) (resp. (ii)), we say that the relation between C r and C r is empty (resp. full6 ). In case (iii) or (iv), we say the relation is semi-full.

Observe, in particular, that a set C of k -1 Ramsey-extracted cliques of size q can be partitioned into q independent sets of size k -1. As we will see later, these cliques will allow us to obtain more structure with the remaining vertices if the graph is H-free. Roughly speaking, if q is large, we will be able to extract from C another set C of k -1 Ramsey-extracted cliques of size q < q, such that every clique is a module 7 with respect to the solution x * 1 , . . . , x * k we are looking for. Then, by guessing the structure of the adjacencies between C

and the solution, we will be able to identify from the remaining vertices k sets X 1 , . . . , X k , where each X i has the same neighborhood as x * i w.r.t. C , and plays the role of "candidates" for this vertex. For a function f : N → N, we define the following problem:

Definition 7 The f -Ramsey-extracted Iterative Expansion MIS problem takes as input an integer k and a graph G whose vertices are partitioned into non-empty sets

X 1 ∪ • • • ∪ X k ∪ C 1 ∪ • • • ∪ C k-1
, where:

-{C 1 , . . . , C k-1 } is a set of k -1 Ramsey-extracted cliques of size f (k) -any independent set of size k in G is contained in X 1 ∪ • • • ∪ X k -∀i ∈ {1, . . . , k}, ∀v, w ∈ X i and ∀j ∈ {1, . . . , k -1}, N (v) ∩ C j = N (w) ∩ C j = ∅ or N (v) ∩ C j = N (w) ∩ C j = C j -the following bipartite graph B is connected: V (B) = B 1 ∪ B 2 , B 1 = {b 1 1 , . . . , b 1 k }, B 2 = {b 2 1 , . . . , b 2 k-1 } and b 1 j b 2 r ∈ E(B) iff X j and C r are adja- cent.
The objective is the following:

if G contains an independent set S such that S ∩ X i = ∅ for all i ∈ {1, . . . , k}, then the algorithm must answer "YES". In that case the solution is called a rainbow independent set.

if G does not contain an independent set of size k, then the algorithm must answer "NO".

Observe that in the case the graph contains an independent set of size k but no rainbow independent set, the algorithm is allowed to answer either yes or no. Eventually, this will imply a one-sided error Monte-Carlo algorithm with constant error probability for MIS. Definition 7 is illustrated by Figure 6.

Lemma 3 Let G be a hereditary graph class. If there exists a computable func-

tion f : N → N such that f -Ramsey-extracted Iterative Expansion MIS is FPT in G, then g-Iterative Expansion MIS is FPT in G, where g(x) = Ram x (f (x)2 x(x-1) ) ∀x ∈ N, with x = 2 (x-1) 2 .
Proof. Let f : N → N be such a function, and let G, k and S = {S 1 , . . . , S g(k) } be an input of g-Iterative Expansion MIS. Recall that the objective is to find an independent set of size k in G, or to decide that α(G) < k. We prove it by induction on k. If G contains an independent set of size k, then either there is one intersecting some set of S, or every independent set of size k avoids the sets in S. In order to capture the first case, we branch on every vertex v of the sets in S, and make a recursive call with parameter

G \ N [v], k -1.
In the remainder of the algorithm, we thus assume that any independent set of size k in G avoids every set of S. 6 The structure of the f -Ramsey-extracted Iterative Expansion MIS inputs.

7 A set of vertices M is a module if every vertex v / ∈ M is adjacent to either all vertices of M , or none. X X 1 X 2 X 3 X 4 X 5 X 6 X 7 C C 1 C 2 C 3 C 4 C 5 C 6 S 3 B Fig.
We choose an arbitrary ordering of the vertices of each S j . Let us denote by s r j the r th vertex of S j . Notice that given an ordered pair of sets of k -1 vertices (A, B), there are k = 2 (k-1) 2 possible sets of edges between these two sets. Let us denote by c 1 , . . . , c 2 (k-1) 2 the possible sets of edges, called types.

We define an auxiliary edge-colored graph H whose vertices are in one-to-one correspondence with S 1 , . . . , S g(k) , and, for i < j, there is an edge between S i and S j of color γ iff the type of (S i , S j ) is γ. By Ramsey's theorem, since H has

Ram k (f (k)2 k(k-1)
) vertices, it must admit a monochromatic clique of size at First, by construction, for every j ∈ {1, . . . , h(k)}, the set {s p j : p = 1, . . . , k-1}

least h(k) = f (k)2 k(k-1
is an independent set. Then, let c be the type of the monochromatic clique of H obtained previously, represented by the adjacencies between two sets (A, B), each of size k -1. For every p ∈ {1, . . . , k -1}, let a p (resp. b p ) be the p th vertex of A (resp. B). Let p, q ∈ {1, . . . , k -1}, p = q. If none of a p b q and a q b p are edges in type c, then there is no edge between C p and C q , and their relation is thus empty. If both edges a p b q and a q b p exist in c, then the relation between C p and C q is full. Finally if exactly one edge among a p b q and a q b p exists in c, then the relation between C p and C q is semi-full. This concludes the fact that C = {C 1 , . . . , C k-1 } are Ramsey-extracted cliques of size h(k).

Suppose that G has an independent set X * = {x * 1 , . . . , x * k }. Recall that we assumed previously that

X * is contained in V (G) \ (C 1 ∪ • • • ∪ C k-1
). The next step of the algorithm consists of branching on every subset of f (k) indices J ⊆ {1, . . . , h(k)}, and restrict every set C p to {s p j : j ∈ J}. For the sake of readability, we keep the notation C p to denote {s p j : j ∈ J} (the nonselected vertices are put back in the set of remaining vertices of the graph,

i.e. we do not delete them). Since h(k) = f (k)2 k(k-1) , there must exist a branch where the chosen indices are such that for every i ∈ {1, . . . , k} and every p ∈ {1, . . . , k -1}, x * i is either adjacent to all vertices of C p or none of them. In the remainder, we may thus assume that such a branch has been made, with respect to the considered solution

X * = {x * 1 , . . . , x * k }. Now, for every v ∈ V (G) \ (C 1 , . . . , C k-1 ), if there exists p ∈ {1, . . . , k -1} such that N (v) ∩ C p = ∅ and N (v) ∩ C p = C p ,

then we can remove this vertex, as

we know that it cannot correspond to any x * i . Thus, we know that all the remaining vertices v are such that for every p ∈ {1, . . . , k -1}, v is either adjacent to all vertices of C p , or none of them.

In the following, we perform a color coding-based step on the remaining vertices. Informally, this color coding will allow us to identify, for every vertex x * i of the optimal solution, a set X i of candidates, with the property that all vertices in X i have the same neighborhood with respect to sets C 1 , . . . , C k-1 . We thus color uniformly at random the remaining vertices V (G) \ (C 1 , . . . , C k-1 ) using k colors. The probability that the elements of X * are colored with pairwise distinct colors is at least e -k .

This random process can be derandomized using the so-called notion of perfect hash families. A (n, k)-perfect hash family is a family of functions F from [n] to [k] (which can be seen as colorings) such that for every set S ∈ [n] k , there exists f ∈ F such that the restriction of f on S is injective.

It is known [START_REF] Naor | Splitters and near-optimal derandomization[END_REF] that a (n, k)-perfect hash family of size e k k O(log k) log n can be constructed in time e k k O(log k) n log n. Hence, instead of coloring V (G) \ (C 1 , . . . , C k-1 ) uniformly at random, we branch on every coloring f ∈ F and run the remainder of the algorithm. The definition of (n, k)-perfect hash family ensures that there is a coloring f such that X * is a rainbow independent set with respect to f . Notice that this derandomization step implies a branching into h(k) log n subcases, for some computable function h. However, the depth of the branching tree (i.e. the maximum number of times this branching will be made in every computation path) is bounded by a function of k only. Since (log n) k ≤ g(k)n for some function g [START_REF] Sloper | An overview of techniques for designing parameterized algorithms[END_REF], the deterministic version of the algorithm is still FPT.

We are thus reduced to the case of finding a rainbow independent set. For every i ∈ {1, . . . , k}, let X i be the vertices of V (G) \ (C 1 , . . . , C k-1 ) colored with color i. We now partition every set X i into at most 2 k-1 subsets X 1 i , . . . ,

X 2 k-1 i
, such that for every j ∈ {1, . . . , 2 k-1 }, all vertices of X j i have the same neighborhood with respect to the sets C 1 , . . . , C k-1 (recall that every vertex of V (G) \ (C 1 , . . . , C k-1 ) is adjacent to all vertices of C p or none, for each p ∈ {1, . . . , k -1}). We branch on every tuple (j 1 , . . . , j k ) ∈ {1, . . . , 2 k-1 }. Clearly the number of branches is bounded by a function of k only and, moreover, one branch (j 1 , . . . , j k ) is such that x * i has the same neighborhood in

C 1 ∪• • •∪C k-1
as vertices of X ji i for every i ∈ {1, . . . , k}. We assume in the following that such a branching has been made. For every i ∈ {1, . . . , k}, we can thus remove vertices of X j i for every j = j i . For the sake of readability, we rename X ji i as X i . Let B be the bipartite graph with vertex bipartition (B 1 , B 2 ),

B 1 = {b 1 1 , . . . , b 1 k }, B 2 = {b 2 1 , . . . , b 2 k-1 }, and b 1 i b 2 p ∈ E(B) iff x * i is adjacent to C p .
Since every x * i has the same neighborhood as X i with respect to C 1 , . . . , C k-1 , this bipartite graph actually corresponds to the one described in Definition 7 representing the adjacencies between X i 's and C p 's. We now prove that it is connected. Suppose it is not. Then, since

|B 1 | = k and |B 2 | = k -1,
there must be a component with as many vertices from B 1 as vertices from B 2 . However, in this case, using the fixed solution X * on one side and an independent set

of size k -1 in C 1 ∪ • • • ∪ C k-1
on the other side, it implies that there is an

independent set of size k intersecting ∪ k-1 p=1 C p , a contradiction.
Hence, all conditions of Definition 7 are now fulfilled. It now remains to find an independent set of size k disjoint from the sets C, and having a nonempty intersection with X i , for every i ∈ {1, . . . , k}. We thus run an algorithm solving f -Ramsey-extracted Iterative Expansion MIS on this input, which concludes the algorithm.

The proof of the following result is immediate, by using successively Lemmas 2 and 3.

Theorem 7 Let G be a hereditary graph class. If f -Ramsey-extracted

Iterative Expansion MIS is FPT in G for some computable function f , then MIS is FPT in G.
We now apply this framework to two families of graphs H.

Clique minus a smaller clique

Theorem 8 For any r 2 and 2 s < r, MIS in (K r \ K s )-free graphs is FPT if s 3, and W [1]-hard otherwise.

Proof. The case s = 2 was already known [START_REF] Dabrowski | Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number[END_REF]. The result for s 4 comes from Theorem 2. We now deal with the case s = 3. We solve the problem in (K r+3 \ K 3 )-free graphs, for every r 2 (the problem is polynomial for r = 1, since it it corresponds exactly to the case of claw-free graphs). Let G, k be an input of the problem. We present an FPT algorithm for f -Ramseyextracted Iterative Expansion MIS with f (x) = r for every x ∈ N. The result for MIS can then be obtained using Theorem 7.

We thus assume that V

(G) = X 1 ∪ • • • ∪ X k ∪ C 1 ∪ • • • ∪ C k-
G \ N [v], k -1.
Hence, for every i ∈ {1, . . . , k}, we may assume that X i contains a clique on r vertices (indeed, if it does not, then it must contain an independent set of size k, in which case we are done). Suppose now that G contains an independent set S * = {x * 1 , . . . , x * k }, with x i ∈ X i for all i ∈ {1, . . . , k}. The first step is to consider the structure of B, using the fact that G is (K r \ K 3 )-free. We have the following:

Claim 9. B is a path, or we can conclude in polynomial time.

Proof of claim: We first prove that for every i ∈ {1, . . . , k}, the degree of X i in B is at most 2. Indeed, assume by contradiction that it is adjacent to C a , C b and C c . Since |X i | Ram(r, k), by Ramsey's theorem, it either contains an independent set of size k, in which case we are done, or a clique K of size r. However, observe in this case that K together with s a 1 , s b 1 and s c 1 (which are pairwise non-adjacent) induces a graph isomorphic to K r+3 \ K 3 .

Then, we show that for every i ∈ {1, . . . , k -1}, the degree of C i in B is at most 2. Assume by contradiction that C i is adjacent to X a , X b and X c . If the instance is positive, then there must be an independent set of size three with non-empty intersection with each of X a , X b and X c . If such an independent set does not exist (which can be checked in cubic time), we can immediately answer NO. Now observe that C i (which is of size r) together with this independent set induces a graph isomorphic to

K r+3 \ K 3 .
To summarize, B is a connected bipartite graph of maximum degree 2 with k vertices in one part, k -1 vertices in the other part. It must be a path.

W.l.o.g., we may assume that for every i ∈ {2, . . . , k -1}, X i is adjacent to C i-1 and C i , and that X 1 (resp. X k ) is adjacent to C 1 (resp. C k-1 ). We now concentrate on the adjacencies between sets X i . We say that an edge

xy ∈ E(G) is a long edge if x ∈ X i , y ∈ X j with |j -i| 2 and 2 i, j k -1, i = j. Claim 10. ∀x ∈ X 2 ∪• • •∪X k-1 , x is incident to at most (k-2)(Ram(r, 3)-1)
long edges.

Proof of claim:

In order to prove it, let us show that for i, j ∈ {2, . . . , k -1} such that |j -i| 2, i = j, and for every x

∈ X i , |N (x) ∩ X j | Ram(r, 3) -1.
Assume by contradiction that there exists x ∈ X i which has at least Ram(r, 3) neighbors Y ⊆ X j . By Ramsey's theorem, either Y contains an independent set of size 3 or a clique of size r. In the first case, C j together with these three vertices induces a graph isomorphic to K r+3 \ K 3 . Hence we may assume that Y contains a clique Y of size r. But in this case, Y together with x, s j-1 1 , s j 1 induce a graph isomorphic to K r+3 \ K 3 as well.

Recall that the objective is to find an independent set of size k with nonempty intersection with X i , for every i ∈ {1, . . . , k}. We assume k 5, otherwise the problem is polynomial. The algorithm starts by branching on every pair of non-adjacent vertices (x 1 , x k ) ∈ X 1 × X k , and removing the union of

their neihborhoods in X 2 ∪ • • • ∪ X k-1 .
For the sake of readability, we still denote by X 2 , . . . , X k-1 these reduced sets. If such a pair does not exist or the removal of their neighborhood empties some X i , then we immediately answer NO (for this branch). Informally speaking, we just guessed the solution within X 1 and X k (the reason for this is that we cannot bound the number of long edges incident to vertices of these sets). We now concentrate on the graph G , which is the graph induced by

X 2 ∪ • • • ∪ X k-1 .
Clearly, it remains to decide whether G admits an independent set of size k -2 with non-empty intersection with X i , for every i ∈ {2, . . . , k -1}.

The previous claim showed that the structure of G is quite particular: roughly speaking, the adjacencies between consecutive X i 's is arbitrary, but the number of long edges is bounded for every vertex. The key observation is that if there were no long edge at all, then a simple dynamic programming algorithm would allow us to conclude. Nevertheless, using the previous claim, we can actually upper bound the number of long edges incident to a vertex of the solution by a function of k only (recall that r is a constant). We can then get rid of these problematic long edges using the so-called technique of The idea of random separation is to delete each vertex of the graph with probability 1 2 . At the end, we say that a removal is successful if both of the two following conditions hold: (i) no vertex of S has been removed, and (ii) all vertices of D have been removed (other vertices but S may have also been removed). Observe that the probability that a removal is successful is at least 3) . In such a case, we can remove all remaining long edges (more formally, we remove their endpoints): indeed, for a remaining long edge xy, we know that there exists a solution avoiding both x and y, hence we can safely delete x and y.

2 -k 2 Ram(r,
Similarly to the color coding step of Lemma 3, this can be derandomized using (n, t)-universal sets: a (n, t)-universal set is a family U of subsets of [n] such that for any S ⊆ [n] of size t, the family {A ∩ S : A ∈ U } contains all 2 t subsets of S. It is known [START_REF] Naor | Splitters and near-optimal derandomization[END_REF] that for any n, t 1, one can construct an (n, t)-universal set of size 2 t t O(log t) log n in time 2 t t O(log t) n log n. Let U be an (n, t)-universal set for t = k + (Ram(r, 3) -1)(k -2) 2 . Instead of deleting vertices of G randomly, branch on every set U ∈ U, and for each branch, delete vertices from U . Then there must be a branch where D ⊆ U and S ⊆ U , hence vertices of D are deleted while those of S are not. As previously, this implies branching into h(k) log n subcases for some computable function of k, but since the depth of the branching tree is a function of k only, the running time of the deterministic version is still FPT.

We still denote by X 2 , . . . , X k-1 the reduced sets, for the sake of readability. We thus end up with a graph composed of sets X 2 , . . . , X k-1 , with edges between X i and X j only if [j -i| = 1. In that case, observe that there is a solution if and only if the following dynamic programming returns true on input P (3, x 2 ) for some x 2 ∈ X 2 :

P (i, x i-1 ) =    true if i = k f alse if X i ⊆ N (x i-1 )
xi∈Xi\N (xi-1) P (i + 1, x i ) otherwise. Informally, this dynamic programming relies on the fact that the only adjacencies between sets X i are between consecutive sets, hence we only need to remember the previous choice when constructing a solution from i = 2 to k -1. Hence, P (i, x i-1 ) represents whether there exists a rainbow solution in

∪ k-1 j=i-1 X j containing x i-1 ∈ X i-1 .
Clearly this dynamic programming runs in O(mnk) time, where m and n are the number of edges and vertices of the remaining graph, respectively. Moreover, it can easily be turned into an algorithm returning a solution of size k -2 if it exists.

Clique minus a complete bipartite graph

For every three positive integers r, s 1 , s 2 with s 1 + s 2 < r, we consider the graph K r \ K s1,s2 . Another way to see K r \ K s1,s2 is as a P 3 of cliques of size s 1 , rs 1 -s 2 , and s 2 . More formally, every graph K r \ K s1,s2 can be obtained from a P 3 by adding s 1 -1 false twins of the first vertex, rs 1 -s 2 -1, for the second, and s 2 -1, for the third.

Theorem 11 For any r 2 and s 1 s 2 with s 1 +s 2 < r, MIS in K r \K s1,s2free graphs is FPT.

Proof. It is more convenient to prove the result for K 3r \ K r,r -free graphs, for any positive integer r. It implies the theorem by choosing this new r to be larger than s 1 , s 2 , and rs 1 -s 2 . We will show that for f (x) := 3r for every

x ∈ N, f -Ramsey-extracted Iterative Expansion MIS in K 3r \K r,r -free graphs is FPT. By Theorem 7, this implies that MIS is FPT in this class. Let C 1 , . . . , C k-1 (whose union is denoted by C) be the Ramsey-extracted cliques of size 3r, which can be partitioned, as in Definition 7, into 3r independent sets S 1 , . . . , S 3r , each of size k -1. Let X = k i=1 X i be the set in which we are looking for an independent set of size k. We recall that between any X i and any C j there are either all the edges or none. Hence, the whole interaction between X and C can be described by the bipartite graph B described in Definition 7.

Firstly, we can assume that each X i is of size at least Ram(r, k), otherwise we can branch on Ram(r, k) choices to find one vertex in an optimum solution (and decrease k by one). By Ramsey's theorem, we can assume that each X i contains a clique of size r (if it contains an independent set of size k, we are done). Our general strategy is to leverage the fact that the input graph is (K 3r \ K r,r )-free to describe the structure of X . Hopefully, this structure will be sufficient to solve our problem in FPT time.

We define an auxiliary graph Y with k-1 vertices. The vertices y 1 , . . . , y k-1

of Y represent the Ramsey-extracted cliques of C and two vertices y i and y j are adjacent iff the relation between C i and C j is not empty (equivalently the relation is full or semi-full). It might seem peculiar that we concentrate the structure of C, when we will eventually discard it from the graph. It is an indirect move: the simple structure of C will imply that the interaction between X and C is simple, which in turn, will severely restrict the subgraph induced by X . More concretely, in the rest of the proof, we will [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF] show that Y is a clique, (2) deduce that B is a complete bipartite graph, (3) conclude that X cannot contain an induced K 2 r = K r K r and run the algorithm of Theorem 6 (which is even stronger than simply solving the colored version of the problem: Theorem 6 returns YES if and only if the instance contains an independent set of size k).

Suppose that there is y i1 y i2 y i3 an induced P 3 in Y , and consider C i1 , C i2 , C i3 the corresponding Ramsey-extracted cliques. For s < t ∈ [3r], let while the relation between C i1 and C i3 is empty. This implies that at least one of the four following sets induces a graph isomorphic to K 3r \ K r,r :

C s→t i := C i ∩ s j t S j
-C 1→r i1 ∪ C r+1→2r i2 ∪ C 1→r i3 -C 1→r i1 ∪ C r+1→2r i2 ∪ C 2r+1→3r i3 -C 2r+1→3r i1 ∪ C r+1→2r i2 ∪ C 1→r i3 -C 2r+1→3r i1 ∪ C r+1→2r i2 ∪ C 2r+1→3r i3
Hence, Y is a disjoint union of cliques (since it is P 3 -free). Let us assume that Y is the union of at least two (maximal) cliques.

Recall that the bipartite graph B is connected. Thus there is b

1 h ∈ B 1 (corresponding to X h ) adjacent to b 2 i ∈ B 2 and b 2 j ∈ B 2 (corresponding to
C i and C j , respectively), such that y i and y j lie in two different connected components of Y (in particular, the relation between C i and C j is empty).

Recall that X h contains a clique of size at least r. This clique induces, together with any r vertices in C i and any r vertices in C j , a graph isomorphic to K 3r \ K r,r ; a contradiction. Hence, Y is a clique. Now, we can show that B is a complete bipartite graph. Each X h has to be adjacent to at least one C i (otherwise this trivially contradicts the connectedness of B). If X h is not linked to C j for some j ∈ {1, . . . , k -1}, then a clique of size r in X h (which always exists) induces, together with

C 1→r i ∪ C 2r+1→3r j or with C 2r+1→3r i ∪ C 1→r j , a graph isomorphic to K 3r \ K r,r .
Since B is a complete bipartite graph, every vertex of C 1 dominates all vertices of X In particular, X is in the intersection of the neighborhood of the vertices of some clique of size r. This implies that the subgraph induced by X Fig. 7 The gem.

is (K r K r )-free. Hence, we can run the FPT algorithm of Theorem 6 on this graph.

The gem

Let the gem be the graph obtained by adding a universal vertex to a path on four vertices (see Figure 7). Using our framework once again, we are able to obtain the following result:

Theorem 12 There is an FPT algorithm for MIS in gem-free graphs.

Proof. Let f (x) := 1 for every x ∈ N. We prove that f -Ramsey-extracted

Iterative Expansion MIS admits an FPT algorithm in gem-free graphs.

By the definition of f , we have C p = {c p } for every p ∈ {1, . . . , k -1}. Recall that the objective is to find a rainbow independent set in G, or to decide that α(G) < k. Since the bipartite graph B representing the adjacencies between {X 1 , . . . , X k } and {c 1 , . . . , c k-1 } is connected, it implies that for every i ∈ {1, . . . , k}, there exists p ∈ {1, . . . , k -1} such that c p dominates all vertices of X i . Since G is gem-free, it implies that G[X i ] is P 4 -free for every i ∈ {1, . . . , k}. Since P 4 -free graphs (a.k.a cographs) are perfect, the size of a maximum independent set equals the size of a clique cover. If G[X i ] contains an independent set of size k (which can be tested in polynomial time), then we are done. Otherwise, we can, still in polynomial time, partition the vertices of X i into at most k -1 sets X 1 i , . . . , X qi i , where G[X j i ] induces a clique for every j ∈ {1, . . . , q i }. We now perform a branching for every tuple (j 1 , . . . , j k ), where j i ∈ {1, . . . , q i } for every i ∈ {1, . . . , k}, which, informally, allows us to guess the clique X ji i which contains the element of the rainbow independent set we are looking for. For the sake of readability, we allow ourselves this slight abuse of notation: we rename X ji i into simply X i . Thus, for every i ∈ {1, . . . , k}, G[X i ] is a clique. Now, let i, j ∈ {1, . . . , k}, i = j. Let us analyse the adjacencies between X i and X j . We say that {a, b, c, d}

⊆ X i ∪ X j is a balanced diamond if a, b ∈ X i (a = b), c, d ∈ X j (c = d
) and all vertices {a, b, c, d} are pairwise adjacent but {b, d}. We have the following claim:

Claim 13. If the graph induced by X i ∪ X j has a balanced diamond, then X i and X j are twins in B.

X 0 i X 1 i X 2 i X 3 i X 4 i X 5 i X 6 i X 6 j X 5 j X 4 j X 3 j X 2 i X 1 j X 0 j
Fig. 8 Schema of the adjacencies between X i and X i when they do not contain a balanced diamond (q = 6). An edge represent a complete relation between the corresponding subsets.

Proof of claim: Suppose they are not. W.l.o.g. we assume that X i is adjacent to {c p } while X j is not, for some p ∈ {1, . . . , k -1}. Then the vertices of the balanced diamond together with c p induce a gem.

The remainder of the proof consists of "cleaning" the adjacencies (X i , X j ) having no balanced diamond (but at least one edge between them). In that case, observe that X i and X j can respectively be partitioned into X 0 i , X 1 i , . . . , X q i and X 0 j , X 1 j , . . . , X q j (where X 0 i and X 0 j are potentially empty) such that X r i ∪ X r j induces a clique for every r ∈ {1, . . . , q}, and there is no edge between X r i and X r j whenever r = r or r = 0 or r = 0 (see Figure 8). In each branch of the next branching rule, the sets {X 1 , . . . , X k } will be modified into {X 1 , . . . , X k }. For the sake of readability, we chose to state the rule as a random one, and then explain how to derandomize it.

Branching rule: Let i, j ∈ {1, . . . , k}, i = j such that X i ∪ X j has no balanced diamond. Then perform the following branching:

-Branch 1:

X i = X 0 i and X z = X z for z ∈ [k] \ {i} -Branch 2: X j = X 0 j and X z = X z for z ∈ [k] \ {j}
-Branch 3: pick a set T ⊆ {1, . . . , q} uniformly at random, then:

-

X i = r∈T X r i -X j = r / ∈T X r j -X z = X z for z ∈ [k] \ {i, j}
Consider the graph G(X 1 , . . . , X k ) having one vertex per set X i , and an edge between X i and X j if these two sets are adjacent. We now prove the following:

Claim 14. The graph G(X 1 , . . . , X k ) has one edge less than G(X 1 , . . . , X k )

Proof of claim: In all three branches, observe that there is no edge between X i and X j .

Claim 15. If G has no independent set of size k, then no graph obtained after the branching contains an independent set of size k.

Proof of claim:

Observe that in all branches,

k z=1 X z ⊆ k z=1 X z , that is,
each graph obtained in each branch is an induced subgraph of G.

Claim 16. If G has a rainbow independent set, then with probability at least 1 2 , at least one branch leads to a graph having a rainbow independent set.

Proof of claim: Suppose that G contains a rainbow independent set S * . If S * intersects X 0 i , then S * also exists in the graph of the first branch. If S * intersects X 0 j , then S * also exists in the graph of the second branch. The last case is where S * intersects X r1 i and X r2 j , for some r 1 , r 2 ∈ {1, . . . q}. In that case, there is a probability of 1 2 that r 1 ∈ T and r 2 / ∈ T , which concludes the proof of the claim

The derandomization of this branching rule uses uses once again (n, t)universal sets. However, this case is simpler since we actually need a (q, 2)universal set, which can be easily constructed as follows. For every i ∈ {1, . . . , log q }, define T i to be the set of all integers r ≤ q whose binary representation contains a one at the i th bit. Then let subcases, but since the depth of the branching tree is a function of k only, the running time of the deterministic version is still FPT.

U = {T i , i = 1... log q }.
We apply the previous branching rule exhaustively, hence we now assume it cannot apply. For the sake of readability, we keep the notation X 1 , . . . , X k in order to denote our instance, even after an eventual application of the previous branching rule. For every X i , X j with i = j, there is either (i) no edge between X i and X j , or (ii) a balanced diamond induced by X i ∪ X j . Hence, Claim 13 implies that each connected component of the graph induced by k i=1 X i is a module with respect to the clique {c 1 , . . . , c k-1 }. In particular, each connected component is dominated by some c p , with p ∈ {1, . . . , k -1}, and is thus P 4free (otherwise, a P 4 together with this vertex c p induce a gem), which means that we can decide in polynomial time whether G contains an independent set of size k, by deciding the problem in every connected component separately (since MIS is polynomial-time solvable in P 4 -free graphs). This concludes the proof, since by Claim 14, the previous branching rule can be applied at most k 2 times.

Polynomial (Turing) kernels

In this section we investigate some special cases of Section 4.3, in particular when H is a clique of size r minus a claw with s branches, for s < r. Although Theorem 11 proves that MIS is FPT for every possible values of r and s, we show that when s r -2, the problem admits a polynomial Turing kernel, while for s 2, it admits a polynomial kernel. Notice that the latter result is somehow tight, as Corollary 4 shows that MIS cannot admit a polynomial kernel in (K r \ K 1,s )-free graphs whenever s 3.

Positive results

The main ingredient of the two following results is a constructive version of the Erdős-Hajnal theorem for the concerned graph classes:

Lemma 4 (Constructive Erdős-Hajnal for K r \ K 1,s ) For every r 2 and s < r, there exists a polynomial-time algorithm which takes as input a connected (K r \ K 1,s )-free graph G, and constructs either a clique or an independent set of size n , which can be found in polynomial time. We may now assume that the maximum degree of G is n r-2 r-1 -1. We construct an independent set v 1 , . . . , v q in G by picking an arbitrary vertex v 1 , removing its neighborhood, and repeating this process until the graph becomes empty.

Using the above argument on the maximum degree, this process can be applied Since a (K r \ K 1,r-1 )-free graph is (K r \ K 1,r -2 )-free for r = r + 1, we have the following:

Corollary 2 For every r 2, MIS in (K r \ K 1,r-1 )-free graphs has a polynomial Turing Kernel.

In other words, (K r \ K 1,r-1 ) is a clique of size r -1 plus an isolated vertex. Observe that the previous corollary can actually be proved in a very simple way: informally, we can "guess" a vertex v of the solution, and return its non-neighborhood together with parameter k -1. Since this non-neighborhood is K r-1 -free, it can be reduced to a O(k r-2 )-sized instance. This is perhaps the most simple example of a problem admitting a polynomial Turing kernel but no polynomial kernel, unless N P ⊆ coN P/poly (as we will prove later in Theorem 19). By considering the complement of graphs, it implies the following even simpler observation: Maximum Clique has a O(k 2 ) Turing kernel on claw -free graphs, but no polynomial kernel, under the same complexitytheoretic assumption.

Theorem 18 For every r 3, MIS in (K r \ K 1,2 )-free graphs has a kernel with O(k r-1 ) vertices.

Proof. For r = 3, the problem is polynomial, so we assume r 4. We first invoke Lemma 4. If the algorithm outputs an independent set of size at least s = n We claim that C ∪ B is a complete |C|-partite graph. To do so, we prove

that for u, v ∈ B, N C (u) = N C (v) implies uv / ∈ E(G), and N C (u) = N C (v) implies uv ∈ E(G). Suppose that N C (u) = N C (v) = C \ {x}. If uv ∈ E(G), then u, v, x together with r -3 vertices of C different from x induce a graph isomorphic to K r \ K 1,2 , which is impossible. Suppose now that N C (u) = C \ {x u }, N C (v) = C \ {x v }, with x u = x v . If uv / ∈ E(G), then u, v, x u together with r -3 vertices of C different from x u and x v induce a graph isomorphic to K r \ K 1,2 , which is impossible. Thus, we now write C ∪ B = S 1 ∪ • • • ∪ S |C| ,
where, for every i, j ∈ {1, . . . , |C|}, i = j, S i induces an independent set, and S i ∪ S j induces a complete bipartite graph. We assume

|S 1 | |S 2 | • • • |S |C| |. Recall that |C| > (k -1)(r -4) + 1.
Using the same arguments as previously, we can

show that every vertex of D is adjacent to at most r -4 different parts among C ∪ B: if a vertex u ∈ D is adjacent to r -3 parts, then taking one vertex in each of these parts together with u and 2 non-neighbors of u in C induces a graph isomorphic to K r \ K 1,2 . Hence, for every u ∈ D, we have Let G denote the reduced instance. We now prove the safeness of this reduction rule. Obviously, if G has an independent set of size k, then G does, since G is an induced subgraph of G. It remains to show that the converse is also true. Let X be an independent set of G of size k.

|{S i : N (u) ∩ S i = ∅}| r -4. Let q = (k -1)(r -
If X ∩ ∪ |C| i=q+1 S i = ∅, then X is also an independent set of size k in G , thus we suppose X ∩ ∪ |C| i=q+1 S i = X r = ∅, which implies that |X ∩ D| ≤ k -1.
In particular, since C ∪ B is a complete multipartite graph, there is a unique i ∈ {1, . . . , |C|} such that X ∩ S i = ∅, and i q + 1. Since every vertex of D is adjacent to at most r -4 parts of C ∪ B, and since q = (k -1)(r -4) + 1, there must exist j ∈ {1, . . . , q} such that N (X ∩ D) ∩ S j = ∅. Moreover, |S j | |S i |. Hence, (X \ S i ) ∪ S j is an independent set of size at least k in G .

Recall that we apply this reduction rule as long as |C| > (k -1)(r -4) + 1.

If it is not the case, then the instance has O(k r-1 ) vertices, since, by Lemma 4, we have |C| n 1 r-1 , and thus n (kr + 5) r-1 , which concludes the proof.

Observe that a (K r \ K 2 )-free graph is (K r+1 \ K 1,2 )-free, hence we have the following, which answers a question of [START_REF] Dabrowski | Parameterized complexity of the weighted independent set problem beyond graphs of bounded clique number[END_REF].

Corollary 3 For every r 1, MIS in (K r \ K 2 )-free graphs has a kernel with O(k r-1 ) vertices.

Kernel lower bounds

We now give a sufficient criteria for a graph H to preclude any polynomial kernel for MIS in H-free graphs. In a nutshell, we characterize graphs which cannot appear in the "straightforward" cross-composition consisting in taking the complete join of several instances.

Definition 8 Given a graph H, a join is a bipartition of V (H) into two nonempty subsets (A, B) such that for every a ∈ A and b ∈ B, ab ∈ E(H).

Theorem 19 Let H be any fixed graph such that (i) MIS is NP-hard in Hfree graphs, and (ii) H has no join. Then MIS does not admit a polynomial kernel in H-free graphs unless NP ⊆ coNP/poly.

Proof. We construct an OR-cross-composition from MIS in H-free graphs. For more details about cross-compositions, see [4]. Let G 1 , . . . , G t be a sequence of H-free graphs, and let G = G 1 + • • • + G t (recall that + is the join operation, that it, there are all possible edges between V (G i ) and V (G j ), i = j). Then we have the following:

α(G ) = max i=1...t α(G i ), since, by construction of G , any independent set cannot intersect the vertex set of two distinct graphs G i and G j .

-G is H-free. Indeed, suppose that X ⊆ V (G ) induces a graph isomorphic to H, and let X j = X ∩ V (G j ) for every j ∈ [t]. Since every G i is H-free, at least two sets X j , X j , j = j are non-empty. But then (X j , ∪ s =j X s ) is a join in H, a contradiction.

These two arguments imply a cross-composition from MIS in H-free graphs to MIS in H-free graphs.

Naturally, the previous lower bound also holds for graphs H containing a graph H as an induced subgraph fulfulling the statement of the theorem (since the class of H -free graphs is included in the class of H-free graphs).

We now use this theorem to show that the polynomial kernel obtained in the previous section for (K r \ K 1,s )-free graphs, s 2, is somehow tight.

Corollary 4 For r 4, and every 3 s r -1, MIS in (K r \ K 1,s )-free graphs does not admit a polynomial kernel unless NP ⊆ coNP/poly.

Proof. Observe that for these values of r and s, (K r \ K 1,s ) always contain as an induced subgraph the graph H defined as the disjoint union of K 1 and K 3 , which does not have a join, while MIS is NP-hard in H-free (since it contains a triangle K 3 ).

It would be interesting to find out whether there exist graphs H not falling into the statement of Theorem 19 for which there is no polynomial kernel. In other words: is Theorem 19 the only way to obtain kernel lower bounds in this case?

Conclusion and open problems

We made some signifiant progress toward the FPT/W [1]-hard dichotomy for MIS in H-free graphs, for a fixed graph H. At the cost of one reduction, we showed that it is W [1]-hard as soon as H is not chordal, even if we simultaneously forbid induced K 1,4 and trees with at least two branching vertices.

Tuning this construction, it is also possible to show that if a connected H is not roughly a "path of cliques" or a "subdivided claw of cliques", then MIS is W [1]-hard. More formally, with the definitions of Section 2.2, the remaining connected open cases are when H has an almost strong clique decomposition on a subdivided claw or a nearly strong clique decomposition on a path. In this language, we showed that for every connected graph H with a strong clique decomposition on a P 3 , there is an FPT algorithm. However, we also proved that for a very simple graph H with a strong clique decomposition on the claw, MIS is W [1]-hard. This suggests that the FPT/W [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hard dichotomy will be somewhat subtle. For instance, easy cases for the parameterized complexity do not coincide with easy cases for the classical complexity where each vertex can be blown into a clique. For graphs H with a clique decomposition on a path, the first unsolved cases are H having:

an almost strong clique decomposition on P 3 ;

a nearly strong clique decomposition on P 3 ;

a strong clique decomposition on P 4 .

For graphs H with a clique decomposition on the claw, an interesting open question is the case of T 1,1,s -free graphs (see notation preceding Theorem 4).

We observe that a randomized FPT algorithm was later found in the T 1,1,2free (or cricket-free) case [5], while W [1]-hardness on T 1,2,2 -free is established in this paper (see Theorem 4)

For disconnected graphs H, we obtained an FPT algorithm when H is a cluster (i.e., a disjoint union of cliques). We conjecture that, more generally, the disjoint union of two easy cases is an easy case; formally, if MIS is FPT in G-free graphs and in H-free graphs, then it is FPT in G H-free graphs.

A natural question regarding our two FPT algorithms of Section 4 concerns the existence of polynomial kernels. In particular, we even do not know whether the problem admits a kernel for very simple cases, such as when

H = K 5 \ K 3 or H = K 5 \ K 2,2 .
A more anecdotal conclusion is the fact that the parameterized complexity of the problem on H-free graphs is now complete for every graph H on four vertices, including concerning the polynomial kernel question (see Figure 9).

Observe that the FPT/W [1]-hard dichotomy was recently settled for all graphs on five vertices [5], using tools from this paper.

  [START_REF] Alekseev | The effect of local constraints on the complexity of determination of the graph independence number[END_REF]-hardness proof for MIS in K 1,4 -free graphs by Hermelin et al.[START_REF] Hermelin | Parameterized complexity of induced graph matching on claw-free graphs[END_REF]. To define this gadget, we first describe an oriented graph with three types of arcs (type T h , T r and T c , which respectively stands for half-graph, row and column, and this naming will become clearer later), and then explain how to represent the vertices and arcs of this graph to get the concrete gadget. Consider first a directed cycle on 4p + 4 vertices c 1 , . . . , c 4p+4 with arcs of type T h . Then consider four oriented paths on p + 1 vertices: P 1 , P 2 , P 3 and P 4 . P 1 and P 3 are composed of arcs of type T c , while P 2 and P 4 are composed of arcs of type T r . Put an arc of type T c between:the last vertex of P 1 and c 1 , -c 2p+3 and the first vertex of P 3 , and an arc of type T r between: -c p+2 and the first vertex of P 2 , -the last vertex of P 4 and c 3p+4 . Now, we replace every vertex of this oriented graph by a clique on n vertices, and fix an arbitrary ordering on the vertices of each clique. The i th vertex in this ordering is said to have index i. For each arc of type T h between c and c , add a half-graph 4 between the corresponding cliques: connect the a th vertex of the clique representing c with the b th vertex of the clique representing c whenever a > b. For every arc of type T r from a vertex c to a vertex c , connect the a th vertex of the clique representing c with the b th vertex of the clique representing c iff s i,j a is not row-compatible with s i,j b . Similarly, for every arc of type T c from a vertex c to a vertex c , connect the a th vertex of the clique representing C with the b th vertex of the clique representing c iff s i,j a is not column-compatible with s i,j b . The cliques corresponding to vertices of this gadget are called the main cliques of T G i,j , and the cliques corresponding to the central cycle on 4p + 4 vertices are called the cycle cliques. The main cliques which are not cycle cliques are called path cliques. The cycle cliques adjacent to one path clique are called branching cliques. We call cycle of cliques the set of all cycle cliques present in the same gadget T G i,j . Two cycle of cliques are said consecutive if they lie on two gadgets T G i,j and T G i,j+1 , or T G i,j and T G i+1,j . A path of cliques is any subgraph induced by the cliques corresponding to vertices forming a directed path in the oriented preliminary graph.

  contains an induced C 4 . Hence the two items can be equivalently replaced by the existence of an almost strong clique decomposition on a subdivision of the claw, and a nearly strong clique decomposition on a path, respectively. Theorem 3 narrows down the connected open cases to graphs H which have a nearly strong clique decomposition on a path or an almost strong clique decomposition on a subdivision of the claw.

  Figure 4, right). We claim that, in this construction, the graph T 1,1,2 , sometimes called cricket, can only appear in the two ways depicted on Figure 5 (up to symmetry). Claim 5. The triangle of the cricket cannot appear within the same main clique. Proof of claim: Otherwise the two leaves (i.e., vertices of degree 1) of the cricket are in two distinct adjacent cliques. But at least one of those adjacent cliques is linked to the main clique of the triangle by an anti-matching. This is a contradiction to the corresponding leaf having two non-neighbors in the main clique of the triangle.

  We thus branch on every vertex v of this union, and, by induction, find an independent set of size k -1 in the graph induced by V (G) \ N [v]. If no step i triggered the previous branching, we end up with f (k) vertex-disjoint independent sets S 1 , . . . , S f (k) , each of size k -1. We now invoke the algorithm for f -Iterative Expansion MIS to conclude. Let us analyze the running time of this algorithm: each step either branches on at most f (k)(k -1) subcases with parameter k -1, or concludes in time A f (n, k), the running time of the algorithm for f -Iterative Expansion MIS. Hence the total running time is O

  random separation[6]. Let S = {x 2 , . . . , x k-1 } be a solution of our problem (with x i ∈ X i for every i ∈ {2, . . . , k -1}). Let us define D = {y : xy is a long edge and x ∈ S}. By the previous claim, we have |D| (Ram(r, 3)-1)(k-2) 2 .

  . In other words, C s→t i contains the elements of C i having indices between s and t. Since |C i | = 3r, each C i can be partitioned into three sets, of r elements each: C 1→r i , C r+1→2r i and C 2r+1→3r i . Recall that the relation between C i1 and C i2 (resp. C i2 and C i3 ) is either full or semi-full,

1 r- 1 , 1 r- 2 = n 1 r- 1 , 2 r- 1 - 1 . 1 r- 1 2 r- 1 1 r- 2 = n 1 r- 1

 11121121111211211 where n is the number of vertices of G.Proof. First consider the case s = r -1, i.e. the forbidden graph is K r-1 plus an isolated vertex. If G contains a vertex v with non-neighborhood N of size at least n r-2 r-1 , then, since G[N ] is K r-1 -free, by Ramsey's theorem, it must contains an independent set of size |N | which can be found in polynomial time. We may now assume that the maximum non-degree 8 of G is n r-We construct a clique v 1 , . . . , v q in G by picking an arbitrary vertex v 1 , removing its non-neighborhood, then picking another vertex v 2 , removing its non-neighborhood, and repeating this process until the graph becomes empty. Using the above argument on the maximum non-degree, this process can be applied n n times, corresponding to the size of the constructed clique. Now, we make an induction on r -1 -s (the base case is above). If G contains a vertex v with neighborhood N of size at least n r-, then, since G[N ] is (K r-1 \ K s )-free, by induction it admits either a clique or an independent set of size |N |

1 r- 1 Theorem 17 1 r- 1 , 1 r- 1 1 r- 1 .

 1117111111 times, corresponding to the size of the constructed independent set. For every r 2, MIS in (K r \ K 1,r-2 )-free graphs has a polynomial Turing kernel.Proof. The problem is polynomial for r = 2 and r = 3, hence we suppose r 4. Suppose we have an algorithm A which, given a graph J and an integer i such that |V (J)| = O(i r-1 ), decides whether J has an independent set of size i in constant time. Having a polynomial algorithm for MIS assuming the existence of A implies a polynomial Turing kernel for the problem[START_REF] Cygan | Parameterized Algorithms[END_REF]. To do so, we will present an algorithm B which, given a connected graph G and an integer k, outputs a polynomial (in |V (G)|) number of instances of size O(k r-1 ), such that one of them is positive iff the former one is. With this algorithm in hand, we obtain the polynomial Turing kernel as follows: let G and k be an instance of MIS. Let V 1 , . . . , V be the connected components of G. For every j ∈ {1, . . . , }, we determine the size of a maximum independent set k j of G[V j ] by first invoking, for successive values i = 1, . . . , k, the algorithmB on input (G[V j ], i),and then A on each reduced instance. At the end of the algorithm, we answer Y ES iff j=1 k i k. We now describe the algorithm B. Let (G, k) be an input, with n = |V (G)|. We first invoke Lemma 4. If the algorithm outputs an independent set of size at least s = n then either k s and we are done (we output a trivially positive instance), or k > n which implies that the instance is a kernel with O(k r-1 ) vertices. Hence, we assume that the algorithm outputs a clique C of size at least n We assume that |C| > r 2 , since otherwise the instance is already reduced. Let B = N (C). First observe that for every u ∈ B, |N C (u)| |C| -(r -3). Indeed, if |N C (u)| |C| -(r -2), then the graph induced by r -2 nonneighbors of u in C together with u and a neighbor of u in C (which exists since|C| > r 2 ) is isomorphic to K r \ K 1,r-2 . Secondly, we claim that V (G) = C ∪ B:for the sake of contradiction, take v ∈ N (B) \ C, and let u ∈ B be such that uv ∈ E(G). By the previous argument, u has at least |C| -r + 3 r -2 neighbors in C which, in addition to u and v, induce a graph isomorphic toK r \ K 1,r-2 .The algorithm outputs, for every u ∈ B, the graph induced by B \ N [u] (with parameter k -1), and, for every u ∈ B and every v ∈ C such that uv / ∈ E(G), the graph induced by B \(N [u]∪N [v]) (with parameter k -2). The correctness of the algorithm follows from the fact that if G has an independent set S of size k > 1, then either: -S ∩ C = ∅, in which case S \ {u} lies entirely in B \ N [u] for any u ∈ S, or -S ∩ C = {v} for some v ∈ C, in which case S \ {u, v} lies entirely in B \ (N [u] ∪ N [v]) for any u ∈ S ∩ B. We now argue that each of these instances has O(k r-3 ) vertices. To do so, observe that for any u ∈ B, B \ N [u] does not contain K r-2 as an induced subgraph: indeed, since |C| > r 2 , then any set of r -1 vertices of B must have a common neighbor in C (since the union of the non-neighborhoods of these r -1 vertices in C is of size at most (r -1)(r -3)). Now, take (for the sake of contradiction) any clique K of size r -2 in B \ N [u], and consider a common neighbor x ∈ C of K ∪ {u}. Then K ∪ {u, x} induces a graph isomorphic to K r \ K 1,r-2 , which is impossible. Since each of these instances is K r-2 -free, applying Ramsey's theorem to each of them allows us to either construct an independent set of size k -1 in one of them (and thus output an independent set of size k in G), or to prove that each of them has at most O(k r-3 ) vertices. At the end, this algorithm outputs O(n 2 ) instances, each having O(k r-3 ) vertices.

1 r- 1 , 1 r- 1 1 r- 1 .

 111111 then either k s and we are done (we output a trivially positive instance), or k > n which implies that the instance is a kernel with O(k r-1 ) vertices. Hence, we assume that the algorithm outputs a clique C of size at least n We assume that this clique is maximal. We present a reduction rule in the case |C| > (k -1)(r -4) + 1. If this rule cannot apply, then it means that the number of vertices of the reduced instance is O(k r-1 ). First observe that for every u ∈ N (C), then either |N C (u)| = |C| -1, or |N C (u)| r -4 (recall that N C (u) = N (u) ∩ C). Indeed, first observe that N C (u) < |C|, since C is maximal. Then, suppose that r -3 |N C (u)| |C| -2. Then u together with r -3 of its neighbors in C and 2 of its nonneighbors in C induce a graph isomorphic to K r \ K 1,2 , a contradiction. Let B = {u ∈ N (C) : |N C (u)| = |C| -1} and D = {u ∈ N (C) : |N C (u)| r -4}.

  4) + 1. The reduction consists of removing S q+1 ∪ • • • ∪ S |C| . Clearly it runs in polynomial time.

Fig. 9

 9 Fig.9Status of the problem for graphs H on four vertices. A green cell represents a positive answer while a red cell represents a negative answer under classical complexity assumptions. P , P K, P T K respectively stand for Polynomial, N P -hard but admits a polynomial kernel, and no polynomial kernel unless N P ⊆ coN P/poly but admits a polynomial Turing kernel.

  W.l.o.g. we may assume that b x ∈ B is the center of the claw, and a α ∈ A, b β ∈ B and c γ ∈ C are the three endpoints. By construction of the gadgets (there is a half-graph between A and B and between B and C), we must have α < x < γ. Now, observe that if x < β then a α must be adjacent to b β , and if β < x, then b β must be adjacent to c γ , but both case are impossible since {a α , b β , c γ } is supposed to be an independent set.

	Similarly, each subgraph induced by P , a path of size 2(p + 1) of cliques
	linking two consecutive cycles of cliques, is claw-free. Hence, for K 1,4 to appear
	in G its center would have to lie in a branching clique. However, in that case,
	a claw must exist either in the cycle of cliques or in P , which we already ruled
	out.
	No C 4 , . . . , C p1 . The main argument is that the graph induced by any
	two main cliques does not contain any of these cycles. Then, we show that
	such a cycle cannot lie entirely in the cycle cliques of a single gadget T G i,j .
	Indeed, if this cycle uses at most one vertex per main clique, then it must
	be of length at least 4p + 4. If it intersects a clique C on two vertices, then
	either it also intersect all the cycle cliques of the gadget, in which case it is of
	length 4p + 5, or it intersects an adjacent clique of C on two vertices, in which
	case these two cliques induce a C 4 , which is impossible. Similarly, such a cycle
	cannot lie entirely in a path between the main cliques of two gadgets. Finally,
	the main cliques of two gadgets are at distance at least 2(p + 1), hence such a
	cycle cannot intersect the main cliques of two gadgets.

  Two cliques C i and C j are said adjacent if H[C i ∪ C j ] is connected. We also write a clique decomposition on T (of H) to denote the choice of an actual partition (C 1 , C 2 , . . . , C ).Let T 1 be the class of trees with at most one branching vertex. Equivalently, T 1 consists of paths and subdivisions of the claw.

	Proposition 1 For a fixed connected graph H, if no tree in T 1 is a clique
	decomposition of H, then MIS in H-free graphs is W [1]-hard.
	Proof. This is immediate from the proof of Theorem 2 since H cannot appear
	in the first construction.
	At this point, we can focus on connected graphs H admitting a tree T ∈ T 1
	as a clique decomposition. The reciprocal of Proposition 1 cannot be true since
	a simple edge is a clique decomposition of C 4 . The next definition further
	restricts the interaction between two adjacent cliques.
	Definition 2 Let T be a graph on vertices t 1 , . . . , t . We say that T is a
	strong clique decomposition of H if there is a partition of V (H) into (C 1 , . . . , C )
	such that:

  1 where all cliques C p have size r. Consider the bipartite graph B representing the adjacencies between {X 1 , . . . , X k } and {C 1 , . . . , C k-1 }, as in Definition 7 (for the sake of readability, we will make no distinction between the vertices of B and the sets {X 1 , . . . , X k } and {C 1 , . . . , C k-1 }). We may first assume that|X i |Ram(r, k) for every i ∈ {1, . . . , k}, since otherwise we can branch on every vertex v of X i and make a recursive call with input

  This family is of size log n and can be constructed in O(n log n) time. The deterministic version of the previous branching rule contains the same first two branches, and replaces the random third one by |U| branches, where, instead of picking T ⊆ {1, . . . , q} at random, we branch on every T ∈ U. Now, Claims 14 and 15 remain the same, while Claim 16 can be replaced by the fact that if G has a rainbow independent set, then at least one branch leads to a graph having a rainbow independent set. Its correctness follows from the fact that by construction of U, for every r 1 , r 2 ∈ {1, . . . , q}, r 1 = r 2 , there exists T ∈ U such that r 1 ∈ T and r 2 / ∈ T . As in Lemma 3, this implies branching into O(log n)

For the sake of simplicity, "MIS" will denote the optimisation, decision and parameterized version of the problem (in the latter case, the parameter is the size of the solution), the correct use being clear from the context.

A branching vertex in a tree is a vertex of degree at least

Notice that the row-compatibility (resp. column-compatibility) relation is not symmetric.

Notice that our definition of half-graph slighly differs from the usual one, in the sense that we do not put edges relying two vertices of the same index. Hence, our construction can actually be seen as the complement of a half-graph (which is consistent with the fact that usually, both parts of a half-graph are independent sets, while they are cliques in our gadgets).

Remark that in this case, the graph induced by Cr ∪ C r is the complement of a perfect matching.

Acknowledgements N. B. and P. C. are supported by the ANR Project DISTANCIA (ANR-17-CE40-0015) operated by the French National Research Agency (ANR).

We would like to thank two anonymous reviewers for their valuable comments which greatly improved the presentation of the paper.