Fedor V Fomin

Petr A Golovach
email: petr.golovach@ii.uib.no

Dimitrios M Thilikos

On the Parameterized Complexity of Graph Modification to first-order logic Properties *

Keywords: First-order logic, graph modification, parameterized complexity, descriptive complexity, kernelization

We establish connections between parameterized/kernelization complexity of graph modification problems and expressibility in logic. For a first-order logic formula ϕ, we consider the problem of deciding whether an input graph can be modified by removing/adding at most k vertices/edges such that the resulting modification has the property expressible by ϕ. We provide sufficient and necessary conditions on the structure of the prefix of ϕ specifying when the corresponding graph modification problem is fixed-parameter tractable (parameterized by k) and when it admits a polynomial kernel.

Introduction

A variety of algorithmic graph problems, called modification problems, can be formulated as problems of modifying a graph such that the resulting graph satisfies some fixed desired property. The study of graph modification problems is one of the most popular trends in graph algorithms, and in particular, in parameterized complexity. One of the classic results about graph modification problems is the work of Lewis and Yannakakis [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF], which provides necessary and sufficient conditions (assuming P = NP) of polynomial time solvability of vertex-removal problems for hereditary properties. For other types of graph modification problems, like edge-removal problems [START_REF] Yannakakis | Edge-deletion problems[END_REF], no such dichotomy is known. For the past 30 years graph modification problems served as a strong inspiration for developing new methods and techniques in parameterized/kernelization algorithms and complexity, see the books [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF] for an overview of the area.

In this paper we approach graph modification problems from the perspective of descriptive complexity. Descriptive complexity is the field of logic which studies the relations between computational complexity and expressibility in logic. The classic example of a theorem in descriptive complexity is the theorem of Fagin [START_REF] Fagin | Generalized first-order spectra and polynomial-time recognizable sets[END_REF] asserting that a property with |F | k such that G F |= φ?

For example, for φ = ∀u∀v¬(u ∼ v), Vertex-Removal to φ is equivalent to Vertex Cover that is the graph modification problem asking whether one can remove at most k vertices such that the resulting graph has no edges (we use u ∼ v for the adjacency predicate). More generally, any vertex-removal problem to a graph class characterized by a finite set of forbidden subgraphs, can be expressed as Vertex-Removal to φ for some φ with only ∀ quantifications over variables, where the number of variables is the maximum number of vertices of a forbidden graph. Clearly, using FOL, we are able to express other properties. For example, the property that the diameter of a graph is at most two cannot be expressed using forbidden subgraphs but can easily be written as the

FOL formula ∀u∀v∃w[(u = v) ∨ (u ∼ v) ∨ ((u ∼ w) ∧ (v ∼ w))].
Similarly, the edge variants of modification problems to φ capture quite a few interesting and well-studied problems like Cluster Editing, where the task is to change at most k adjacencies in the graph resulting in a disjoint union of cliques.

We consider modification problems, where the specification of a prefix class of formula φ is defined according to the arithmetic hierarchy (also known as Kleene-Mostowski hierarchy) used for classifications of the formulas in the first-order arithmetic language (see, e.g., [START_REF] Smorynski | The incompleteness theorems[END_REF]). We define prefix classes according to alternations of quantifiers, that is, switchings from ∀ to ∃ or vice versa in the prefix string of the formula. We allow a formula to have free, i.e., non-quantified, variables. Let Σ 0 = Π 0 be the classes of FOL-formulas without quantifiers. For a positive integer s, the class Σ s contains formulas that could be written in the form

φ = ∃x 1 ∃x 2 • • • ∃x t ψ,
where ψ is a Π s-1 -formula, t is some integer, and x 1 , . . . , x t are free variables of ψ. Respectively, Π s consists of formulas

φ = ∀x 1 ∀x 2 • • • ∀x t ψ,
where ψ is a Σ s-1 -formula and x 1 , . . . , x t are free variables of ψ. Note that we allow t = 0, which implies that for s > s, Σ s ∪ Π s ⊆ Σ s ∩ Π s .

We establish a number of algorithmic results about modification problems where the target property is definable in FOL. We complement these results by lower bounds, which in combination provide a neat dichotomy theorems about the parameterized complexity of such problems. Hence we establish sufficient and necessary conditions on the prefix classes of FOL-formulas such that the corresponding graph modification problems are fixed-parameter tractable and/or admit a polynomial kernel.

Our first result shows the following dichotomy (subject to W[2] = FPT) for Vertex-Removal to φ, depending on the structure of the prefix class of φ.

Theorem 1.

(i) For every φ ∈ Σ 3 without free variables, Vertex-Removal to φ is FPT.

(ii) There is φ ∈ Π 3 without free variables such that Vertex-Removal to φ is W[2]- hard.
In other words, if the prefix of an FOL-formula φ has at most two alternations of quantifiers and, in the case of exactly two alternations, if the first quantifier is ∃, then Vertex-Removal to φ is FPT. For each other type of quantifier alternations, there exists a formula for which the problem becomes W[2]-hard.

For kernelization complexity of Vertex-Removal to φ, we establish the following dichotomy.

Theorem 2.

(i) For every φ ∈ Σ 1 ∪ Π 1 without free variables, Vertex-Removal to φ admits a polynomial kernel.

(ii) There is φ ∈ Σ 2 (φ ∈ Π 2 ) without free variables such that Vertex-Removal to φ admits no polynomial kernel unless NP ⊆ coNP/poly.

For edge-modification problems we prove the following.

Theorem 3.

(i) For every φ ∈ Σ 2 without free variables, Edge-Removal to φ, Edge-Completion to φ, and Edge-Editing to φ are FPT.

(ii) There exists φ ∈ Π 2 without free varaibles such that Edge-Removal to φ (respectively, Edge-Completion to φ and Edge-Editing to φ) is W[2]-hard.

We observe that if φ ∈ Σ 1 , then all considered problems can be solved in polynomial time. Clearly, this means that they are FPT and have trivial polynomial kernels. We complement this with lower bounds and summarize these results in the following theorem.

Theorem 4.

(i) For every φ ∈ Σ 1 without free variables, Edge-Removal to φ, Edge-Completion to φ, and Edge-Editing to φ admit polynomial kernels.

(ii) There exists φ ∈ Π 1 without free variables such that Edge-Removal to φ (respectively, Edge-Completion to φ and Edge-Editing to φ) admits no polynomial kernel unless NP ⊆ coNP/poly.

This paper is organized as follows. In Section 2, we introduce basic notions and state some auxiliary results. In Section 3, we obtain the algorithmic upper bounds, that is, we show the claims (i) of Theorems 1-4. In Section 4, we complement these results by the lower bounds given in the claims (ii) of Theorems 1-4. We conclude with Section 5, where we discuss some possible extension of our results and mention some directions for further research.

Preliminaries

Sets. We use N to denote the set of all non-negative numbers. Given some k ∈ N, we denote [k] = [1, k]. Given a set A, we denote by 2 A the set of all its subsets and we define

A 2 := {e | e ∈ 2 A ∧ |e| = 2}.
We denote by a = a 1 , . . . , a r a sequence of elements of a set A and call a an r-tuple of simply a tuple. Note that the elements of a not necessarily pairwise distinct. We denote by ab the concatenation of tuples a and b.

Graphs. All graphs in this paper are undirected, loop-less, and without multiple edges unless it is explicitly specified to be different. Given a graph G, we denote by V (G) its vertex set and by E(G) its edge set. For an edge e = {x, y} ∈ E(G), we use instead the notation e = xy, that is equivalent to e = yx. We denote |G| = |V (G)|. Throughout the paper we use n to denote |G| if it does not create confusion. For a vertex v, d G (v) denotes the degree of v. For any set of vertices S ⊆ V (G), we denote by G[S] the subgraph of G induced by the vertices from S. We also define G -

