Sylvain Guillemot

Frédéric Havet

Christophe Paul
email: paul@lirmm.fr

Anthony Perez
email: perez@lirmm.fr

On the (non-)existence of polynomial kernels for P l -free edge modification problems

Keywords: parameterized complexity, kernelization algorithms, cograph, modular decomposition

. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P 4 -free graphs (i.e. cographs). This paper provides positive and negative results in that line of research. We prove that Parameterized cograph edge-modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P l -free edge-deletion and the C l -free edge-deletion problems for l ≥ 7 and l ≥ 4 respectively. Indeed, if they exist, then N P ⊆ coN P/poly.

Introduction

An edge modification problem aims at changing the edge set of an input graph G = (V, E) in order to get a certain property Π satisfied (see [START_REF] Natanzon | Complexity classification of some edge modification problems[END_REF] for a recent study). Edge modification problems cover a broad range of graph optimization problems among which completion problems (e.g. minimum fill-in, a.k.a chordal graph completion [START_REF] Rose | A graph-theoretic study of the numerical solution of sparse positive systems of linear equations[END_REF][START_REF] Tarjan | Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs[END_REF]), editing problems (e.g. cluster editing [START_REF] Shamir | Cluster graph modification problems[END_REF]) and edge deletion problems (e.g. maximum planar subgraph [START_REF] Garey | Computers and intractability: a guide to the theory of NPcompleteness[END_REF]). In a completion problem, the set F of modified edges is constrained to be disjoint from E; in an edge deletion problem, F has to be a subset of E; and in an editing problem, no restriction applies to F . These problems are fundamental in graph theory and play an important role in computational complexity theory (indeed they represent a large number of the earliest NP-Complete problems [START_REF] Garey | Computers and intractability: a guide to the theory of NPcompleteness[END_REF]). Edge modification problems are also relevant in the context of applications as graphs are often used to model data sets which may contain errors. Adding or deleting an edge thereby corresponds to fixing some false negatives or false positives (see e.g. [START_REF] Shamir | Cluster graph modification problems[END_REF] in the context of cluster editing). Different variants of edge modification problems have been studied in the literature such as graph sandwich problems [START_REF] Golumbic | Graph sandwich problems[END_REF]. Most of the edge modification problems turn out to be NP-Complete [START_REF] Natanzon | Complexity classification of some edge modification problems[END_REF] and approximation algorithms exist for some known graph properties (see e.g. [START_REF] Kenyon-Mathieu | How to rank with few errors[END_REF][START_REF] Van Zuylen | Deterministic algorithms for rank aggragation and other ranking and clustering problems[END_REF]). But in order to compute an exact solution, fixed parameter algorithms [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Flum | Parameterized complexity theorey[END_REF][START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF] are a good alternative to cope with such hard problems. In the last decades, edge modification problems have been extensively studied in the context of fixed parameterized complexity (see [START_REF] Cai | Fixed-parameter tractability of graph modification problems for hereditary properties[END_REF][START_REF] Fellows | Efficient parameterized preprocessing for cluster editing[END_REF][START_REF] Heggernes | Interval completion with few edges[END_REF]).

A parameterized problem Q is fixed parameter tractable (FPT for short) with respect to parameter k whenever it can be solved in time f (k) • n O (1) , where f (k) is an arbitrary computable function [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF]. In the context of edge modification problems, the size k of the set F of modified edges is a natural parameterization. The generic question is thereby whether a given edge modification problem is FPT for this parameterization. More formally:

Parameterized Π edge-modification Problem: Input: An undirected graph G = (V, E). Parameter: An integer k 0. Question: Is there a subset F ⊆ V × V with |F | k such that the graph H = (V, E △ F ) satisfies Π?

A classical result of parameterized complexity states that a parameterized problem Q is FPT if and only if it admits a kernelization [START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF]. A kernelization of a parameterized problem Q is a polynomial-time algorithm K that given an instance (x, k) computes an equivalent instance K(x, k) = (x ′ , k ′ ) such that the sizes of x ′ and k ′ are bounded by a computable function h() depending only on the parameter k. The reduced instance (x ′ , k ′ ) is called a kernel and we say that Q admits a polynomial kernel if the function h() is a polynomial. The equivalence between the existence of an FPT algorithm and the existence of a kernelization only yields kernels of (at least) exponential size. Determining whether an FPT problem has kernel of polynomial (or even linear) size is thus an important challenge. Indeed, the existence of such polynomial-time reduction algorithm (or pre-processing algorithm or reduction rules) really speed-up the resolution of the problem, especially if it is interleaved with other techniques [START_REF] Niedermeier | A general method to speed up fixed-parametertractable algorithms[END_REF]. However, recent results proved that it is unlikely that every fixed parameter tractable problem admits a polynomial kernel [START_REF] Bodlaender | On problems without polynomial kernels[END_REF].

Cai [START_REF] Cai | Fixed-parameter tractability of graph modification problems for hereditary properties[END_REF] proved that if Π is an hereditary graph property characterized by a finite set of forbidden subgraphs, then the Parameterized Π edgemodification problems (edge-completion, edge-deletion and edge-editing) are FPT. It was then natural to ask [START_REF] Cai | Fixed-parameter tractability of graph modification problems for hereditary properties[END_REF] whether these Π edge-modification problems also admit a polynomial kernel. Using recent lower-bound techniques, Kratsch and Wahlström answered negatively this question [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF]. However, the problem remains open on many natural graph classes characterized by forbidden induced subgraphs. Kratsch and Wahlström asked whether the result holds when the forbidden subgraphs are paths or cycles and pointed out that the problem is already open in the case of P 4 -free graphs (i.e. cographs). In this paper, we prove that Parameterized cograph edge modification problems have cubic vertex kernels whereas polynomial kernels are unlikely to exist for the P l -free edge-deletion and C l -free edge-deletion problems for large enough l. The NP-Completeness of the cograph edge-deletion and edge-completion problems have been proved in [START_REF] El-Mallah | The complexity of some edge deletion problems[END_REF].

Outline of the paper. We begin with some notations and definitions regarding parameterized complexity and modular decomposition. We then establish structural properties of optimal edge-modification sets with respect to modules of the input graph. These properties allow us to design general reduction rules for the Parameterized cograph edge-modification problems (Section 3.1). We then establish cubic kernels for these problems using an extra sunflower rule (Section 3.2 and 3.3). Finally, we show it is unlikely that the C l -free edge-deletion and P l -free edge-deletion problems admit polynomial kernels (Section 4).

Preliminaries

Notations

We only consider finite undirected graphs without loops nor multiple edges. Given a graph G = (V, E), we denote by xy the edge of E between the vertices x and y of V . We set n = |V | and m = |E| (subscripts may be used to avoid possible confusion). The neighbourhood of a vertex x is denoted by N (x). Two subsets of vertices X and Y are adjacent if there exist x ∈ X and y ∈ Y such that x and y are adjacent. If S is a subset of vertices, then G[S] is the subgraph induced by S (i.e. any edge xy ∈ E between vertices x, y ∈ S belongs to E G[S] ). Given a set of pairs of vertices F and a subset S ⊆ V , F [S] denotes the pairs of F with both vertices in S. Given two sets S and S ′ , we denote by S △ S ′ their symmetric difference. Finally, given any integer l, an induced path (resp. cycle) on l vertices is denoted by P l (resp. C l ).

Fixed parameter complexity and kernelization

We let Σ denote a finite alphabet and N the set of natural numbers. A (classical) problem Q is a subset of Σ * , and a string x

∈ Σ * is an input of Q. A parameterized problem Q over Σ is a subset of Σ * × N. The second component of an instance (x, k) of a parameterized problem is called the parameter. Given a parameterized problem Q, one can derive its unparameterized (or classical) version Q by Q = {x#1 k : (x, k) ∈ Q},
where # is a symbol that does not belong to Σ.

A parameterized problem Q is fixed parameter tractable (FPT for short) if there is an algorithm which given an instance (x, k) 1) where f (k) is an arbitrary computable function (see [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Flum | Parameterized complexity theorey[END_REF][START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF]). A kernelization of a parameterized problem Q is a polynomialtime algorithm K which given an instance (x, k)

∈ Σ * × N decides whether (x, k) ∈ Q in time f (k) • n O(
∈ Σ * × N outputs an instance (x ′ , k ′ ) ∈ Σ * × N such that 1. (x, k) ∈ Q if and only if (x ′ , k ′ ) ∈ Q, and 2. |x ′ |, k ′ h(k) for some computable function h : N → N.
The reduced instance (x ′ , k ′ ) is called a kernel and we say that Q admits a polynomial kernel if the function h() is a polynomial. It is well known that a parameterized problem Q is FPT if and only if it has a kernelization [START_REF] Niedermeier | Invitation to fixed parameter algorithms[END_REF]. But this equivalence only yields (at least) exponential size kernels. Recent results proved that it is unlikely that every fixed parameter tractable problem admits a polynomial kernel [START_REF] Bodlaender | On problems without polynomial kernels[END_REF]. These results rely on the notion of (or-)composition algorithms for parameterized problems, which together with a polynomial kernel would imply a collapse in the polynomial hierarchy [START_REF] Bodlaender | On problems without polynomial kernels[END_REF]. An or-composition algorithm for a parameterized problem Q is an algorithm that receives as input a sequence of instances (x 1 , k) . . .

(x t , k) with (x i , k) ∈ Σ * × N for 1 i t, runs in time polynomial in t i=1 |x i | + k and outputs an instance (y, k ′ ) ∈ Σ * × N such that: 1. (y, k ′ ) ∈ Q if and only if (x i , k) ∈ Q for some 1 i t, and 2. k ′ is polynomial in k.
A parameterized problem admitting an or-composition algorithm is said to be or-compositional.

Theorem 1 [START_REF] Bodlaender | On problems without polynomial kernels[END_REF][START_REF] Fortnow | Infeasibility of instance compression and succinct PCPs for NP[END_REF] Let Q be an or-compositional parameterized problem whose unparameterized version Q is NP-complete. The problem Q does not admit a polynomial kernel unless N P ⊆ coN P/poly.

Let P and Q be parameterized problems. A polynomial-time-and-parameter transformation from P to Q is a polynomial-time computable function T which, given an instance (x, k) ∈ Σ * × N, outputs an instance (x ′ , k ′ ) ∈ Σ * × N such that 1. (x, k) ∈ P if and only if (x ′ , k ′ ) ∈ Q, and 2. k ′ p(k) for some polynomial p. Theorem 2 ([3]) Let P and Q be parameterized problems and let P and Q be their unparameterized versions. Suppose that P is NP-complete and Q belongs to NP. If there is a polynomial-time-and-parameter transformation from P to Q and if Q admits a polynomial kernel, then P also admits a polynomial kernel.

Modular decomposition and cographs

A module in a graph G = (V, E) is a set of vertices M ⊆ V such that for any x / ∈ M either M ⊆ N (x) or M ∩ N (x) = ∅. Clearly if M = V or |M | = 1, then
M is a module. We call such a module trivial. A graph without any non-trivial module is called prime. For two disjoint modules M and M ′ , either all the vertices of M are adjacent to all the vertices of M ′ or none of the vertices of M is adjacent to any vertex of M ′ . A partition P = {M 1 , . . . , M p } of the vertex set V (G) whose parts are modules is a modular partition. A quotient graph G /P is associated with any modular partition P: its vertices are the parts of P and there is an edge between M i and M j if and only if M i and M j are adjacent in G.

A module M is strong if for any module M ′ distinct from M , either M ∩ M ′ = ∅ or M ⊂ M ′ or M ′ ⊂ M .
It is clear from definition that the family of strong modules arranges in an inclusion tree, called the modular decomposition tree and denoted M D(G). Each node N of M D(G) thereby represents the set of leaves (vertices of G) for which N is an ancestor. With every node N of M D(G) is associated a quotient graph G N whose vertices correspond to the children N 1 , . . . , N p of N (see Figure 1 for an example): i.e. G N = G[N ] /{N1,...,Np} . We say that a node N of M D(G) is parallel if G N has no edge, series if G N is complete, and prime if G N is prime. A strong property of the family of modules in a graph (used in Lemma 4) is that every module M is either a strong module or there exists a series or a parallel node N such that M is the union of strong modules represented by a subset of the children of N . For a survey on modular decomposition theory, refer to [START_REF] Habib | A survey on algorithmic aspects of modular decomposition[END_REF].

Definition 1 Let G i = (V i , E i ), 1 ≤ i ≤ k be vertex-disjoint graphs. The series composition or join of the G i , 1 ≤ i ≤ k is the graph G 1 ⊕ • • • ⊕ G k = ( i∈I V i , i∈I E i ∪ {v i v j | v i ∈ G i , v j ∈ G j and i = j}). The parallel composition (or disjoint union) of G 1 and G 2 is the graph G 1 + • • • + G k = ( k i=1 V i , k i=1 E i ).
Fig. 1 A graph G and its modular decomposition tree M D(G). The root of M D(G) is prime and its quotient graph is the 5 vertex graph depicted beside. Every other node is either parallel or series.

Parallel and series nodes in the modular decomposition tree respectively correspond to a parallel and series composition of their children.

Cographs are known as P 4 -free graphs, i.e. a cograph does not contain any induced P 4 (see [START_REF] Brandstädt | Graph Classes: A Survey[END_REF][START_REF] Habib | A survey on algorithmic aspects of modular decomposition[END_REF] for example). However, they were originally defined as follows:

Definition 2 ([4]) A graph is a cograph if it can be constructed from single vertex graphs by a sequence of parallel and series composition.

In particular, this means that the modular decomposition tree of a cograph does not contain any prime node. It follows that cographs are also known as the totally decomposable graphs for the modular decomposition.

3 Polynomial kernels for cograph modification problems

Modules in optimal solutions

Since cographs correspond to P 4 -free graphs, cograph edge-modification problems consist in adding or deleting at most k edges to the input graph in order to make it P 4 -free. The use of the modular decomposition tree in our algorithms follows from the following observation. This means that given a modular partition P of a graph G, any induced P 4 of G is either contained in some part of P or intersects the parts of P in at most one vertex. This observation allows us to show that a cograph edgemodification problem can be solved independently on modules of the partition P and on the quotient graph G /P , as stated by the following results.

Observation 2 Let M be a non-trivial module of a graph G = (V, E). Let F M be an optimal edge-deletion (resp. edge-completion, edge-edition) set of G[M ] and let F opt be an optimal edge-deletion (resp. edge-completion, edge-edition) set of G. Then

F = (F opt \ F opt [M ]) ∪ F M
is an optimal edge-deletion (resp. edge-completion, edge-edition) set of G.

Proof By Observation 1, it follows that H = (V, E △ F ) is P 4 -free, thereby F is an edge-deletion set. As being a cograph is an hereditary property,

F opt [M ] is an edge-deletion set of G[M ]. Now observe that |F | = |F opt | since otherwise |F M | > |F opt [M ]
|, which would contradict the optimality of F M . The same argument holds for edge-completion and edge-edition sets.

Lemma 3 Let M be a module of a graph G = (V, E). There exists an optimal edge-deletion (resp. edge-completion, edge-edition) set F such that M is a module of the cograph H = (V, E △ F ).

Proof Let F opt be an optimal edge-deletion set and denote H opt = (V, E △ F opt ). Let x be a vertex of M such that |{xy ∈ F : y / ∈ M }| is minimum. We argue that the following set of edges is an optimal edge-deletion set: We want to prove the existence of an optimal solution F (for the edgedeletion, edge-completion and edge-editing problems) that preserves every module of G: that is every module of G is a module of H = (V, E △ F ). To that aim Lemma 3 is not yet enough. But if we apply it in a bottom-up manner on the strong modules in the modular decomposition tree, we can prove that such an optimal solution does exist.

F = F opt [M ] ∪ F opt [V \ M ] ∪ {zy : z ∈ M, y / ∈ M,
Lemma 4 Let G = (V, E) be an arbitrary graph. There exists an optimal edgedeletion (resp. edge-completion, edge-edition) set F such that every module M of G is a module of the cograph H = (V, E △ F ).

Proof We prove the statement for edge-deletion sets by induction on the number of non-trival strong modules of a graph. The same proof applies for edgecompletion and edge-edition sets. Observe that the result trivially holds if G is a prime graph. Suppose that G has a unique non-trivial strong module M . If M is prime, then the result follows from Lemma 3 as G contains a unique non-trivial module. Assume M is represented by a series or a parallel node. Then the non-trivial modules of G (distinct from M ) are exactly the nontrivial subsets of M (see Subsection 2.3). Moreover as G[M ] is either a clique or an independent set, it is P 4 -free. By Observation 2, there is no need to change the edge set of G[M ]. The result follows.

Let us now assume that the property holds for every graph with at most t non-trivial strong modules. Let G be a graph with t + 1 non-trivial strong modules and let M be a non-trivial strong module of G which is minimal for inclusion. By induction hypothesis, the statement holds on G[M ] (since it is a prime graph or a clique or an independent set) and on the graph G M→x where M has been contracted to a single vertex x (since it contains at most t non-trivial strong modules). The conclusion follows from Observation 2.

As a direct corollary we obtain the existence of an optimal solution that either changes all or none of the edges between two disjoint modules.

Corollary 1 Let G = (V, E) be an arbitrary graph. There exists an optimal edge-deletion (resp. edge-completion, edge-edition) set F such that for every pair M and M ′ of disjoint modules, either

(M ×M ′ ) ⊆ F or (M ×M ′ )∩F = ∅.

Dismantling the modular decomposition tree

We now present three reduction rules which apply to the three cograph edgemodification problems we consider. The second reduction rule is not required to obtain a polynomial kernel for each of these problems. However, it will ease the analysis of the structure of a reduced graph. The idea behind these rules is to simplify the modular decomposition tree of the input graph. The modular decomposition tree of the reduced graph will have depth at most two.

The three following reduction rules preserve the parameter and only modify the graph.

Rule 1 Remove the connected components of G which are cographs.

Rule 2 If C = G 1 ⊕ G 2 is a connected component of G, then replace C by G 1 + G 2 .
Rule 3 If M is a non-trivial module of G which is strictly contained in a connected component and is not an independent set of size at most k + 1, then return the graph G ′ + G[M ] where G ′ is obtained from G by deleting M and adding an independent set of size min{|M |, k + 1} having the same neighbourhood than M .

Observe that if G[M ] is a cograph, adding a disjoint copy to the graph is irrelevant since it will then be removed by Rule 1.

A reduction rule of a parameterized problem Q is said to be safe if for any instance (x, k), the rule applied to it returns an equivalent instance (

x ′ , k ′ ), (that is (x, k) ∈ Q if and only if (x ′ , k ′ ) ∈ Q).
Lemma 5 Rules 1, 2 and 3 are safe and can be carried out in linear time.

Proof The three rules can be computed in linear time using any linear-time modular-decomposition algorithm [START_REF] Habib | A survey on algorithmic aspects of modular decomposition[END_REF]. The first rule is trivially safe. The second rule is safe by Lemma 4. The safeness of Rule 3 follows from Corollary 1: there always exists an optimal solution that edits all or none of the edges between any two disjoint modules. Thereby if a module M has size larger than k + 1, none of the edges (or non-edges) xy with x ∈ M , y / ∈ M can be changed in such a solution. Shrinking M into an independent set of size k + 1 and adding a disjoint copy of G[M ] (to keep track of the edge modifications inside the module) is thereby safe.

The analysis of the size of the kernel relies on the following structural property of the modular decomposition tree of an instance reduced under Rule 1, Rule 2 and Rule 3. Proof By Rule 2, none of the connected components of G results from a series composition. By Rule 3, a module strictly contained in C has size at most k + 1 and is an independent set.

Observe that Rule 3 increases the number of vertices of the instance. Nevertheless, we will be able to bound the number of vertices of a reduced instance.

It remains to show that computing a reduced graph requires polynomial time. Let us mention that it is safe to apply Rule 2 and Rule 3 only on strong modules (in Rule 2, G 1 can be chosen as a strong module). This will optimize the number of rules applications.

Lemma 7 Given a graph G = (V, E), computing a graph reduced under Rule 1, Rule 2 and Rule 3 requires polynomial time.

Proof Let us say that a module M of G is reduced if it is an independent set of size at most k + 1 or the disjoint union of some connected components of G (observe that connected components of G are also modules of G). By Observation 6, if G is reduced under Rule 1, Rule 2 and Rule 3, then every module of G is reduced. Notice that if every strong module of G is reduced, then every module of G is reduced. So to prove the statement, we count the number of strong modules (i.e. nodes of the modular decomposition tree M D(G)) which are not reduced.

Let us also remark that if a connected component C is a cograph with at least two vertices, then a series of applications of Rule 2 eventually transforms C in a set of isolated vertices. This means that we can assume that the applications of Rule 1 is postponed to the end of the reduction process. This will ease the argument below.

When Rule 3 is applied on a strong module, then by definition the number of non-reduced strong modules decreases by one. When Rule 2 is applied (i.e. G = G 1 ⊕ G 2 and G 1 is induced by a strong module), unless G 1 is an independent set of size at most k + 1, then the number of non-reduced strong modules also decreases by one. But observe that if G 1 is an independent set of size at most k + 1, then its vertices will be removed by Rule 1 as they will become isolated vertices. As the number of strong modules of a graph is bounded by the number of vertices, this proves that a series of at most n applications of Rule 2 and Rule 3 is enough to compute a reduced graph.

Cograph edge-deletion (and edge-completion)

In addition to the previous reduction rules, we need the classical sunflower rule to obtain a polynomial kernel for the Parameterized cograph edgedeletion problem.

Rule 4 If e is an edge of G that belongs to a set P of at least k + 1 P 4 's such that e is the only common edge of any two distinct P 4 's of P, then remove e and decrease k by one. (See Figure 2.)

e ′ e Fig. 2 The two distinct cases of a sunflower of 5 edge-disjoint P 4 . Edges e and e ′ have to be removed when k ≤ 4.

Observation 8 Rule 4 is safe and can be carried out in polynomial time.

Proof It is clear that the edge e has to be deleted as otherwise at least k + 1 edge deletions would be required to break all the P 4 's of the set P. Such an edge, if it exists, can be found in polynomial time if one computes the set of all P 4 's of the input graph (which can be done in O(n 4 ) time).

To analyse the size of a reduced graph G = (V, E), we study the structure of the cograph H = (V, E △ F ) resulting from the removal of an optimal (of size at most k) edge-deletion set F . The modular decomposition tree or cotree is the appropriate tool for this analysis. Proof Let G = (V, E) be a graph reduced under Rule 1, Rule 2, Rule 3 and Rule 4 that can be turned into a cograph by deleting at most k edges. Let F be an optimal edge-deletion set and denote by H = (V, E △ F ) the cograph resulting from the deletion of F and by T its cotree. We will count the number of leaves of T (or equivalently of vertices of G and H).

Observe that since a set of k edges covers at most 2k vertices, T contains at most 2k affected leaves (i.e. leaves corresponding to a vertex incident to an edge of F ). We say that an internal node of the cotree T is affected if it is the least common ancestor of two affected leaves. Notice that there are at most 2k affected nodes.

We first argue that the root of T is a parallel node and is affected. Assume that the root of T is a series node: since no edges are added to G, this would imply that G is not reduced under Rule 2, a contradiction. Moreover, since G is reduced under Rule 1, none of its connected components is a cograph. It follows that every connected component of G contains a vertex incident to a removed edge, and thus that every subtree attached to the root contains an affected leaf as a descendant. Hence the root of T is an affected node.

Claim 9 Let p be an affected leaf or an affected node different from the root, and q be the least affected ancestor of p. The path between p and q has length at most 2k + 3.

Proof. Observe first that the result trivially holds if q is the root of T and p one of its children. In all other cases, let M be the set of leaves descendant of p in T . We claim that M contains a leaf x which is incident to a removed edge xy, with y / ∈ M . If p is an affected leaf, then this is true by definition. Otherwise, if p is an affected node different from the root, assume by contradiction that all the removed edges in M are of the form uv with u, v ∈ M . In particular, this implies that M is a module of G strictly contained in a connected component. By Observation 6, it follows that M is an independent set and hence contains no edges, a contradiction. Let t be the least common ancestor of x and y. The node t is a parallel node which is an ancestor of p and q (observe that we may have t = q). Assume by contradiction that the path between x and t in T contains a sequence of 2k + 3 consecutive non-affected nodes. The type of these nodes is alternatively series and parallel. So we can find a sequence s 1 , p 1 . . . s k+1 , p k+1 of consecutive non-affected nodes with s i (resp. p i ) being the father of p i (resp. s i+1 ) and with s i 's being series nodes and the p i 's being parallel node. Now each of the s i 's (resp. p i ) has a non-affected leaf a i (resp. b i ) which is not a descendant of p i (resp. s i+1 ). Observe that for every i ∈ [1, k + 1] the vertex set {b i , a i , x, y} induces a P 4 in G. Thereby we found a set of k + 1 P 4 's in G pairwise intersecting on the edge xy. It follows that G is not reduced by the Rule 4, a contradiction. Since all nodes between p and q are non-affected, it follows that the path between p and q contains at most 2k + 3 nodes. ⋄

Since there are at most 2k affected nodes and 2k affected leaves, T contains at most (4k -1)(2k + 3) + 2k internal nodes. As G is reduced, Observation 6 implies that each of these O(k 2 ) nodes is attached to a set of at most k + 1 leaves or a parallel node with k + 1 children. It follows that T contains at most 2k + (k + 1)[(4k -1)(2k + 3) + 2k] 8k 3 + 20k 2 + 11k leaves, which correspond to the number of vertices of G.

We now conclude with the time complexity needed to compute the kernel. Since the application of Rule 4 decreases the value of the parameter (which is not changed by the other rules), Rule 4 is applied at most k n 2 times. It then follows from Lemma 7 that a reduced instance can be computed in polynomial time.

The following corollary simply follows from the observation that the family of cographs is closed under complementation (since the complement of a P 4 is a P 4 ).

Corollary 2

The Parameterized cograph edge-completion problem admits a cubic vertex kernel.

Cograph edge-editing

The lines of the proof for the cubic kernel of the edge-editing problem are essentially the same as for the edge-deletion problem. But since edges can be added and deleted, the reduction Rule 4 has to be extended to take into account edges whose addition breaks an arbitrary large set of P 4 's.

Rule 5 If {x, y} is a pair of vertices of G that belongs to a set S of t k + 1 quadruples P i = {x, y, a i , b i } such that for every 1 i t, P i induces a P 4 and for any 1 i < j t, P i ∩ P j = {x, y}, then change E into E △ {xy} and decrease k by one.

As for reduction Rule 4, it is clear that reduction Rule 5 is safe and can be applied in polynomial time. The kernelization algorithm of cograph edgeediting consists of an exhaustive application of Rules 1, 2, 3 and 5.

Theorem 4

The Parameterized cograph edge-editing problem admits a cubic vertex kernel.

Proof Let G = (V, E) be a graph reduced under Rule 1, Rule 2, Rule 3 and Rule 5 that can be turned into a cograph by editing at most k edges. Let H be the cograph obtained by an optimal edge-edition. The cotree of H is denoted by T . Unlike in the edge-deletion problem, the root of T is not necessary a parallel node. However it is still true that the root of T is affected. Indeed, assume first that the root of T is a series node. Then it is affected since otherwise G would not be reduced under Rule 2. Now, assume that the root is a non affected parallel node. This means that at most one of its children contains an affected leaf as descendant, and hence that G is not reduced under Rule 1, a contradiction.

In the following we assume w.l.o.g. that the root of T is a parallel node. We prove that Claim 9 still holds in this case. Let p be an affected leaf or an affected node different from the root, and q be the least affected ancestor of p. Observe that the result is trivially true if q is the root of T and p one of its children. In all other cases, let M be the set of leaves descendant of p in T . As in the proof of Theorem 3, there must exist an edited edge xy with x ∈ M, y / ∈ M (otherwise M would be a module of G, i.e. an independent set by Observation 6 and would thus not be edited by Observation 2). Now the proof follows the arguments of the proof of Theorem 3, if one can find in T a path of 2k + 3 consecutive non-affected nodes between p and q, then G is not reduced under Rule 5. Proving that T contains O(k 2 ) nodes and thereby O(k 3 ) leaves.

The fact that a reduced instance can be computed in polynomial time follows from Lemma 7 and the observation that Rule 5 decreases the value of the parameter and requires polynomial time.

For the deletion (resp. editing) problem there exists a graph reduced under Rule 1, Rule 2, Rule 3 and Rule 4 (resp. Rule 5) that achieves the cubic bound (see Figure 3). In [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF], Kratsch and Wahlström show that the Not-1-in-3-sat problem has no polynomial kernel under the complexity-theoretic assumption N P coN P/poly.

We observe that their argument still applies to a graph restriction of Not-1in-3-sat where the constraints arise from the triangles of an input graph. Proof The NP-hardness follows from a reduction from Vertex Cover. Let (G, k) be an instance of Vertex Cover [START_REF] Garey | Computers and intractability: a guide to the theory of NPcompleteness[END_REF], where G = (V, E). We create an instance (G ′ , B, k ′ ) of Not-1-in-3-edge-triangle as follows. The graph G ′ is obtained from G by adding a dominating vertex q, the partial edge-bicoloring B is such that B(e) = 1 for every e ∈ E, and we let k ′ = |E| + k. As the triangles of G are monochromatic, the constraints to obtain a valid extension of B are carried by the triangles of the form quv with uv ∈ E. It is easy to observe that (G ′ , B, k ′ ) has a valid edge-bicoloring extension of weight k ′ if and only if G has a vertex cover of size k. As Not-1-in-3-edge-triangle clearly belongs to NP, the NP-completeness follows.

A graphic version of the

We now show that Not-1-in-3-edge-triangle is or-compositional. The proof closely follows the proof of [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF] for Not-1-in-3-sat. We first need the following result: Claim 10 Given an instance (G, B, k) of Not-1-in-3-edge-triangle, and two positive integers p and k ′ such that k ′ ≥ k + p, we can compute in polynomial time an equivalent instance

(G ′ , B ′ , k ′ ) of Not-1-in-3-edge-triangle such that ω(B ′ ) = ω(B) + p.
Proof. To build G ′ , we first add to G a set F of p new isolated edges e 1 . . . e p such that B ′ (e i ) = 1 for all i ∈ [p]. Then we add to the resulting graph k ′ -(k + p) gadgets one after another as follows: let e = uv be an arbitrary 1-edge of the graph constructed so far; add the triangles uvx, vxy where x and y are new vertices and set B ′ (vy) = B ′ (xy) = 0. (The successive edges e are not necessarily distinct.) Observe that in any valid edge-bicoloring of G ′ extending B ′ , the edge vx is a 0-edge while the edge ux is a 1-edge. It follows that (G, B, k) is a positive instance if and only if (G ′ , B ′ , k ′ ) is a positive instance as the set F increases the weight by p and the added triangles by k ′ -(k + p). ⋄ Consider a sequence (G 1 , B 1 , k), . . . , (G t , B t , k) of instances of Not-1-in-3-edge-triangle. Free to remove the instances such that w(B j ) > k, which are trivially false, we may assume that w(B j ) ≤ k for 1 ≤ j ≤ t. Furthermore, by Claim 10, we can assume w.l.o.g. that w(B j ) = k, for 1 j t.

We can also assume that t 2 k since otherwise an easy exact branching algorithm solves the problem. Finally, for the sake of the construction, we assume t = 2 l (free to duplicate some instances (G i , B i , k) if necessary).

We denote by E 1 (j) the set of 1-edges of (G j , B j , k).

Intuitively, the graph G of the composed instance (G, B, k ′ ) is built on the disjoint union of the G j 's, 1 j t. Then, as a selection gadget, we add a "tree-like graph" T connecting a"root edge" e r to edges e j for j = 1, ..., t. Finally, for every 1 j t, the 1-edges of the graph G j are connected via a propagation gadget to the edge e j in T . The root edge is the unique 1-edge of G. The copies of the G j 's inherit the 0-edges of the G j 's, the other edges are uncolored. The idea is that the selection gadget guarantees that at least one of the e j 's edge gets colored 1. Then the propagation gadgets attached to that edge e j transmit color 1 to the copies of every 1-edge of G j .

Formally, we do the following: (i) we start with a complete binary tree T 0 with root r and t leaves s 1 , . . . , s t ; (ii) to each node u of T 0 , we associate an edge e u in T as follows: if u is associated to the edge xy and if u has two children v, v ′ , we create a new vertex z and we let e v = xz, e v ′ = yz. For convenience, we write e j instead of e sj . Now, for every 1 j t, the propagation gadget S j consists of vertex-disjoint graphs S j,e for every edge e of E 1 (j). If e = uv and e j = xy, then S j,e consists of four triangles uva, vab, abx, bxy, with edges ua, vb, ax, by colored 0 by B (the other edges remain uncolored). Again the unique 1-edge of B is the root edge of T , in particular the edges of E 1 (j) are uncolored by B. However, the 0-edge sets of the G j 's are inherited by B. See Figure 4.

Observe first that every valid edge-bicoloring extending B has to assign color 1 to at least one edge e j , for 1 j t, and to the l edges e v for v vertices of the (r, s j )-path in T 0 . Then the edges of E 1 (j) and the 3k non 0-edges of S j are also assigned color 1. Reciprocally, for every 1 j t, one can extend B in such a way that the only 1-edges are the ones corresponding to the (r, s j )-path in T 0 , the non 0-edges of S j and some in G j . Hence, if we choose k ′ = k + 3k + l, then (G, B, k ′ ) is a positive instance if and only if there exists 1 j t such that (G j , B j , k) is a positive instance.

The following corollary follows from Theorem 1: Corollary 3 The Not-1-in-3-edge-triangle problem does not admit a polynomial kernel unless N P ⊆ coN P/poly. Fig. 4 The instance (G, B, k ′ ) built from a sequence (G 1 , B 1 , k), . . . , (Gt, Bt, k) with t = 2 3 . The unique 1-edge is r. Every "leaf edge" e j of T is linked to the copies of the 1-edges of (G j , B j , k) via the propagation gadget. The 0-edges are depicted as dotted lines: they either belong to a propagation gadget or correspond to a 0-edge of some (G j , B j , k).

The problem Tripartite-Not-1-in-3-edge-triangle is the restriction of Not-1-in-3-edge-triangle where the input graph Let (G, B, k) be an instance of Not-1-in-3-edge-triangle. We build an instance (G ′ , B ′ , 6k) of Tripartite-Not-1-in-3-edge-triangle in the following way. Suppose that G = (V, E), then G ′ has vertex set

G = (V, E) is tripar- tite, i.e. V = V 1 ∪ V 2 ∪ V 3 where V i is an independent set, i = 1, 2,
V ′ = {v 1 , v 2 , v 3 : v ∈ V }, and has edge set E ′ = {u 1 v 2 , u 1 v 3 , u 2 v 3 : u = v or uv ∈ E}. The par- tial edge-bicoloring B ′ is defined as follows: B ′ (u i u j ) = 0 for 1 i < j 3; if the edge uv of G is colored, then B ′ (u i v j ) = B(uv) for 1 i, j 3, i = j; the other edges of G ′ are uncolored.
Observe that every valid edge-bicoloring extending B ′ assigns the same color to the six edges of G ′ associated with an edge uv of G: indeed, given

u i v k , u j v l 1 i, j, k, l 3, if i = j this holds since B ′ (v k v l ) = 0, if k = l
this holds since B ′ (u i u j ) = 0, and otherwise this follows by transitivity. It is then easy to see that solutions of (G, B, k) and solutions of (G ′ , B ′ , 6k) are in one-to-one correspondence.

Negative results for Γ -free edge deletion problems

In this subsection, we prove the following twin theorems.

Theorem 5 For all l 7, C l -free edge-deletion has no polynomial kernel unless N P ⊆ coN P/poly.

Theorem 6 For all l 7, P l -free edge-deletion has no polynomial kernel unless N P ⊆ coN P/poly.

To prove these theorems, we provide polynomial-time-and-parameter transformations from Tripartite-Not-1-in-3-edge-triangle to Vertex annotated C l -free edge-deletion and to Vertex annotated P l -free edgedeletion. For a graph Γ , the Vertex annotated Γ -free edge-deletion problem is defined as follows.

Vertex annotated Γ -free edge-deletion Input: An undirected graph G = (V, E) and a subset S of vertices. Parameter: An integer k ∈ N. Question: Is there a subset

F ⊆ E ∩ (S × S) of size at most k such that H = (V, E \ F ) is Γ -free?
The edges of E ∩ (S × S) are said to be allowed edges. Observe that the Vertex annotated Γ -free edge-deletion problem reduces to the (unannotated) Γ -free edge-deletion problem whenever the class of Γ -free graphs is closed under true (resp. false) twin addition: it suffices to add for every vertex v ∈ V \ S a set of k + 1 true (resp. false) twins. A true twin of v is a vertex u adjacent to v with the same closed neighborhood (N (v) ∪ {v} = N (u) ∪ {u}). A false twin of v is a vertex u non-adjacent to v with the same neighborhood (N (v) = N (u)). Clearly adding a false or true twin preserves the parameter.

Since the family of C l -free graphs is closed under false twin addition (for l 5), Vertex annotated C l -free edge-deletion reduces to C l -free edge-deletion, Theorem 5 is a direct consequence of the following statement.

Lemma 12 For all l 7, Vertex annotated C l -free edge-deletion has no polynomial kernel unless N P ⊆ coN P/poly.

Proof We describe a polynomial-time-and-parameter transformation from Tripartite-Not-1-in-3-edge-triangle to Vertex annotated C l -free edge-deletion. The result then follows Theorem 2 and Lemma 11.

Observe that we can restrict Tripartite-Not-1-in-3-edge-triangle to instances (G, B, k) without 0-edges (i.e. B(e) = 1 whenever it is defined). The reason is that any uncolored edge e = uw of G can be forced to be assigned color 0 in every valid edge-bicoloring extending B by adding to G a set of k + 1 new vertices v 1 , . . . , v k such that uv i w, 1 i k, is an uncolored triangle. Clearly if e is a 1-edge of an edge-bicoloring B ′ extending B, B ′ needs at least k + 1 1-edges to be valid: e plus one edge per triangle. The same argument was used in [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF] for the Not-1-in-3-sat problem.

Let (G, B, k) be an instance of the Tripartite-Not-1-in-3-edge-triangle problem, where V 1 , V 2 , V 3 are disjoint independent sets of G = (V, E). The construction of the instance (H, S, k ′ ) of Annotated C l -free edge-deletion works as follows. First the sets V 1 , V 2 and V 3 are turned into cliques and the 1-edges of G are removed. Then, for each pair t = (uw, v) such that {u, v, w} induces a triangle in G, we create a path P t of length l -3 with endpoints a t and b t and join a t to V -{v, w} and b t to V -{u, v}. Notice that each triangle of G generates three such paths in H. Finally, every two vertices x and y belonging to different P t are made adjacent. We denote by H = (V H , E H ) the resulting graph. See Figure 5. In other words, H is obtained from the disjoint union of G and the join of the P t , by turning V 1 , V 2 , V 3 into cliques and adding edges from a t to V -{v, w} and b t to V -{u, v} for each t = (uw, v) such that {u, v, w} induces a triangle in G.

To complete the description of (H, S, k ′ ) we set S = V and the parameter k ′ = kk 1 where k 1 is the number of 1-edges of (G, B, k).

Fig. 5 The graph H = (V H , E H ) built from an instance (G, B, k) of the Tripartite-Not-1-in-3-edge-triangle problem for l = 12. The white and the square vertices form the set U of new vertices. The independent sets V 1 , V 2 and V 3 of G are turned into cliques. The thick dotted edges are the removed 1-edges of (G, B, k). The non 1-edges of (G, B, k) are preserved in H.

Claim 13 A subset of vertices C ⊆ V H induces a cycle of length l if and only if G contains a triangle uvw, with e = uw a 1-edge and uv, vw uncolored edges, such that C = P t ∪ {u, v, w} with t = (e, v).

Proof. By construction, if G contains a triangle uvw with a unique 1-edge e = uw, then C = P t ∪ {u, v, w} (with t = (e, v)) induces a cycle of length l in H (keep in mind that the 1-edges of G are removed from H). Let C be an induced C l in H. Observe that as V 1 , V 2 and V 3 are turned into cliques, |C ∩ V | 6. Thereby C intersects the vertex set U . We claim that C ∩ U is included in a single path P t . Observe first that C ∩ U cannot intersect three paths P t , P t ′ , P t ′′ , since we would find three vertices inducing a C 3 , impossible. Suppose now that C ∩U intersects exactly two distinct paths P t , P t ′ (t = t ′ ). If C ∩ U contained two vertices in P t and two vertices in P t ′ , these four vertices would induce a C 4 , impossible. If C ∩ U contained three vertices in P t and one vertex in P t ′ , this vertex would have degree at least 3 in C, impossible. Hence, we can assume that |C ∩ P t | ≤ 2 and |C ∩ P t ′ | = 1. The elements of C ∩ P t must be endpoints of P t , as together with the vertex of C ∩ P t ′ they form either a P 2 or a P 3 . But an element of C ∩ P t is nonadjacent to at least l -4 ≥ 3 vertices of C ∩ V , and thus cannot be a t nor b t by definition of the adjacencies of these vertices. This is a contradiction.

Hence there exists a path P t , with t = (e, v) and e = uw, containing the vertices of C ∩ U . We then have the following alternative: either (i) C ∩ P t ⊆ {a t , b t }, or (ii) P t is included in C. In case (i), we have that a t or b t is nonadjacent to at least l -4 ≥ 3 vertices of C ∩ V , contradicting the definition of the adjacencies. Thus, we are in case (ii), and C consists of the vertices of P t , together with three extra vertices x, y, z ∈ V , with x adjacent to a t only, z adjacent to b t only, and y nonadjacent to a t and b t . We have y = v as v is the only vertex of V nonadjacent to a t , b t . We then have x = u as x is nonadjacent to b t , and z = w as z is nonadjacent to a t . Now the existence of P t witnesses the existence of the triangle uvw in G. As uv, wv ∈ E H and uw / ∈ E H , uw is the only 1-edge of the triangle uvw.

⋄

We now argue for the correctness of the transformation. Suppose that there exists a set F of allowed edges of size at most k ′ such that H ′ = (V H , E H \F ) is C l -free. Define the edge-bicoloring B ′ of E as follows: for any edge e ∈ E H ∩ E B ′ (e) = 1 if e ∈ F , B ′ (e) = 0 otherwise. Moreover, since any edge e ∈ E \E H is a 1-edge, we set B ′ (e) = 1 for such edges. As by assumption B does not assign color 0 to any edge, B ′ extends B and has weight at most |F |+k 1 k ′ +k 1 = k. Besides, B ′ is a valid edge-bicoloring of G. Let t = (e, v) with e = uw be a pair such that {u, v, w} induces a triangle in G. If we had B(uw) = 1, B ′ (uv) = B ′ (vw) = 0, we would obtain that P t ∪ {u, v, w} induces a C l in H ′ , impossible. Conversely, suppose that B ′ is valid edge-bicoloring of weight at most k of G which extends B. Let F ⊆ E be the set of edges such that B ′ (e) = 1 but are uncolored by B. By construction F is a set of allowed edges of H of size at most kk 1 . Since B ′ is a valid edge-bicoloring of G, Claim 13 implies that

H ′ = (V H , E H \ F ) is C l -free.
The proof of Theorem 6 is very similar to the one of Theorem 5. Indeed, since the family of P l -free graphs is closed under true twin addition for l 3, it follows the following analog of Lemma 12.

Lemma 14 For all l 7, Vertex annotated P l -free edge-deletion has no polynomial kernel unless N P ⊆ coN P/poly.

Proof Let (G, B, k) be an instance of the Tripartite-Not-1-in-3-edgetriangle problem without 0-edges and such that V 1 , V 2 , V 3 are disjoint independent sets of G = (V, E). We modify the construction given in the proof of Lemma 12 to obtain an instance (H, S, k ′ ) of Vertex annotated P l -free edge-deletion problem. The vertex set V H of H consists of the union of V and a set U of new vertices. The sets V 1 , V 2 and V 3 are again turned into cliques and the 1-edges of E are not duplicated in E H . But for each pair t = (e, v), with e = uw ∈ E and v ∈ V such that {u, v, w} is a triangle of G, the associated gadget Q t is no longer a path. Instead, Q t consists of two paths Q u t and Q w t , whose lengths are at least 2 and sum to l -3 (this is possible since l ≥ 7). As before for every t = t ′ we add all the edges between vertices of Q t and Q t ′ . Let a t be an endpoint of Q u t , and let b t be an endpoint of Q w t , then a t is made adjacent to V -{v, w} and b t is made adjacent to V -{u, v}. To complete the description of (H, S, k ′ ) we set S = V and k ′ = kk 1 where k 1 is the number of 1-edges of (G, B, k).

The correctness proof of the construction follows the same lines as the proof of Lemma 12. It now relies on the following claim that characterizes the possible induced paths of length l.

Claim 15 A subset of vertices Q ⊆ V H induces a path of length l if and only if G contains a triangle uvw, with e = uw a 1-edge and uv, vw uncolored edges, such that Q = Q t ∪ {u, v, w} with t = (e, v).

Proof. By construction, if G contains a triangle uvw with a unique 1-edge e = uw, then Q = Q t ∪ {u, v, w} (with t = (e, v)) induces a path of length l in H (keep in mind that the 1-edges of G are removed from H). Let Q be an induced P l in H. As in the proof of Claim 13, observe that |Q ∩ V | 6 and thereby Q intersects the vertex set U and that there exists a unique pair t = (e, v) with e = uw such that Q t contains Q ∩ U . We then have either (i)

P ∩ Q t ⊆ {a t , b t }, or (ii) |P ∩ Q u t | ≥ 2, or (iii) |P ∩ Q w t | ≥ 2.
In case (i) we have that a t or b t are nonadjacent to at least l -4 ≥ 3 vertices of V , contradicting the definition of the adjacencies. Suppose now that we are in case (ii). Since |P ∩ Q u t | ≥ 2, a t is adjacent to at most one vertex of V in P . As a t is nonadjacent to only two vertices of V , we obtain that |P ∩ V | ≤ 3. We reach the same conclusion in case (iii) by considering b t instead of a t . It follows that |P ∩ Q t | ≥ l -3, and this must be an equality. Hence P consists of the vertices of Q u t , followed by three vertices x, y, z ∈ V , followed by the vertices of Q w t . As in the proof of Claim 13, we obtain that x = u, y = v, z = w. Now, the existence of Q t witnesses the existence of the triangle uvw in G. Moreover the edge uw cannot exist in H, meaning that uw is a 1-edge of (G, B, k).

Improved results for C l -free edge deletion problems

In the previous section, we obtained kernel bounds for the C l -free edge deletion problems for every l ≥ 7. We extend these bounds to 4 ≤ l < 7, by using a different proof technique. We rely on the notion of cross-composition introduced by [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF].

We need the following definitions from [START_REF] Bodlaender | Cross-composition: A new technique for kernelization lower bounds[END_REF]. An equivalence relation R on Σ * is a polynomial equivalence relation if and only if the following two conditions hold:

1. The relation R is decidable in polynomial time. Let P be a classical problem, and let Q be a parameterized problem. A cross-composition from P to Q consists of a polynomial equivalence relation R, and of an algorithm A that receives as input a sequence of strings x 1 , ..., x t belonging to the same equivalence class of R, runs in time polynomial in t i=1 |x i |, and outputs an instance (y, k ′ ) ∈ Σ * × N such that: 1. (y, k ′ ) ∈ Q if and only if x i ∈ P for some 1 ≤ i ≤ t, and 2. k ′ is polynomial in max t i=1 |x i | + log t.

Theorem 7 ([2]) Let P be a classical problem and let Q be a parameterized problem. Suppose that P is N P -hard under Karp reductions and that there is a cross-composition of P into Q. Then Q does not admit a polynomial kernel unless N P ⊆ coN P/poly.

We define Annotated C l -free edge deletion as follows: given a graph G = (V, E), a set F ⊆ E of allowed edges, can we remove at most k allowed edges in G to obtain a C l -free graph? Observe that Vertex annotated C l -free edge deletion is a particular case of Annotated C l -free edge deletion. Hence, for l ≥ 7, both problems have no polynomial unless P ⊆ coN P/poly. We first prove that this annotated version is unlikely to have a polynomial kernel for any l ≥ 4, and we transfer the result to the unannotated version using a polynomial-time-and-parameter transformation.

Lemma 16

The problem Vertex Cover is N P -hard on graphs of girth at least 9.

Proof We give a reduction from Vertex Cover. The reduction consists, starting with a graph G = (V, E), in subdividing each edge with two new degree-2 vertices, yielding a new graph G ′ . More precisely, each edge e = uv is replaced by a a path ux e,u x e,v v, where x e,u ad x e,v are two new vertices. We claim the following: if OP T is the size of a minimum vertex cover of G, and if OP T ′ is the size of a minimum vertex cover of G ′ , then OP T ′ = OP T + |E|. Proposition 2 For all l ≥ 4, Annotated C l -free edge deletion has no polynomial kernel unless N P ⊆ coN P/poly.

Proof We give a cross-composition from Vertex Cover in graphs of girth at least 9, which is N P -hard by Lemma 16. By choosing an appropriate polynomial equivalence relation, we can assume that we are given t instances (G 1 , k), ..., (G t , k) of the problem, where all G i 's have the same number of vertices n. We assume that t = 2 s (free to duplicate some instances if necessary). We let p = ⌊l/2⌋ + 1. We shall construct an instance (G, F, k ′ ) of Annotated C l -free edge deletion, with k ′ = s + 2pn(n -1) + k, and where G, F are constructed as follows. Non-allowed edges will be said as forbidden.

Construction. We first construct the graph T as in Claim 10. We start with a complete binary tree T 0 with root r and t leaves s 1 , . . . , s t ; to each node u of T 0 , we associate an edge e u in T as follows: if u is associated to the edge xy and if u has two children v, v ′ , we create a new vertex z and we let e v = xz, e v ′ = yz. the edges of T are allowed. For all 1 ≤ i ≤ t, we write e i instead of e si , and we denote by R i the path in T from r to s i . Now, for each 1 ≤ i ≤ t, we introduce in G three graphs G ′ i , G ′′ i , P i . Suppose that G i = (V i , E i ). Let r = ⌊l/2⌋ -1 and r ′ = ⌈l/2⌉ -1, so that r + r ′ = l -2. The graph G ′ i is a copy of a r-subdivision of G i , i.e. for each edge uv in G it contains a path p ′ uv of length r + 1 joining u ′ and v ′ . Likewise, the graph G ′′ i is a copy of a r ′ -subdivision of G i , i.e. for each edge uv in G it contains a path p ′′ uv of length r ′ + 1 joining u ′′ and v ′′ . We mark the edges of G ′ i , G ′′ i as forbidden. We add all edges between V ′ i , V ′′ i and we mark these edges as allowed. Let S i be the set of edges u ′ v ′′ (u, v ∈ V i ) with u = v. For each edge e ∈ S i , we add a "propagation gadget" P i,e such that the deletion of e i entails the deletion of e. Suppose that e i = uv and that e = xy. The graph P i,e consists of 2p-2 vertices x 1 , ..., x 2p-2 , and of 2p triangles uvx 1 , vx 1 x 2 , x j x j+1 x j+2 (1 ≤ j ≤ 2p -2), x 2p-1 x 2p x, x 2p xy. We mark the edges vx 1 , x j x j+1 (1 ≤ j ≤ 2p -3), x 2p-2 x as allowed, and the other edges as forbidden. We let P i be the union of the graphs P i,e for e ∈ S i .

To complete the construction, we do the following. First, for every allowed edge e of T ∪ t i=1 P i , we add a path Q e of length l-2 joining the two endpoints of e. We mark the edges of these paths as forbidden. Finally, we remove the edge e r . We let

V ′ = ∪ t i=1 V ′ i , V ′′ = ∪ t i=1
V ′′ i , P denote the union of the graphs P i , and Q denote the union of the graphs Q e .

Correctness. Suppose that (G, F, k ′ ) is a positive instance of Annotated C l -free edge deletion, admitting a solution S. Let v and w be the two children of r in T 0 . In T , the absence of the edge e r implies that Q eu e v e w form a C l in G. Hence one of e v , e w must be in S. By iterating this process, there is i ∈ [t] such that all the s edges associated to vertices in R i are in S. In particular, e i ∈ S. Now, for each edge e in S i , the gadget P i,e implies that the allowed edges of P i,e , as well as e, are in S. Let S ′ be the set of vertices u ∈ V i such that u ′ u ′′ ∈ S. We then have s + 2pn(n -1)

+ |S ′ | ≤ |S| ≤ k ′ , and thus |S ′ | ≤ k ′ -s -2pn(n -1) = k. We claim that S ′ is a vertex cover of G i . Indeed, for each edge uv in G i , since u ′ p ′ uv v ′ v ′′ p ′′ vu u ′′ cannot be a C l in G i \ S it follows that one of u ′ u ′′ , v ′ v ′′
must be in S, and thus one of u, v is in S ′ . We conclude that (G i , k) is a positive instance of Vertex Cover.

Suppose that (G i , k) is a positive instance of Vertex Cover, admitting a solution S. Let S ′ be the set containing contains (i) the edges of T associated to vertices of R i , (ii) the allowed edges of P i,e and the edge e, for each e ∈ S i , (iii) the edge u ′ u ′′ for each u ∈ S. We then have

|S ′ | = s + 2pn(n -1) + |S| ≤ s + 2pn(n -1) + k = k ′ .
The following claim will allow us to conclude that (G, F, k ′ ) is a positive instance of Annotated C l -free edge deletion.

Claim 17 G \ S ′ is C l -free.
Proof. Suppose that C is an induced C l in G \ S ′ . We first consider the case when C intersects Q. Then C contains a path Q e for some e allowed edge of T ∪ P . Since Q e has length l -2, C contains two extra edges e ′ , e ′′ , and the edge e is in S ′ . Assume first that e is an allowed edge of T , then e = e u for some u node of T 0 . We have e ′ = e v , e ′′ e w with either (i) v, w children of u in T 0 , or (ii) u, w children of v in T 0 . In case (i) one of e ′ , e ′′ is in S ′ ; in case (ii) e ′ is in S ′ . This contradicts the assumption that C is an induced cycle. Assume now that e is an allowed edge of P j,f . Then one of e ′ , e ′′ is an allowed edge which is in S ′ by definition, a contradiction.

The second case to consider is when C does not intersect Q, but intersects P . Let us assume that C intersects P j,e with e ∈ S j . Let e j = uv and e = xy. Observe that P j,e \ S ′ consists of either a chain of triangles, or of two vertexdisjoint paths. Therefore, if C intersects P j,e , it follows that C contains a path in P j,e joining {u, v} to {x, y}, and that this path has at least p edges. Since the vertices of P j disconnect T from V ′ j ∪ V ′′ j , C must contain another path in some P j,f , with at least p edges. We conclude that C has at least 2p > l edges, a contradiction.

The third case to consider is when C does not intersect P, Q, but intersects V ′ or V ′′ . As P j separates T from V ′ j ∪ V ′′ j , it follows that C is included in V ′ j ∪ V ′′ j for some j. We cannot have G included in V ′ j , as G ′ j has girth 9r ≥ l. Likewise, we cannot have G included in V ′′ j . If |C ∩ V ′ j | = 1, then C has the form u ′′ p ′′ u,v v ′′ p ′′ v,w w ′′ x ′ , and the edges x ′ u ′′ , x ′ w ′′ imply that j = i and thus the edge x ′ v ′′ is present, contradiction. We reason similarly if |C ∩ V ′′ j | = 1. Suppose now that |C ∩ V ′ j | ≥ 2 and that |C ∩ V ′′ j | ≥ 2. Then C has the form u ′ p ′ u,v v ′ y ′′ p ′′ y,x x ′′ . The absence of the edges u ′ y ′′ , v ′ x ′′ implies that j = i, and the presence of the edges u ′ x ′′ , v ′ y ′′ implies that u = x, v = y. We obtain that uv is in G and that u, v / ∈ S, contradicting the assumption that S is a vertex cover of G.

The last case to consider is when C does not intersect V ′ , V ′′ , P, Q. Then C is included in T . We claim that T \ S ′ is a chordal graph. Indeed, it can be obtained in the following way: when considering a node u with children v, w, such that e u = xy, then (i) if e u = e r and e u / ∈ S ′ then add a new vertex z adjacent to x, y, and let e v = xz, e w = yz, (ii) otherwise, one of e v , e w is in S ′ ; if e v ∈ S ′ then add a new vertex z adjacent to y, and let e w = yz; proceed similarly if e w ∈ S ′ . Since T \ S ′ is a chordal graph, it cannot contain an induced C l with l ≥ 4, contradiction.

We are now in a position to prove the following: Theorem 8 The C l -free edge deletion problem has no polynomial kernel for any l ≥ 4, unless N P ⊆ coN P/poly.

Proof We give a polynomial-time-and-parameter transformation from Annotated C l -free edge deletion. Let (G, F, k) be an instance of Annotated C l -free edge deletion, where G = (V G , E G ). We construct an instance (H, k) of C l -free edge deletion as follows. The graph H = (V H , E H ) is obtained from G by adding, for each edge e = uv in F , a set V e of vertices consisting of : (i) k + 1 vertices x 0,e , ..., x k,e , (ii) k + 1 paths of length l -3 p 0,e , ..., p k,e . Let y i,e , z i,e be the two endpoints of p i,e , then: (i) we make x i,e , y i,e adjacent to u, (ii) we make x i,e , z i,e adjacent to v.

Let us prove the correctness of the transformation. Suppose that there a set S of allowed edges of size at most k such that G ′ = (V G , E G \S) is C l -free. We show that H ′ = (V H , E H \S) is C l -free. Suppose by contradiction that C is an induced C l in H ′ . As C cannot be an induced C l in G ′ , it has to intersect some set V e with e = uv in F . If C contains a vertex x i,e , its neighbors in C are the vertices u, v yielding an induced C 3 , impossible. If C contains a path p i,e , then in C the vertex y i,e is adjacent to u and the vertex z i,e is adjacent to v, which yields an induced C l-1 , impossible. Conversely, suppose that there exists a set S of at most k edges such that H ′ = (V H , E H \S) is C l -free. It suffices to show that S is disjoint from F , as this implies that S ′ = S ∩ E G is a set of allowed edges of size at most k such that G ′ = (V G , E G \S ′ ) is C l -free. Suppose by contradiction that S contains an edge e = uv in F . As |S| ≤ k, we can find an i such that the path ux i,e v is present in H ′ , and we can find a j such that the path up j,e v is present in H ′ . Since uv is not an edge of H ′ , these two paths form a C l in H ′ , contradiction.

Conclusion

In this paper, we provide evidence that the C l -free edge-deletion and the P l -free edge-deletion problems do not admit polynomial kernels for large enough l (unless N P ⊆ coN P/poly [START_REF] Bodlaender | On problems without polynomial kernels[END_REF]). These problems were left open by Kratsch and Wahlström in [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF]. While our result for C t -free edge-deletion is best possible, it remains open whether the P t -free edge-deletion problem admits a polynomial kernel for 4 t < 7.

Moreover, we have shown that the Parameterized cograph edge modification problems admit vertex cubic kernels. It would be interesting to really determine why these results hold. There are few possible reasons: the first is the P 4 -free characterization of cographs, the second is the property of being totally decomposable with respect to the modular decomposition. Because of the negative results for P t -free graphs with t 7, we suspect the forbidden subgraph characterization is not enough. To push further the idea that having a nice tree-decomposition scheme is important, we should investigate whether other decompositions can be used to achieve polynomial kernels for edge-modification problems. An interesting candidate would be the split decomposition [START_REF] Cunningham | A combinatorial decomposition theory[END_REF][START_REF] Ma | An O(n 2 ) algorithm for undirected split decomposition[END_REF] which provides a decomposition similar to the cotree for distance hereditary graphs. Moreover, it is known that distance hereditary graphs do not have a finite set of forbidden induced subgraphs.

To conclude, we mention that cographs are exactly clique-width 2 graphs [START_REF] Courcelle | Handle rewriting hypergraph grammars[END_REF] and that distance hereditary graph are exactly rank-width one graphs [START_REF] Oum | Graphs of bounded rank-width[END_REF]. What about kernelization for edge-modification problems for small value of

Observation 1 (

 1 Folklore) Let M be a module of a graph G = (V, E) and {a, b, c, d} be four vertices inducing a P 4 of G, then |M ∩{a, b, c, d}| 1 or {a, b, c, d} ⊆ M .

Observation 6

 6 Let G be a graph reduced under Rule 1, Rule 2 and Rule 3. If C is a non-prime connected component of G, then the modules of C are independent sets of size at most k + 1.

Theorem 3

 3 The Parameterized cograph edge-deletion problem admits a cubic vertex kernel.

Fig. 3 A 4

 34 Fig.3A reduced graph G with k(k + 1) 2 + k vertices for which k edge deletions, namely the x i y i 's for i ∈[1, k], are required to obtain a cograph H. The cotree T of H is represented. Each parallel node of T which is not the root has k + 2 children, k + 1 of which are leaves. The root of T has 2k children.

Proposition 1

 1 Not-1-in-3-sat problem For a graph G = (V, E), an edge-bicoloring is a function B : E → {0, 1}. A partial edge-bicoloring of G is an edge-bicoloring of a subset of edges of E. An edge colored 1 (resp. 0) is called a 1-edge (resp. 0-edge). We say that the edgebicoloring B ′ extends a partial edge-bicoloring B if B ′ (e) = B(e) for every edge e ∈ E colored by B. The weight of an edge-bicoloring B is the number ω(B) of 1-edges. An edge-bicoloring is valid if every triangle of G contains either zero, two or three 1-edges. We consider the following problem:Not-1-in-3-edge-triangle: Input: An undirected graph G = (V, E) and a partial edge-bicoloring B :E ′ → {0, 1} with E ′ ⊆ E.Parameter: An integer k ∈ N. Question: Can we extend B to a valid edge-bicoloring B ′ of weight at most k? Not-1-in-3-edge-triangle is NP-complete and or-compositional.

  [START_REF] Bodlaender | Kernel bounds for disjoint cycles and disjoint paths[END_REF]. The hardness results obtained for Not-1-in-3-edge-triangle carry over to this restriction:Lemma 11 The Tripartite-Not-1-in-3-edge-triangle problem does not admit a polynomial kernel unless N P ⊆ coN P/poly.Proof The proof uses Theorem 2, that is we provide a polynomial-time-andparameter transformation from Not-1-in-3-edge-triangle to Tripartite-Not-1-in-3-edge-triangle. By Proposition 1, Not-1-in-3-edge-triangle is NP-complete. Observe that Tripartite-Not-1-in-3-edge-triangle clearly belongs to NP.

2 .

 2 For any finite set S ⊆ Σ * , the equivalence relation R partitions the elements of S in at most (max x∈S |x|) O(1) classes.

  Suppose that C is a vertex cover of G. Let C ′ = C ∪ {x e,u : v ∈ C} ∪ {x e,v : v / ∈ C}. Then |C ′ | = |C| + |E|, and C ′ is a vertex cover of G ′ . Conversely, suppose that C is a minimum vertex cover of G ′ . We can assume that for every e = uv in E, the set C contains only one of x e,u , x e,v (for if both are in C, then C \ {x e,v } ∪ {v} is a vertex cover of G ′ of the same size). It follows that for e = uv in E: if x e,u / ∈ C then u ∈ C, and if x e,v / ∈ C then v ∈ C. Thus, the set C ′ = C ∩ V is a vertex cover of G of size |C| -|E|.

  xy ∈ F opt } First observe that by construction M is a module in the graph H = (V, E △ F ) and that by the choice of x, |F | |F opt |. Let us prove that H is P 4 -free. As H[M ] and H[V \ M ] are respectively isomorphic to H opt [M ] and H opt [V \ M ], they are P 4 -free. So if H contains an induced P 4 , its vertex set {a, b, c, d} intersects M and V \ M . As M is a module of H it follows by Observation 1 that |M ∩ {a, b, c, d}| = 1 (say a ∈ M ∩ {a, b, c, d}). It follows by construction of F , that {x,b, c, d} also induces a P 4 in H opt , contradicting the assumption that F opt is an edge-deletion set. So we proved that F is an edge-deletion set of G which preserves the module M and is not larger than F opt . The same proof holds for edge-completion and edge-edition sets.

Acknowledgment. Research supported by the AGAPE project (ANR-09-BLAN-0159).

such classical width-parameters?