S := G[V (G) \ S]. Given an edge set F ⊆ E(G), we denote G -F = (V (G), E(G) \ F ). Also, given a set F ⊆ V (G 2 \ E(G), i.e.,
F is a set of pairs of vertices that are not edges of G, we define

G + F = (V (G), E(G) ∪ F ), and for F ⊆ V (G 2 , we define G F = (V (G), E(G) -E(G) ∩ F + F \ E(G)).
Formulas. In this paper we deal with logic formulas on graphs. In particular we will deal with formulas of first-order logic (FOL). The syntax of FOL-formulas on graphs includes the logical connectives ∨, ∧, ¬, variables for vertices, the quantifiers ∀, ∃ that are applied to these variables, the predicate u ∼ v, where u and v are vertex variables and the interpretation is that u and v are adjacent, and the equality of variables representing vertices. . It also convenient to assume that we have the logical connectives → and ↔. An FOL-formula φ is in prenex normal form if it is written as φ

= Q 1 x 1 Q 2 x 2 • • • Q t x t χ
where each Q i ∈ {∀, ∃} is a quantifier, x i is a varible, and χ is a quantifier-free part that depends on the variables x 1 , . . . , x t . Then Q

1 x 1 Q 2 x 2 • • • Q t x t is
referred as the prefix of φ. From now on, when we mention the term "FOL-formula", we mean an FOL-formula on graphs that is in prenex normal form. For an FOL-formula φ without free variables and a graph G, we write G |= φ to denote that φ evaluates to true on G.

For technical reasons, we extend FOL-formulas on graphs to structures of a special type. We say that a pair (G, v), where v = v 1 , . . . , v r is an r-tuple of vertices of G, is an r-structure. Let φ be an FOL-formula without free variables and let x = x 1 , . . . , x r be an r-tuple of pairwise distinct variables of φ. We denote by φ[x] the formula obtained from φ by the deletion of the quantification over x 1 , . . . , x r , that is, these variables become the free variables of φ

[x]. For an r-structure (G, v) with v = v 1 , . . . , v r and φ[x], we write (G, v) |= φ[x] to denote that φ[x] evaluates to true on G if x i is assigned v i for i ∈ [r]. If r = 0, that is, v and x are empty, then (G, v) |= φ[x] is equivalent to G |= φ.
Parameterized Complexity. We refer to the books [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF][START_REF] Flum | Parameterized Complexity Theory[END_REF][START_REF] Niedermeier | Invitation to fixed-parameter algorithms[END_REF] for the detailed introduction to the field. Here we only briefly review the basic notions.

Parameterized Complexity is a bivariate framework for studying the computational complexity of computational problems. One variable is the input size n and the other is a parameter k associated with the input. The main goal is to confine the combinatorial explosion in the running time of an algorithm for an NP-hard problem to depend only on k. Thus, a parameterized problem is defined formally as a language L ⊆ Σ * × N, where Σ * is a set of string over a finite alphabet Σ. A parameterized problem is said to be fixed parameter tractable (or FPT) if it can be solved in time f (k) • n O (1) for some computable function f . Also, we say that a parameterized problem belongs in the class XP if it can be solved in time O(n f (k) ) for some computable function f . The complexity class FPT consists of all fixed parameter tractable problems. Parameterized complexity theory also provides tools to disprove the existence of FPT algorithms under plausible complexity-theoretic assumptions. For this, Downey and Fellows introduced a hierarchy of parameterized complexity classes, namely

FPT ⊆ W[1] ⊆ W[2] ⊆ W[3] ⊆ • • • ⊆ XP
and conjectured that it is proper. This conjecture plays a central role in obtaining lower complexity bounds. The basic way to show that it is unlikely that a parameterized problem admit an FPT algorithm is to show that it is

W[1] or W[2]-hard using a parameterized reduction form a known W[1] or W[2]-hard problem.
A kernelization for a parameterized problem is a polynomial time algorithm that maps each instance (I, k) of a parameterized problem with the input I and parameter k to an instance (I , k ) of the same problem such that (i) (I, k) is a yes-instance if and only if (I , k ) is a yes-instance, and

(ii) |I | + k is bounded by f (k) for some computable function f .
The output (I , k ) is called a kernel. The function f is said to be the size of the kernel. A kernel is polynomial if f is polynomial. While it can be shown that every decidable parameterized problem is FPT if and only if it admits a kernel, it is unlikely that every problem in FPT has a polynomial kernel. In particular, the now standard composition and cross-composition techniques [START_REF] Bodlaender | On problems without polynomial kernels[END_REF][START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF] allow to show that certain problems have no polynomial kernels unless NP ⊆ coNP/poly.

To solve all considered problems, we have to solve the Model Checking problem for first-order logic on graphs:

Model Checking

Input: A graph G and an FOL-formula φ.

Question: Does G |= φ?

Model Checking is known to be PSPACE-complete [START_REF] Vardi | The complexity of relational query languages[END_REF]. The problem is also hard from the parameterized complexity viewpoint when parameterized by the size of the formula. It was proved by Frick and Grohe in [START_REF] Frick | The complexity of first-order and monadic second-order logic revisited[END_REF] that the problem is AW[ * ]-complete for this parametrization (see, e.g., the book [START_REF] Flum | Parameterized Complexity Theory[END_REF] for the definition of the class). Thus, it is unlikely that Model Checking is FPT when parameterized by the formula size. This immediately implies that the problem Vertex-Removal to φ as well as the problems Edge-Removal/Completion/Editing to φ are AW[ * ]-hard when parameterized by the size of φ even for k = 0. However, Model Checking is in XP when parameterized by the number of variables. In particular, if φ has r variables and input size is n, then it can be solved in time O(n r ) by exhaustive search. The currently best algorithm is given by Williams in [START_REF] Williams | Faster decision of first-order graph properties[END_REF] who proved the following.

Theorem 5 ([20]). Model Checking can be solved in time Õ(n ω ) for formulas with 3 variables and if the number of variables r 3, then it can be solved in time Õ(n r-3+ω ) where ω is the matrix-multiplication exponent. Moreover, if r 9, then Model Checking can be solved in time n r-1+o (1) .

Here Õ(f (n)) is used to denote an upper bound O(f (n) log c n) for some positive constant c. These algorithms are, in fact, asymptotically optimal up to the Strong Exponential Time Hypothesis (SETH) (see [START_REF] Cygan | Parameterized Algorithms[END_REF][START_REF] Impagliazzo | Which problems have strongly exponential complexity?[END_REF] for the definition). It was shown by Williams [20] that if Model Checking for formulas with r 4 can be solved in time O(n r-1-ε ) for some ε > 0, then SETH is false.

Because of these results, we assume throughout the paper that the FOL-formulas in the considered modification problems have a constant number of variables and, therefore, constant sizes. In particular, the exponents of polynomials in running times and the sizes of kernels should depend on the length |φ| of the formula φ.

We conclude this section by observing that Theorems 3 and 4 claim the same complexity status for Edge-Removal to φ and Edge-Completion to φ. This is not surprising, because these problems are equivalent in the following sense. Denote by G the complement of a graph G, that is, the graph with the same vertex set such that every two distinct vertices are adjacent in G if and only if they are nonadjacent in G. For an FOL-formula φ, denote by φ the formula obtained from φ by replacing each adjacency predicate by the subformula expressing non-adjacency of distinct vertices, that is, u ∼ v is replaced by

¬(u = v) ∧ ¬(u ∼ v).
Then we can make the following straightforward observation.

Observation 1. For every FOL

-formula φ, (G, k) is a yes-instance of Edge-Removal to φ if and only if (G, k) is a a yes-instance of Edge-Completion to φ.
By Observation 1, it is sufficient to show Theorems 3 and 4 for Edge-Removal to φ and Edge-Editing to φ.

Upper bounds

In this section we prove the claims (i) of Theorems 1-4. First, we consider Vertex-Removal to φ. Lemma 1. For every φ ∈ Σ 3 without free variables, Vertex-Removal to φ can be solved in time

|φ| k • n O(|φ|) . Proof. Consider an instance (G, k) of Vertex-Removal to φ for φ = ∃x 1 • • • ∃x r ∀y 1 • • • ∀y s ∃z 1 • • • ∃z t χ,
where r, s, t 0 and χ is quantifier-free. Let x = x 1 , . . . , x r , y = y 1 , . . . , y s , and

z = z 1 , . . . , z t . Assume that (G, k) is a yes-instance of Vertex-Removal to φ. This means that there is S ⊆ V (G) of size at most k such that G -S |= φ. Observe that G -S |= φ if and only if there is an r-tuple u = u 1 , . . . , u r of vertices of G -S such that (G -S, u) |= φ[x].
We use this observation, and for each r-tuple u of vertices of G, check whether there is S ⊆ V (G) of size at most k that has no common vertices with u and it holds that (G -S, u) |= φ[x]. If we find such a set S, we return this solution for the considered instance of Vertex-Removal to φ. Otherwise, if we fail to find S for all r-tuples u, we conclude that (G, k) is a no-instance. From now we assume that u is given.

Suppose that (G, u) |= φ[x] does not hold. Then there is an s-tuple v = v 1 , . . . , v s of vertices of G such that (G, uv) |= φ[xy] does not hold. Our algorithm is based on the following crucial claim. Claim 1.1 leads to the following recursive algorithm that find a solution S for the given u (if such a solution exist). The algorithm receives as the input the current set S that is initially set to be empty and finds a solution S * ⊇ S as follows. (ii) else, for each v i ∈ v that is not in u, call the algorithm for S = S ∪ {v i }.

1. If (G -S, uv) |= φ[xy] for all s-tuples v = v 1 , . . . , v s of vertices of G -S,
The correctness of the algorithm follows from Claim 1.1. Concerning the running time of the algorithm. At each iteration we check at most n s s-tuples v and for each v we verify in time n O(|φ|) whether (G -S, uv) |= φ [xv]. Hence, each iteration takes time n O(|φ|) . Also at each iteration we branch into at most s subproblems and the depth of the search tree produced by the algorithm is at most k. Thus the running time is s k • n O(|φ|) . Recall that we call the algorithm for each r-tuple u. Since there are n r such tuples, we have that the total running time is s k • n O(|φ|) , which can be rewritten as

|φ| k • n O(|φ|) .
Lemma 1 immediately implies Theorem 1 (i). We move to Edge-Removal to φ and Edge-Editing to φ. Lemma 2. For every φ ∈ Σ 2 without free variables, Edge-Removal to φ and Edge-Editing to φ can be solved in time

|φ| 2k • n O(|φ|) .
Proof. The proof is similar to the proof of Lemma 1. We show the claim for Edge-Removal to φ and then explain how it should be modified for Edge-editing to φ.

Let (G, k) be an instance of Edge-Removal to φ for

φ = ∃x 1 • • • ∃x r ∀y 1 • • • ∀y s χ,
where χ is quantifier-free. Let x = x 1 , . . . , x r and y = y 1 , . . . , y s . We observe that F ⊆ E(G) of size at most k is a solution for an instance (G, k) of Edge-Removal to φ if and only if there is an r-tuple u = u 1 , . . . , u r of vertices of G such that (G -F, u) |= φ[x]. Respectively, for each r-tuple u of vertices of G, we check whether there is

F ⊆ E(G) of size at most k such that (G -F, u) |= φ[x].
If we find such F , we return this solution and we obtain that (G, k) is a no-instance otherwise. Assume that u is given.

If the property (G, u) |= φ[x] is not fulfilled, then there is an s-tuple v = v 1 , . . . , v s of vertices of G such that it does not hold that (G, uv) |= φ [xy]. We use the following claim.

Claim 2.1. For every F ⊆ E(G) such that (G -F, u) |= φ[x], F contains at least one edge with both end-vertices in uv.

To obtain a contradiction, assume that (G -F, u) |= φ[x] but every edge of F has at least one end-vertex outside the tuples u and v. This means that χ evaluates to true on G -F if the x any y-variables are assigned to u and v respectively. Notice that every two vertices of uv are adjacent in G -F if and only if they are adjacent in G. Hence, χ evaluates to true on G if the x any y-variables are assigned to u and v respectively. This means that (G, uv) |= φ[xy]; a contradiction. We construct the following recursive branching algorithm that finds a solution F for the given u if it exists. The algorithm takes as the input the current set F that is initially empty and finds a solution F * ⊇ F : (iii) else, and for each e ∈ L, call the algorithm for F = F ∪ {e}.

1. If (G -F, uv) |= φ[xy] for all s-tuples v = v 1 , . . . , v
The correctness of the algorithm follows from Claim 2.1. On each iteration we check at most n s s-tuples v, and for each v, verify in time n O(|φ|) whether (G -F, uv) |= φ [xv]. Hence, each iteration can be done in time n O(|φ|) . Also on each iteration we have at most |L| r+s 2

branches and the depth of the search tree produced by the algorithm is at most k. This implies that the running time is (r + s) 2k • n O(|φ|) . Recall that we call the algorithm for each r-tuple u. Since there are n r such tuples, we have that the total running time is

|φ| 2k • n O(|φ|) .
For Edge-Editing to φ, the algorithm is essentially the same. The difference is that in addition to edge removal we allowed to add edges. Respectively, we replace G -F by G F in the above algorithm and modify Steps 2 (i)-(iii):

(i) set L be the set of pairs of distinct vertices of uv,

(ii) if |F | = k or L = ∅, then stop;
(iii) else, and for each e ∈ L, call the algorithm for F = F ∪ {e}.

Notice that the variant of Claim 2.1 , where G -F is replaces by G F , holds and this implies correctness. The time analysis is the same.

Lemma 2 together with Observation 1 implies Theorem 3(i). Our next aim is show kernelization upper bounds. First, we observe that for Σ 1 -formulas, our problems can be solved in polynomial time. Lemma 3. For every φ ∈ Σ 1 without free variables, Vertex-Removal to φ, Edge-Removal to φ, and Edge-Editing to φ can be solved in time n O(|φ|) .

Proof. Assume that φ = ∃x 1 • • • ∃x r χ
where χ is quantifier-free.

For Vertex-Removal to φ, it is sufficient to observe that (G, k) is a yes-instance of the problem if and only if G |= φ. We can use Theorem 5 and solve the problem in time n O|φ| .

For Edge-Removal to φ and Edge-Editing to φ, we can observe that (G, k) is a yes-instance if and only if there is a set of vertices U of size s = min{r, n} such that (G[U ], k) is a yes-instance. We can check all such sets U in time n O(|φ|) , and for each set, we use brute force to verify whether (G[U ], k) is a yes-instance. Since the brute force checking of all subsets of edges or pairs of vertices of G[U ] of size at most k = min{k, s 2 } can be done in time s 2k , the total running time is s 2s 2 • n O(|φ|) . Because s |φ|, we can write it as n O(|φ|) .

Because every problem that can be solved in polynomial time has a trivial polynomial kernel, Lemma 3 together with Observation 1 implies Theorem 4(i). Clearly, the lemma also implies the claim of Theorem 2 (i) for Σ 1 -formulas. It remains to prove it for Π 1formulas. For this, we need the classic result of Lewis and Yannakakis [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF]. A graph property P is said to be hereditary if for each graph G satisfying P , it hold that P holds for every induced subgraph of G. A property P is nontrivial if it is true for infinitely many graphs and it is false for infinitely many graphs. Vertex-Removal to P asks, given a graph G and a positive integer k, whether it is possible to remove at most k vertices of G to obtain a graph satisfying P . It was proved by Lewis and Yannakakis [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF] that the following dichotomy holds for a hereditary property P that can be tested in polynomial time: Vertex-Removal to P can be solved in polynomial time if P is trivial, and the problem is NP-complete otherwise. Lemma 4. For every φ ∈ Π 1 without free variables, Vertex-Removal to φ admits a polynomial kernel.

Proof. Let (G, k) be an instance of Vertex-Removal to φ for

φ = ∀x 1 • • • ∀x r χ
where χ is quantifier-free. Let x = x 1 , . . . , x r . Observe that the graph property G |= φ is hereditary for Π 1 -formulas. If this property is trivial, we can solve Vertex-Removal to φ in polynomial time [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF] and conclude that the problem admits a trivial polynomial kernel. Assume from now that the property G |= φ is not trivial. By the result of Lewis and Yannakakis [START_REF] Lewis | The node-deletion problem for hereditary properties is NP-complete[END_REF], Vertex-Removal to φ is NP-complete.

For every tuple v of vertices of G, denote by U v the set of vertices contained in v. Let

U = {U v | v is an r-tuple of vertices of G such that (G, v) |= φ[x]}.
The crucial observation is that S ⊆ V (G) of size at most k is a solution for (G, k) if and only if S is a hitting set for U, that is, S ∩ U v = ∅ for every U v ∈ U. This observation is proved by the same arguments as Claim 1.1 assuming that u is empty.

The s-Hitting Set problem that asks, given a family of sets U of size at most s over some universe and a non-negative integer k, whether there is a hitting set S for U in known to have a polynomial kernel of size at most (2s -1)k s-1 + k by the result of Abu-Khzam [START_REF] Abu-Khzam | A kernelization algorithm for d-hitting set[END_REF]. Apparently Hitting Set is in NP. Hence, there is a polynomial reduction from Hitting Set to the NP-complete problem Vertex-Removal to φ. This implies that Vertex-Removal to φ admits a polynomial kernel.

Lower bounds

Here we prove the hardness claims of Theorems 1-4. In Subsection 4.1, we give the technical result about reducing Edge-Removal to φ to Vertex-Removal to ψ. In Subsection 4.2, we show W[2]-hardness and in Subsection 4.3 we obtain kernelization lower bounds.

Reducing Edge Removal to Vertex Removal

In this section we construct a generic reduction of Edge-Removal to to Vertex-Removal to ψ that we use twice in the proofs of our complexity lower bounds.

We say that an FOL-formula φ is ∀-containing if the prefix of φ contains a ∀ quantifier.

Lemma 5. For every ∀-containing FOL-formula φ ∈ Σ s ∪ Π s without free variables for s 1, there is formula ψ ∈ Σ s+1 ∪ Π s+1 without free variables such that

(i) |ψ| = poly(|φ|), (ii) if φ ∈ Σ s (resp. φ ∈ Π s ), then φ ∈ Σ s+1 (resp. φ ∈ Π s+1 ),
(iii) there is a polynomial reduction of Edge-Removal to φ to Vertex-Removal to ψ that transforms each instance (G, k) of Edge-Removal to φ to an equivalent instance (G , k) of Vertex-Removal to ψ, i.e., the parameter k remains the same.

Proof. Let (G, k) be an instance of Edge-Removal to φ. We construct the instance (G , k) of Vertex-Removal to ψ from (G, k) and then we construct ψ. The main idea is to replace edge removals by vertex removals switching to the incidence graph of G or, equivalently, by subdividing edges of G. Then we have to "label" the vertices of the original graph that should not be removed. We do it by making them adjacent to sufficiently many pendant vertices. Formally, we construct G as follows.

• Construct a copy of G and subdivide each edge, that is, for each e = xy ∈ E(G), delete e, construct a new vertex v e and make it adjacent to x and y. We say that the vertices of G are branching vertices and the vertices obtained by the edge subdivisions are called subdivision vertices.

• For each branching vertex u, introduce k + 3 new vertices v 1 , . . . , v k+3 and make them adjacent to u; we call these vertices pendant.

Notice that every subdivision vertex has degree 2 and every branching vertex has degree at least 3. Moreover, if H is obtained from G by the removal of at most k vertices, then still every remaining branching vertex has degree at least 3. Observe also that H has isolated vertices if and only if at least one branching vertex of G is removed in the construction of H.

Our next aim is to construct ψ from φ to ensure that (G, k) is a yes-instance of Edge-Removal to φ if and only if (G , k) is a yes-instance of Vertex-Removal to ψ. Let

φ = Q 1 x 1 . . . Q p x p χ
where Q 1 , . . . , Q p are quantifiers, x 1 , . . . , x p are variables and χ is quantifier-free. We also assume that χ is written in the conjunctive normal form.

The construction of ψ is done in several steps. First, we take care of adjacencies in φ. Recall that two verices u and v are adjacent in G if and only if they have a common neighbor in G . Respectively, we modify the adjacency predicates in χ.

Let Π = {π 1 , . . . , π s } be the family (multiset) of all predicates of the form x i ∼ x j that occur in χ without negations. If the same predicate x i ∼ x j occurs several times, then for each occurrence, we include it in Π. Similarly, let Π = {π 1 , . . . , πt } be the family (multiset) of all predicates of the form ¬(x i ∼ x j ) that occur in χ. Then we do the following.

• Construct s new variables y 1 , . . . , y s and t variables z 1 , . . . , z t .

• For each h ∈ {1, . . . , s}, consider π h = x i ∼ x j for some i, j ∈ {1, . . . , p} and replace it by ¬(

x i = x j ) ∧ (x i ∼ y h ) ∧ (y h ∼ x j ).
• For each h ∈ {1, . . . , t}, consider πh = ¬(x i ∼ x j ) for some i, j ∈ {1, . . . , p} and replace it by (

x i = x j ) ∨ ¬(x i ∼ y h ) ∨ ¬(y h ∼ x j ).
• Denote the formula obtained from χ by χ . Then

-if Q p = ∃, set σ = ∃y 1 . . . ∃y s ∀z 1 . . . ∀z t χ , and
-if Q p = ∀, set σ = ∀z 1 . . . ∀z t ∃y 1 . . . ∃y s χ .
Consider the formula α = Q 1 x 1 . . . Q p x p σ. Observe that we added new quantified variables in the end of the prefix of φ in such a way that we obtain at most one additional alternation of quantifiers. That is, we obtain that α ∈ Σ s+1 if φ ∈ Σ s and α ∈ Π s+1 if φ ∈ Π s . The crucial property of the above construction is given in the following straightforward claim.

Claim 5.1. G |= φ if and only if G |= β where

β = Q 1 x 1 . . . Q p x p σ
with the domains of the variables x 1 , . . . , x p restricted to V (G).

Moreover, for every set of pendant vertices X of size at most k, G |= φ if and only if

(G -X) |= β.
Notice that in the formula of Claim 5.1 we insist to restrict the domains of the variables x 1 , . . . , x p in β to V (G), that is, β is not an FOL-formula (and β = α). Our next aim is to express these additional constraints in the first-order logic. We do it using the property that the branching vertices of G have degrees at least 3 and all the other vertices have degrees at most 2.

We consecutively construct the formulas ρ n+1 , . . . , ρ 1 . First, we set ρ n+1 = σ. Note that x 1 , . . . , x p are free variable for ρ n+1 . Assume inductively that 1 i p and ρ i+1 with free variables x 1 , . . . , x i is already constructed. Denote by P i+1 the prefix and µ i+1 the quantifier-free part of ρ i+1 respectively, that is, ρ i+1 = P i+1 µ i+1 . The construction of ρ i depends on the quantifier Q i . Recall that the removal of the edges in G corresponds to the removal of subdivision vertices of G . Respectively, our next aim is to ensure that the removal of a branching vertex of G leads to the graph for which our formula is false. We use the property that for every set S of at most k vertices of G , G -S has an isolated vertex if and only if S contains a branching vertex. We use the property that the condition that a graph has no an isolated can be expressed by the formula ∀s 1 ∃s 2 (s 1 ∼ s 2 ) and modify γ as follows. Let P be the prefix of γ and let µ be the quantifier-free part. We write P as the concatenation of 3 parts P 1 , P 2 and P 3 where P 1 and/or P 3 may be empty. Recall that the prefix of the original formula φ contains the ∀x i for some i ∈ {1, . . . , p} by the condition of the lemma. Hence, the same holds for γ. Let P 1 be the first part of P until the first occurrence of the quantifier ∀. Then P 2 is the next part until the first occurrence of the quantifier ∃ or until the end of P if such a quantifier does not exist. Respectively, P 3 is the remaining part. We define ψ = P 1 ∀s 1 P 2 ∃s 2 P 3 [(s 1 ∼ s 2 ) ∧ µ] using two new variables s 1 and s 2 .

• Introduce 3 new variables r 1 i , r 2 i , r 3 i . • If Q i = ∃, then set ρ i = ∃x i ∃r 1 i ∃r 2 i ∃r 3 i P i+1 [(¬(r 1 i = r 2 i ) ∧ ¬(r 1 i = r 3 i ) ∧ ¬(r 2 i = r 3 i ))∧ ((x i ∼ r 1 i ) ∧ (x i ∼ r 2 i ) ∧ (x i ∼ r 3 i )) ∧ µ i+1 ]. • If Q i = ∀, then set ρ i = ∀x i ∀r 1 i ∀r 2 i ∀r 3 i P i+1 [((¬(r 1 i = r 2 i ) ∧ ¬(r 1 i = r 3 i ) ∧ ¬(r 2 i = r 3 i ))∧ ((x i ∼ r 1 i ) ∧ (x i ∼ r 2 i ) ∧ (x i ∼ r 3 i )) → µ i+1 ]. Let γ = ρ 1 . Note
Notice that the insertion of the new quantifications is done in such a way that we do not introduce new alternations of quantifiers unless P 3 is empty. But if P 3 is empty, then φ ∈ Π 1 or φ ∈ Σ 2 and the new alternations were not introduced in the construction of α from φ. We have that either φ, γ ∈ Σ s and ψ ∈ Σ s+1 or φ, γ ∈ Π s and ψ ∈ Π s+1 .

We show the following claim. Suppose now that (G , k) is a yes-instance of Vertex-Removal to ψ. Then there is S ⊆ V (G ) of size at most k such that (G -S) |= ψ. Since ψ = P 1 ∀s 1 P 2 ∃s 2 P 3 [(s 1 ∼ s 2 )∧µ], we have that G -S has no isolated vertices, that is, S contains only subdivision vertices of G or pendants vertices. Also this immediately implies that (G -S) |= γ. Let S be the set of subdivision vertices of S and let X be the set of pendant vertices in S. We define F to be the set of edges of G corresponding to the subdivision vertices in S , that is, F = {e ∈ E(G) | v e ∈ S }. We have that |F | k. Let also X be the set of pendant vertices in S. Observe again that our reduction algorithm for graphs produces G -S from G -F . Then by Claim 5.2, we have that (G -F ) |= φ. We conclude that (G, k) is a yes-instance of Edge-Removal to φ.

To complete the proof of the lemma, observe that the size of ψ is polynomial in the size of φ by our construction of the formula and this shows (i). To show (ii), observe that ψ ∈ Σ s+1 if φ ∈ Σ s and ψ ∈ Π s+1 if φ ∈ Π s . The last claim (iii) of the lemma immediately follows from Claim 5.3.

W[2]-hardness

In this subsection we show that there are formulas φ in Π 2 and Π 3 for which Edge-Removal (Editing) to φ and Vertex-Removal to ψ. respectively are W[2]-hard when parameterized by k. First, we show the claim for Edge-Removal to φ and Edge-Editing to φ. Lemma 6. There is an FOL-formula φ ∈ Π 2 without free variables with 5 variables such that Edge-Removal to φ and Edge-Editing to φ are W[2]-hard.

Proof. We define the formula φ as follows:

φ = ∀x∃y 1 ∃y 2 ∃y 3 ∃y 4 [(x ∼ y 1 ) ∧ (x ∼ y 2 ) ∧ (x ∼ y 3 ) ∧ (x ∼ y 4 ) ∧ (y 1 ∼ y 2 ) ∧ (y 1 ∼ y 3 )∧ (y 2 ∼ y 3 ) ∧ (y 2 ∼ y 4 ) ∧ (y 3 ∼ y 4 ) ∧ ¬(y 1 = y 4 ) ∧ ¬(y 1 ∼ y 4 )].
In terms of graphs, G |= φ means that for every vertex x of G, there are vertices y 1 , y 2 , y 3 , y 4 such that these vertices together with x induce the graph W shown in Fig. 1. We say that W is a φ-witness subgraph rooted in x. We show hardness for Edge-Editing to φ by reducing the Set Cover problem:

Set Cover

Parameter: k Input: A family of sets S over the universe U and a positive integer k. Question: Is there a subfamily S * ⊆ S of size at most k that covers U , that is, every element of U is in one of the set of S * ? It is well-known that Set Cover is W[2]-hard when parameterized by k [START_REF] Downey | Fundamentals of Parameterized Complexity[END_REF].

Let (U, S, k) be an instance Set Cover, S = {S 1 , . . . , S m } and U = {u 1 , . . . , u n }. We construct the graph G as follows.

• For each i ∈ {1, . . . , m}, construct the graph H i with 4 root vertices s 1 i , s 2 i , s 3 i , s 4 i as it is shown in Fig. 2 a). • For each j ∈ {1, . . . , n}, construct 2k + 1 vertices u 0 j , . . . , u 2k j and make them adjacent to the root vertices of all the gadgets H r such that the element u j of the universe U is in the set S r ∈ S.

We claim that (U, S, k) is a yes-instance Set Cover if and only if (G, k) is a yesinstance of Edge-Editing to φ.

Suppose that (U, S, k) is a yes-instance Set Cover. Let S * ⊆ S be a family of size at most k that covers U . We construct the set of edges F of G as follows. For every S i ∈ S * , we include the edge s

1 i s 4 i of the gadget H i in F . Clearly, |F | k. Let G = G F = G -F .
We show that G |= φ. Recall that we have to show that for every x ∈ V (G ), there are y 1 , y 2 , y 3 , y 4 , such that G[{x, y 1 , y 2 , y 3 , y 3 }] is a φ-witness subgraph rooted in x. For x ∈ m i=1 V (H i ), such subgraphs are shown in Fig. 2 b). Let x = u h j for j ∈ {1, . . . , n} and h ∈ {0, . . . , 2k}. The element u j ∈ U is covered by some set S i ∈ S * . Since

s 1 i s 4 i ∈ F , we have that G[u h j , s 1 i , s 2 i , s 3 i , s 4 i ] is a φ-witness subgraph rooted in x.
We conclude that G |= φ and, therefore, (G, k) is a yes-instance of Edge-Editing to φ.

Assume that (G, k) is a yes-instance of Edge-Editing to φ. Then there is

F ⊆ V (G) 2 with |F | k such that for G = G F , it holds that G |= φ. Consider the auxiliary graph Q = (V (G), F ). For i ∈ {1, . . . , m}, let δ i = v∈V (H i ) d Q (v). We define S * = {S i | 1 i m, δ i 2}. Because |F | k, n i=1 δ i 2k and, therefore, |S * | k.
We claim that S * covers U . To obtain a contradiction, assume that there is j ∈ {1, . . . , n} such that u j is not covered by S * . Since |F | k, there is h ∈ {0, . . . , 2k} such that the vertex u h j is not incident to the pairs of F . Because G |= φ, there is a φ-witness subgraph rooted in x = u h j . Hence, there are y 1 , y 2 , y 3 , y

4 ∈ V (G) such that G[{x, y 1 , y 2 , y 3 , y 4 }] is a φ- witness subgraph. Notice that y 1 , y 2 , y 3 , y 4 ∈ ∪ m i=1 V (H i ). Observe that if y s ∈ V (H i ), then F ∩ V (H i ) 2 = ∅, because δ i 1.
Hence, it cannot happen that y 1 , y 2 , y 3 , y 4 ∈ V (H i ) for some i ∈ {1, . . . , m}, because it would mean that {y 1 , y 2 , y 3 , y

4 } = {s 1 i , s 2 i , s 3 i , s 4 i } but G [{s 1 i , s 2 i , s 3 i , s 4 i }] = K 4 , a contradiction. Therefore, there are distinct i, i ∈ {1, . . . , n} such that V (H i ) ∩ {y 1 , y 2 , y 3 , y 4 } = ∅ and V (H i ) ∩ {y 1 , y 2 , y 3 , y 4 } = ∅. Since δ i , δ i 1, there is a unique pair ab of F such that a ∈ V (H i ) and b ∈ V (H i ). Moreover, ab is a bridge of G [∪ m s=1 V (H s )
] and, therefore, ab is a bridge of G [{y 1 , y 2 , y 3 , y 4 }]. This contradicts the fact that W -x is 2-connected. We conclude that S * covers U . Hence, (U, S, k) is a

We claim that (G , k ) is a yes-instance of Vertex-Removal to φ if and only if there is i ∈ {1, . . . , t} such that (G i , k) is a yes-instance of Clique.

Suppose that there is i ∈ {1, . . . , t} such that (G i , k) is a yes-instance of Clique. Then G i has a clique K of size k. Let S = V (G) \ K. Note that |S| = n -k = k . Now for x = u 1 i , we have that the neighborhood of x in G is the clique K, that is, (G , k ) is a yes-instance of Vertex-Removal to φ.

Assume that (G , k ) is a yes-instance of Vertex-Removal to φ. Then there is a set of vertices S ⊆ V (G ) of size at most k such that (G -S) |= φ. Let G = G -S. We have that there is x ∈ V (G ) such that the neighborhood of x in G is a clique. Then there is i ∈ {1, . . . , t} such that x ∈ V (G i ) or x ∈ {u 1 i , . . . , u n-k+2 i }. Suppose that x ∈ V (G i ). Since |S| k = n -k, x is adjacent in G to at least two distinct vertices of {u 1 i , . . . , u n-k+2 i } but these two verices are not adjacent. It implies that x ∈ {u 1 i , . . . , u n-k+2 i } and the neighborhood of

x in G is V (G i ) \ S, that is, K = V (G i ) -S is a clique. Because |S| k , we have that |K| n -k = k, that is, (G i , k) is a yes-instance of Clique.
Since |V (G )| = O(nt) and k = O(n), we conclude that Vertex-Removal to φ has no polynomial kernel unless NP ⊆ coNP/poly by Theorem 6.

We have that Lemmata 9 and 10 imply Theorem 2 (ii).

Conclusion

In this paper we have provided necessary and sufficient conditions (subject to some complexity assumptions) on the fixed-parameter tractability, as well as polynomial kernelization, of graph modification problems to the properties expressible by an FOL-formula from a certain prefix class. While we stated our results for undirected graphs, in fact, all our results could be rewritten for directed graphs. In particular, the FPT and kernelization algorithms work for directed graphs without any changes. For the hardness proofs, we need only a minor modification. Denote by arc(x, y) the predicate for variables x and y meaning that (x, y) is an arc of a directed graph. Denote by φ the FOL-formula on directed graphs obtained from an FOL-formula φ on undirected graphs by replacing every predicate x ∼ y with arc(x, y) ∨ arc(y, x). Then we have the following observation. Observation 2 immediately implies that whenever Vertex Removal to φ or Edge Removal/Completion/Editing to φ is hard (W[2]-hard or does not have a polynomial kernel unless NP ⊆ coNP/poly), the same holds for the variant of the problem on directed graphs. The straightforward reduction constructs a directed graph from an undirected graph G by turning its edges to arcs by assigning arbitrary orientations.

Our results are for FOL-formulas. It would be very interesting to obtain a similar type of dichotomies for prefix classes of Monadic Second Order Logic (MSOL) formulas on graphs. MSOL is substantially richer and allows to express more interesting graph properties like connectivity that cannot be expressed in FOL. The crucial difference is that while Model Checking for FOL-formulas can be solved in polynomial time for formulas of bounded size (see Theorem 5), the problem for MSOL is well-known to be NP-complete even for formulas whose size is bounded by a constant.

Claim 1 . 1 .

 11 For every S ⊆ V (G) such that S is disjoint with u and (G -S, u) |= φ[x], S contains at least one vertex of v. The proof is by contradiction. Assume that (G -S, u) |= φ[x] but S and v are disjoint. Then (G -S, uv) |= φ[xy]. By definition, this means that there is a t-tuple of vertices w of G -S such that (G -S, uvw) |= φ[xyz]. In other words, χ evaluates to true if the x, y and z-variables are assigned to u, v and w respectively. This immediately implies that (G, uvw) |= φ[xyz] and, therefore, (G, uv) |= φ[xy]. This contradicts the assumption that (G, uv) |= φ[xy].

  then return S and stop. 2. Otherwise, for an s-tuple v = v 1 , . . . , v s of vertices of G -S such that (G -S, uv) |= φ[xy], do the following: (i) if |S| = k or all the vertices of v are in u, then stop;

  s of vertices of G, then return F and stop. 2. Otherwise, for an s-tuple v = v 1 , . . . , v s of vertices of G such that (G -F, uv) |= φ[xy], do the following: (i) set L ⊆ E(G) be the set of edges with both end-vertices in uv, (ii) if |F | = k or L = ∅, then stop;

Claim 5 . 3 .

 53 The instance (G, k) is a yes-instance of Edge-Removal to φ if and only if (G , k) is a yes-instance of Vertex-Removal to ψ.To show the claim, assume first that (G, k) is a yes-instance of Edge-Removal to φ. Then there is F ⊆ E(G) of size at most k such that (G -F ) |= φ. We define S ⊆ V (G )be the the set of the subdivision vertices of G corresponding to the edges of F , that is, S = {v e | e ∈ F }. Clearly, |S| k. Notice that our reduction algorithm for graphs produces G -S from G -F . Hence, by Claim 5.2, (G -F ) |= γ. Because G -S has no isolated vertices, we have that (G -S) |= ψ. It means that (G , k) is a yes-instance of Vertex-Removal to ψ.

3 Figure 1 :

 31 Figure 1: The φ-witness graph W .

Figure 2 :

 2 Figure 2: Construction of H i and the witness subgraphs for the vertices of H i . The witness subgraphs are shown by thick lines and the other edges are shown by dashed lines.

Observation 2 .

 2 Let G be the underlaying undirected graph of a directed graph D and let φ be an FOL-formula on undirected graphs without free variables. Then G |= φ if and only if D |= φ.

  that in our construction of γ, we do not create new alternations of quantifications, that is, γ ∈ Σ s+1 or in Π s+1 depending on whether α ∈ Σ s+1 or in Π s+1 . The construction of γ implies the next claim.

Claim 5.2. G |= φ if and only if G |= γ. Moreover, for every set of pendant vertices X of size at most k, G |= φ if and only if (G -X) |= γ.

Acknowledgments. We are grateful to Pål Drange for his very helpful remarks.

* The two first authors have been supported by the Research Council of Norway via the projects "CLAS-SIS" and "MULTIVAL". The third author has been supported by projects DEMOGRAPH (ANR-16-CE40-0028) and ESIGMA (ANR-17-CE23-0010). All authors have been supported by the Research Council of Norway and the French Ministry of Europe and Foreign Affairs, via the Franco-Norwegian project PHC AURORA 2019.

yes-instance Set Cover.

This concludes the W [START_REF] Bodlaender | On problems without polynomial kernels[END_REF]-hardness proof for Edge-Editing to φ. To show that Edge-Removal to φ is W [START_REF] Bodlaender | On problems without polynomial kernels[END_REF]-hard when parameterized by k, we use the same reduction. Note that to show that if (U, S, k) is a yes-instance of Set Cover then (G, k) is a yes-instance of Edge-Editing to φ, we constructed F ⊆ E(G), that is, we proved that (G, k) is a yes-instance of Edge-Removal to φ. Lemma 6 and Observation 1 imply Theorem 3 (ii). To show the claim for Vertex-Removal to φ we combain Lemma 6 with Lemma 5 and obtain the following lemma that implies Theorem 1 (ii).

Lemma 7.

There is a constant c such that there is an FOL-formula φ ∈ Π 3 without free variables that has at most c variables such that Vertex-Removal to φ is W[2]-hard.

Kernelization lower bounds

In this subsection we obtain the kernelization lower bounds for Edge-Removal (Editing) to φ and Vertex-Removal to ψ.

First, we show the lower bounds for Edge-Removal to φ and Edge-Editing to φ for Π 1 -formulas. To do it, we use the known results about kernelization lower bounds for the H-Free Edge Removal and H-Free Editing. Recall that for a graph H, H-Free Edge Removal (H-Free Editing) asks, given a graph G and a nonnegative integer k, whether there is a set of edges F (a set F ⊆ V (G) 2 respectively) of size at most k such that G -F (G F respectively) does not contain an induced subgraph isomorphic to H. Since the property that a graph G has no induced subgraph isomorphic to H can be expressed by an FOL-formula φ H ∈ Π 1 that has |V (H)| variables, H-Free Edge Removal and H-Free Editing can be written as Edge-Removal to φ H and Edge-Editing to φ H respectively. The first kernelization lower bounds for H-Free Edge Removal and H-Free Editing were obtained by Kratsch and Wahlström in [START_REF] Kratsch | Two edge modification problems without polynomial kernels[END_REF] who proved that there are graphs H for which these problems do not admit polynomial kernels unless NP ⊆ coNP/poly. Some further results were obtained by Guillemot et al. [START_REF] Guillemot | On the (non-)existence of polynomial kernels for P -free edge modification problems[END_REF]. In [START_REF] Cai | Incompressibility of H-free edge modification problems[END_REF] Cai and Cai completely characterized the cases when the problems have no polynomial kernels if H is a path or cycle is 3-connected graph up to the conjecture that NP ⊆ coNP/poly. In particular, they proved that H-Free Edge Removal and H-Free Editing do not have polynomial kernels if H = C 4 unless NP ⊆ coNP/poly. This immediately yields the following lemma. Lemma 8. There is an FOL-formula φ ∈ Σ 1 without free variables that has 5 variables such that Edge-Removal to φ and Edge-Editing to φ have no polynomial kernels unless NP ⊆ coNP/poly. Lemma 8 and Observation 1 prove Theorem 4 (ii). Using 5, we obtain the following lemma for Vertex-Removal to φ. Lemma 9. There is a constant c such that there is an FOL-formula φ ∈ Π 2 without free variables that has at most c variables such that Vertex-Removal to φ is has no polynomial kernel unless NP ⊆ coNP/poly.

Our final task is to show that it is unlikely that Vertex-Removal to φ has a polynomial kernel for Σ 2 -formulas. We do it by using the cross-composition technique introduced by Bodlaender, Jansen and Kratsch [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF] (see also [START_REF] Cygan | Parameterized Algorithms[END_REF] for the introduction to the technique).

Here we only briefly sketch the main notions that we need to apply it.

Let Σ be a finite alphabet. An equivalence relation R on the set of strings Σ * is called a polynomial equivalence relation if the following two conditions hold: i) there is an algorithm that given two strings x, y ∈ Σ * decides whether x and y belong to the same equivalence class in time polynomial in |x| + |y|, ii) for any finite set S ⊆ Σ * , the equivalence relation R partitions the elements of S into a number of classes that is polynomially bounded in the size of the largest element of S.

Let L ⊆ Σ * be a problem, let R be a polynomial equivalence relation on Σ * , and let P ⊆ Σ * × N be a parameterized problem. An OR-cross-composition of L into P (with respect to R) is an algorithm that, given t instances I 1 , I 2 , . . . , I t ∈ Σ * of L belonging to the same equivalence class of R, takes time polynomial in t i=1 |I i | and outputs an instance (I, k) ∈ Σ * × N such that: i) the parameter value k is polynomially bounded in max{|I 1 |, . . . , |I t |} + log t, ii) the instance (I, k) is a yes-instance of P if and only there is i ∈ {1, . . . , t} such that I i is a yes-instance of L.

It is said that L OR-cross-composes into P if a cross-composition algorithm exists for a suitable relation R.

Bodlaender, Jansen and Kratsch [START_REF] Bodlaender | Kernelization lower bounds by cross-composition[END_REF] proved the following theorem.

Theorem 6 ([3]). If an NP-hard problem L OR-cross-composes into the parameterized problem P, then P does not admit a polynomial kernelization unless NP ⊆ coNP/poly.

Lemma 10. There is φ ∈ Σ 2 without free variables that has 3 variables such that Vertex-Removal to φ has no polynomial kernel unless NP ⊆ coNP/poly.

Proof. We define the formula φ as follows:

In terms of graphs, G |= φ means that there is a vertex x whose neighborhood is a clique. We consider the Clique problem: Let (G 1 , k), . . . , (G t , k) be equivalent instances of Clique where graphs have n vertices. We construct the instance (G , k ) of Vertex-Removal to φ as follows.

• Construct disjoint copies of G 1 , . . . , G t .

• For every i ∈ {1, . . . , t}, construct n-k +2 vertices u 1 i , . . . , u n-k+2 i and make them adjacent to the vertices of G i .

• Set k = n -k.


S Naceur

M Choubani

B Smiri

H Maaref

G Monier

C Robert-Goumet

L Sfaxi

B Gruzza

R Mghaieth

The effect of nitridation on the optical properties of InAs quantum dots grown on GaAs substrate by MBE

Keywords: Nitridation effect, InAs QDs, X-Ray Photoelectron Spectroscopy (XPS), Photoluminescence (PL), S-shape

InAs/GaAs quantum dots (QDs) under their exposure to a nitrogen plasma were investigated using photoluminescence (PL) and X-Ray Photoelectron Spectroscopy (XPS) techniques. The motivation of this work is to study the effect of nitrogen in InAs QDs, and their role in the amelioration of optical properties. At low temperature, nitrogen addition causes a red-shift of the PL emission. This can be explained by reduction of quantum confinement. Powerdependent analysis of PL exhibit that the transition is about band-to-band intrinsic recombination which may be due to the formation of an lnAsN thin layer at the interface of InAs QDs.

XPS is used to determine the species created at the surface. To follow QDs nitridation, we focused our attention on the N1s and In3d XPS spectra.

The temperature dependent PL measurements in the range 10-300 K for nitrided InAs QDs showed an S-shape in PL peak energy and contributed to an estimated value of exciton localization energy.

In addition, by increasing the time nitridation in InAs QDs, the emission wavelength increases further. Our results displayed a significant improvement of the crystalline quality and enhancement of the optical properties for InAs QDs grown after nitridation.

Introduction

The growth of self-assembled InAs/GaAs quantum dots (QDs) has been studied extensively in recent years with particular prominence on optoelectronic devices [1,2] and for high performance and low-cost optical communication lasers [3,4]. However, a large InAs-GaAs lattice mismatch (7%) induces an unwanted quantum dot band gap increase [START_REF] Kikuno | International Conference on Indium Phosphide and Related Materials[END_REF][START_REF] Inoue | Extended Abstracts of the 2005 International Conference on Solid State Devices and Materials[END_REF]. For this reason, in order to decrease this mismatch, nitrogen was added to InAs QDs [START_REF] Inoue | Extended Abstracts of the 2005 International Conference on Solid State Devices and Materials[END_REF].

The active regions of devices in semiconductor electronics have been regularly decreasing in recent years [START_REF] Ueda | [END_REF]. As a result, surfaces and interfaces have a larger influence on device characteristics. So, to eliminate the undesirable effect of the surface on device properties, the technique called 'nitridation' is being vigorously developed. In fact, the surface nitridation technology of III-V semi-conductors [8-10] has been a critical way for to extend the emitting wavelength [11,12]. Yang Zhao et al showed a significant improvement of the crystalline qualities and surface morphologies and enhancement of the electrical and optical properties for InN films after nitridation [13].

The photoluminescence study versus temperature provides useful information about the material, which is of considerable practical and theoretical interest. Nitridation of GaAs has been extensively studied mainly as the initial stage of GaN growth on GaAs wafers and as a method for the preparation of thick GaN layers [14-16]. To our knowledge, there have been very few reports on the nitridation of InAs. This paper reports on the optical properties of InAs QDs grown on GaAs (100) substrate by solid source molecular beam epitaxy (MBE), which have been studied by X-Ray Photoelectron Spectroscopy (XPS) and PL experiments. We investigate the influence of nitridation on optical properties in InAs QDs. Also, we will discuss the influence of time nitridation in such structures.

Experimental details

Self-assembled InAs QDs were grown on GaAs substrate by MBE system with using Stranski -Krastanov (SK) process. Active N species were created in radio-frequency (rf) plasma using an electron cyclotron source from ultrapure N 2 gas. The nitrogen partial pressure was 7-8.10 -5 mbar. A 200 nm buffer layer of GaAs was grown at 580°C. InAs deposition was performed at 500°C. The deposition rate of InAs was 3 ML/s, which was estimated from the reflection high energy electron diffraction (RHEED) oscillations. The transition from two-dimensional (2D) wetting layer to three-dimensional (3D) islands growth is determined from the change in the RHEED pattern (fig. 1). The nominal deposition rate was 0.4 Å/s. The studied samples S0 and S1 corresponding, respectively, to non-capped and capped GaAs layer. After growing InAs QDs, we performed atomic layer nitridation for two different durations of 1 and 3 hours (respectively for S2 and S3 samples).

The in-situ method based on X-Ray Spectroscopy (XPS) is developed in order to determine the nanostructure surface and chemical bonding [17] of a deposited InAs QDs on GaAs substrate after nitridation. XPS measurements were carried out in an UHV chamber equipped with an XPS system (dual anode Al-Mg X-ray source and hemispherical electron energy analyzer OMICRON EA125). The Mg Kα source (1253.6 eV) is separated from the analyzer by an angle of 55° (almost the "magic angle": L = 1), constant pass energy of the analyzer equal to 20 eV and Medium Magnification Mode was used for analysis. Considering the absence of adventitious carbon on the surface, binding energy was referenced to As3d5/2 peak of the GaAs substrate at 40.4 eV. Photoluminescence (PL) was measured to characterize the nitrided QDs. The samples were excited by 514 nm line of Ar + ion laser. Spectral analysis of the luminescence measurements was dispersed using Jobin Yvin HRD1 monochromator and detected by a thermoelectrically cooled Si photodetector. The excitation density was fixed at 80 W/cm 2 .

Results and discussion

Fig. 2 shows the 10 K PL spectra of S0, S1 and S2 samples using 80 mW excitation in the range of 750-1100 nm. In order to determine the exact peak energy of each samples, PL spectra were deconvoluted by using OriginPro analysis software with Gaussian function. Due to band-to-band recombination in GaAs, the A band appears in S0, S1 and S2 at the same energy around 1.44 eV (gap of GaAs). The wide peak B appears at energies 1.24 and 1.22 eV with a full width at half maximum (FWHM) of 157 and 140 meV, respectively, for S1 and S2 samples, which can be attributed to InAs quantum dots (QDs). The origin of the widening can be explained by the carrier scattering processes and quantum dot size variation [18].

Furthermore, we notice that the PL intensity of sample S2 is enhanced more than the intensity of sample S1 which can be explained by the decrease of non-radiative centers due to nitrogen incorporation effect [19,20]. This phenomenon points out the relevance of incorporation of nitrogen in such structure would enhance the PL intensity. Based on the FWHM drop and intensity increase for sample S2 than that of sample S1, the crystalline quality is improved for sample S2. As a result, for sample S2 the enhancement of the crystalline quality is related to nitrogen incorporation. From another side, the presence of oxidation effect can be explained by the absence of GaAs cap layer in sample S0. In this case, the InAs QDs leading to surface roughness show a success of localization of carriers in InAs QDs, which is manifested by the appearance of low InAs QDs PL band.

The PL B-band displays a red shift with nitrogen addition as shown in fig. 2c. The observed red shift of the QD PL by the nitridation is about 20 meV. Two possible explanations could be related to this behavior of PL peak for our samples: (i) the dislocations that were located in nitrided InAs QDs and (ii) the weaken of quantum confinement effect. In fact, according to the PL results as described above, the model which can be considered for our nitrided QDs is that a thin lnAsN layer [21] covers the InAs QDs. A similar conclusion was also reported by V. Sallet et al [11] attributed the low energy shoulder in nitrided InAs QDs to the reduction of quantum confinement.

In order to understand the nature of InAs peaks energies, the PL spectra at different optical excitation powers varying between 8 and 80 mW were measured as shown in fig. 3 a andb.

We notice that for sample S1 and S2, the PL intensity decreases with decreasing excitation power. By fitting the PL intensity drop, we obtained that the exponent n is at around of the unity and no saturation at higher excitation power [22] is detected (fig. 4). This indicates that this PL transition is not ascribed to any impurity or defects, yet it is an intrinsic recombination To monitor the nitridation, in situ XPS measurements were performed. Using this technique, a large surface area is analyzed, gathering information from the InAs QDs and the GaAs substrate. Then we focused our attention on the N1s and In3d XPS spectra to specifically follow the nitridation of the QDs. Fig. 6 show these spectra at TOA=0° (take off angles) for samples S2 and S3. The N1s and In3d spectra are fitted using Gaussian peak after removing The temperature dependence of the PL peaks exhibits an S-shape phenomenon linked to the exciton localization. To prove our hypothesis, a detailed study as function of PL temperature is performed. The PL peak energy, the FWHM and the PL intensity are depicted in fig. 9. We focus our study on the PL peak emission. The S-shaped form temperature dependence of emission energy, i.e. a red-blue-red shift with increasing temperature, is clearly shown. It exhibits an anomalous behavior between 10 and 300 K and can be divided into three temperature intervals. Firstly, at low temperature from 10 to 30 K, the emission energy peak shows a red shift. This behavior is attributed to the recombination of photo-generated carriers trapped by localized states [32][33][34]. In fact, it is related to the modulated potential structure due to the non uniform insertion of nitrogen atoms. At the intermediate PL temperature between 30 and 90 K, a significant increase of temperature thermalizes the localized carriers leading to the blue shift of the emission peak. Finally, at even higher temperature (90-300 K), the temperature dependence peak energy is mainly dominated by band-to-band transition and the peak energy will decrease as a thermal shrinkage of band gap energy [35].

Then, for PL linewidth (FWHM), the PL peak increases at high temperature and then drops above. This behavior can be clarified by transfer and thermalization of localized states. When the temperature increases up to the thermalization point, some of localized carriers occupy shallower localized states. This leads to linewidth increase. When approaching the high temperature, most localized carriers become progressively mobile [36].

Finally, the temperature dependence of PL peak intensity was investigated. At low temperature (T<30 K), PL intensity decreases. With increasing temperature, it is shown that the PL intensity of each sample increases first and then decreases drastically. At sufficiently high temperatures (beyond 60 K) , the mobility of the carriers increases, more carriers can reach to the localization potential within the potential minima where the PL peak is originated, which makes the spectral peak intensity increase. By increasing temperature further, the overall emission intensity gradually decreases. It indicates that the non-radiative recombination starts to dominate over the radiative recombination process [37].This should correspond to the thermal activated non-radiative recombination mechanism.

In fig. 10 and in order to understand the mechanism of carrier thermal quenching in this system, we fit the experimental data of the integrated PL intensity (I PL ) as a function of reciprocal temperature by using the Arrhenius equation [38]:

0 ( ) 1 exp( ) a b I I T E A k T = - + (1)
Where I 0 is the PL intensity at 10K, A are the pre-factor including information about the escape rate of charge carriers, and E a are the thermal activation energies, which are the slope of Arrhenius plot and obtained by choosing the best fit.

Conclusion

To sum up, we have studied self-assembled InAs QDs grown on GaAs substrate by molecular beam epitaxy (MBE) with and without nitrogen addition. PL measurement revealed that nitrogen has a significant effect on the optical properties. At low temperature, a red-shift of the InAs QDs transition has been observed with nitrogen addition. This can be explained by reduction of quantum confinement. The power-excitation density PL measurements confirm the type-II transition in nitrided sample, which may be due to the formation of a new layer at the interface of InAs QDs.

In situ XPS measurements after nitridation were performed. The QDs nitridation was confirmed by the detection of In3d and N1s XPS peaks. A detailed analysis of N1s XPS peaks reveals the presence of three contributions ascribed to In-N and Ga-N bonds, a mixed compound In-(As,N) and some interstitial nitrogen.

The enhancement of PL intensity of nitrided sample is caused by the defect states, which produced non-radiative centers. A systematic study of PL temperature dependence has shown an S-shape as a result of the competition process between localized and delocalized states at the interface. This phenomenon is more enhanced for the nitrided sample.

We show also that the long duration of nitridation of InAs QDs deteriorates drastically the material quality.

The InAs QDs grown after nitridation exhibited a significant improvement of optical properties. All these results show the possibility to integrate our structure in solar cell devices.

  (band-to-band)[22,23].In addition, we observed a red shift in PL peak energy (P2) with the increase of power excitation for sample S2. All changes are illustrated with arrows in fig.3. This red shift produced at the higher excitation power comes from the band-bending effect [23,24] induced by the spatial separation of electrons and holes at InAs/GaAs interface. This behavior is a fingerprint of a type-II radiative recombination[START_REF] Matsushita | International Conference on Indium Phosphide and Related Materials[END_REF]. For this reason, may be a new layer was produced at S2 sample caused by nitrogen incorporation. These results require more investigations.

Fig. 5 a

 5 Fig.5 a and b show the PL response of our structure at room temperature (300 K). For sample S1, a Gaussian fit of the PL spectra shows two peaks located at around 0.862 µm (1.430 eV) for GaAs and 1.010µm (1.228 eV) for InAs QDs. For sample S2, the two peaks are located at around 0.862 µm (1.430 eV) and 1.014 µm (1.223 eV) respectively for GaAs and InAs QDs. These results show the possibility of our structure application in optoelectronic devices such as solar cell [26].

Fig. 8 a

 8 Fig.8 a and b show the temperature dependent PL spectra with a fixed excitation of 80W/cm 2 measured at temperatures varying from 10 K to 300 K.

FiguresFig. 1 :

 1 Figures

Fig. 2 :

 2 Fig.2: (a), (b) and (c) Low temperature PL spectra of InAs/GaAs quantum dots for S0, S1 and S2 samples.

Fig. 3 :Fig. 4 :

 34 Fig.3: (a) and (b) PL spectra of samples S1 and S2 at 12 K at different excitation powers. This last vary from 0.8 to 80 W/cm 2 .

Fig. 5 :

 5 Fig.5: (a) and (b) Room temperature PL spectra respectively for samples S1 and S2. The dash lines are the Gaussian-fitting curves.

Fig. 6 :

 6 Fig.6: In3d and N1s photoelectron spectra for the nitridated samples S2 (a) and (b) and S3 (c) and (d) respectively.

Fig. 7 :

 7 Fig.7: Variation of PL Intensity as function of nitridation time.

Fig. 8 :

 8 Fig.8: Temperature-dependent PL spectra respectively for samples S1 (a) and S2 (b).

Fig. 9 :

 9 Fig.9: Temperature dependence of PL peak energy (a), the full width at half maximum (FWHM) (b) and PL intensity (c) of samples S1, S2 and S3.

Fig. 10 :

 10 Fig.10 : (a) and (b) Evolution of the integrated intensity for the transition type I versus the inverse of the temperature (black scatters) and the corresponding linear fit (red line), for S1 and S2 samples, respectively.

Fig. 1 :Fig. 2 :Fig. 3 :Fig. 4 :Fig. 5 :Fig. 6 :Fig. 7 :Fig. 8 Fig. 10 :

 1234567810 Fig.1:

  The value of E a gives us an idea about the depth of confining potential[37]. activation energy values are 10 and 16 meV respectively for sample S1 and Sample S2. It is obvious that the carriers need more thermal energy to overcome (i.e. larger depth of confining potential). It is interpreted as the presence of impurities and defects as non-radiative recombination centers in PL recombination. It is a competition between radiative and non radiative channels.

	The

Acknowledgements

This work was supported by the University of Monastir, Laboratory of Micro-Optoelectronic and Nanostructures, Department of Physics, Faculty of Sciences Monastir, Tunisia and Clermont University, University of Blaise Pascal, Institute of Pascal, BP 10448, F-63000 Clermont-Ferrand, France and research Laboratory CNRS, UMR 6602, IP, F-63171 Aubière, France.

The authors have no affiliation with any organization with a direct or indirect financial interest in the subject matter discussed in the manuscript

The following authors have affiliations with organizations with direct or indirect financial interest in the subject matter discussed in the manuscript:

Author's name Affiliation

Syrine Naceur

Faculté des sciences Monastir, Tunisie.

Mohsen Choubani

Faculté des sciences Monastir, Tunisie.

Badreddine Smiri

Faculté des sciences Monastir, Tunisie.

Hassen Maaref

Faculté des sciences Monastir, Tunisie.

Guillaume Monier

Institut Pascal, Université Clermont Auvergne, France. Christine Robert-Goumet Institut Pascal, Université Clermont Auvergne, France.

Larbi Sfaxi

Faculté des sciences Monastir, Tunisie.

Bernard Gruzza

Institut Pascal, Université Clermont Auvergne, France.

Ridha Mghaieth

Faculté des sciences Monastir, Tunisie.