Cristina Bazgan
email: bazgan@lamsade.dauphine.fr

Morgan Chopin
email: chopin@lamsade.dauphine.fr

The Robust Set problem: parameterized complexity and approximation

In this paper, we introduce the k-Robust Set problem: given a graph G = (V, E), a threshold function t : V → N and an integer k, find a subset of vertices V ⊆ V of size at least k such that every vertex v in G has less than t(v) neighbors in V . This problem occurs in the context of the spread of undesirable agents through a network (virus, ideas, fire, . . .). Informally speaking, the problem asks to find the largest subset of vertices with the property that if anything bad happens in it then this will have no consequences on the remaining graph. The threshold t(v) of a vertex v represents its reliability regarding its neighborhood; that is, how many neighbors can be infected before v gets himself infected. We study in this paper the parameterized complexity of k-Robust Set and the approximation of the associated maximization problem. When the parameter is k, we show that this problem is W[2]-complete in general and W[1]-complete if all thresholds are constant bounded. Moreover, we prove that, if P = N P , the maximization version is not n 1--approximable for any > 0 even when all thresholds are at most two. When each threshold is equal to the degree of the vertex, we show that k-Robust Set is fixed-parameter tractable for parameter k and the maximization version is APX-complete. We give a polynomial-time algorithm for graphs of bounded treewidth and a PTAS for planar graphs. Finally, we show that the parametric dual problem (n -k)-Robust Set is fixedparameter tractable for a large family of threshold functions.

Introduction

The subject of optimization problems that involve a diffusion process through a network is a large and well-studied topic [START_REF] Kempe | Maximizing the spread of influence through a social network[END_REF][START_REF] Chen | On the approximability of influence in social networks[END_REF][START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF][START_REF] Dreyer | Irreversible k-threshold processes: Graphtheoretical threshold models of the spread of disease and of opinion[END_REF][START_REF] Ben-Zwi | Treewidth governs the complexity of Target Set Selection[END_REF]. Such problems share a common idea of selecting an initial subset of vertices to activate in a graph such that, according to a propagation rule, all vertices are activated once the propagation process stops. One such representative problem is the Target Set Selection problem first introduced in [START_REF] Chen | On the approximability of influence in social networks[END_REF]: given a graph G = (V, E) and a threshold function t : V → N , the problem asks to find the minimum number of vertices to activate such that all vertices are activated at the end of the propagation process. A vertex v is activated if and only if the number of its activated neighbors is above the threshold t(v). This problem has been proved NP-complete even when all thresholds are at most two [START_REF] Chen | On the approximability of influence in social networks[END_REF]. Moreover, the problem was surprisingly shown to be hard to approximate within a ratio O(2 log 1-n ) for any > 0 even when all thresholds are at most two [START_REF] Chen | On the approximability of influence in social networks[END_REF]. The same inapproximability result holds with majority thresholds i.e, for each v ∈ V, t(v) = d(v) 2 [START_REF] Chen | On the approximability of influence in social networks[END_REF]. From a parameterized perspective, Target Set Selection is W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]-hard with respect to the solution size for majority thresholds and for thresholds at most two [START_REF] Nichterlein | On tractable cases of target set selection[END_REF]. Furthermore, the problem is proved to be in XP and W [START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF]-hard with respect to the treewidth [START_REF] Ben-Zwi | Treewidth governs the complexity of Target Set Selection[END_REF]. These negative results emphasis the strong intractability nature of the problem.

With regards to the motivation for this study, it is an interesting question to ask the complexity of the converse problem: find the largest subset of vertices such that if a set of vertices gets infected in it then there will be no consequence for all the other vertices. In this context, there is no propagation process involved like in the previous problem; here we want to prevent such phenomenon. This idea of "controlling" the diffusion of dangerous ideas or epidemics is also wellstudied [START_REF] Kimura | Blocking links to minimize contamination spread in a social network[END_REF][START_REF] Finbow | The firefighter problem: a survey of results, directions and questions[END_REF][START_REF] Chalermsook | Resource minimization for fire containment[END_REF]. More formally, we introduce the k-Robust Set problem: given a graph G = (V, E), a threshold function t : V → N and an integer k, find a subset of vertices V ⊆ V of size at least k such that every vertex v in G has less than t(v) neighbors in V . The set V is said to be robust. Indeed, if one infects any subset S ⊆ V then there will be no propogation at all since every vertex has a number of infected neighbors below its threshold. Finally, it is worth pointing out that our problem can also be related to a recent paper about the (σ, ρ)-Dominating Set problem [START_REF] Golovach | Parameterized complexity of generalized domination problems[END_REF].

In this paper, we study the parameterized complexity of k-Robust Set and the approximation of the associated maximization problem Max Robust Set. The paper is organized as follows. In Section 2 we give the definitions, terminology and preliminaries. In Section 3 we establish parameterized intractability results for k-Robust Set with various threshold functions. We show that the parametric dual problem (n -k)-Robust Set is fixed-parameter tractable for a large family of threshold functions. In Section 4 we give a polynomial-time algorithm to solve k-Robust Set for graphs of bounded treewidth. In Section 5 we establish that Max Robust Set is not n 1--approximable for any > 0 even when all thresholds are at most two. If each threshold is equal to the degree of the vertex, we show that Max Robust Set is APX-complete. Conclusion and open problems are given in Section 6. Due to the space limit, some proofs are omitted.

Preliminaries

In this section, we give the notation used throughout this paper as well as the statement of the problems. We will conclude this section by providing the basic backgrounds on parameterized complexity and approximation.

Graph terminology. Let

G = (V, E) be an undirected graph. The open neigh- borhood of a node v ∈ V , denoted by N (v), is the set of all neighboors of v. The closed neighborhood of a node v, denoted N [v], is the set N (v) ∪ {v}. The degree of a node v is denoted by d G (v) or simply d(v) if the graph is clear from context. Let X ⊆ V , we denote by G[X] the subgraph of G induced by X. Problem definitions. Let G = (V, E) be an undirected graph, a threshold function t : V → N . A subset V ⊆ V is called robust if ∀v ∈ V, d V (v) < t(v).
We call a vertex bounded if t(v) = O(1); otherwise, it is said unbounded. We define in the following the problems we study in this paper.

k-Robust Set

Input: A graph G = (V, E), a threshold function t : V → N where 1 ≤ t(v) ≤ d(v)
for every v ∈ V , and an integer k Parameter: k Question: Is there a robust set V ⊆ V of size at least k?

We considered also the parametric dual problem (n -k)-Robust Set which asks for the existence of a robust set of size at least n -k.

The optimization version of k-Robust Set is defined as follows.

Max Robust Set

Input: A graph G = (V, E) and a threshold function t :

V → N where 1 ≤ t(v) ≤ d(v) for every v ∈ V Output: A robust set V ⊆ V such that |V | is maximized.
If the threshold function is defined by t(v) = d(v), ∀v ∈ V then we add the suffix With Unanimity to the problem name. The majority threshold is

t(v) = d(v) 2 , ∀v ∈ V .
Parameterized complexity. Here we only give the basics notions on parameterized complexity, for more background the reader is referred to [START_REF] Downey | Parameterized complexity[END_REF][START_REF] Niedermeier | Invitation to Fixed-Parameter Algorithms[END_REF]. A decision problem parameterized by k is said to be fixed-parameter tractable if there exists an algorithm that solves every instance (I, k) in fpt-time i.e., in f (k).|I| O(1) -time for some function f depending solely on k.

The basic class of parameterized intractability is W [START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF] and there is a good reason to believe that W [START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF]-hard problems are unlikely to be fixed-parameter tractable. In fact, there is a all hierarchies of classes W[i] with the following inclusions FPT

⊆ W[1] ⊆ W[2] . . . . A problem in W[i] is considered harder than those in W[i -1]
where i > 1. These classes are defined via the satisfiability problem of boolean circuits. More specifically, a parameterized problem belongs to W[i] if every instance (I, k) can be transformed in fpt-time to a boolean circuit C of constant depth and weft at most i, such that (I, k) is a yes instance if and only if there is a satisfying truth assignment for C of weight exactly k. The weft of a circuit is the maximum number of large gates i.e., gates with a number of inputs not bounded by any constant, on a path from an input to the output. The depth is the maximum number of all gates on a path from an input to the output.

In this paper, the kernel size is expressed in terms of the number of vertices.

Approximation. Given an optimization problem A and an instance I of this problem, we denote by |I| the size of I, by opt A (I) the optimum value of I and by val(I, S) the value of a feasible solution S of I. In this paper, we will make use of the following approximation preserving reduction.

Definition 1 (L-reduction [START_REF] Papadimitriou | Optimization, approximation, and complexity classes[END_REF]). Let A and B be two optimization problems.

Then A is said to be L-reducible to B if there are two constants α, β > 0 and two polynomial time computable functions f , g such that

1. f maps an instance I of A into an instance I of B such that opt B (I ) ≤ α • opt A (I), 2. g maps solutions each solution S of I into a solution S of I such that |val(I, S) -opt A (I)| ≤ β • |val(I , S ) -opt B (I )|.
For us the important property of this reduction is that if A is APX-hard then B is also APX-hard.

Parameterized complexity

In this section, we consider the parameterized complexity of k-Robust Set. In some reductions we make use of the following gadget: a forbidden edge denotes an edge uv where both vertices have threshold one. Attaching a forbidden edge to a vertex w means to create a forbidden edge uv and make w adjacent to u. Notice that none of the three vertices u, v or w can be part of a robust set.

First, we show that k-Robust Set belongs to W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF] using the Turing way, that is, we reduce k-Robust Set to the Short Multi-tape Nondeterministic Turing Machine problem that is proved to belong to W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF] in [START_REF] Cesati | The Turing way to parameterized complexity[END_REF] and defined as follows: given a multi-tape nondeterministic Turing machine M , a word x on the input alphabet of M , and an integer k, determine if there is a computation of M on input x that reaches a final accepting state in at most k steps. The parameter is k.

Theorem 1. k-Robust Set is in W[2].
Proof. We construct an fpt-reduction from k-Robust Set to Short Multitape Nondeterministic Turing Machine as follows. Let (G, t, k) be an instance of k-Robust Set with G = (V, E) and V = {v 1 , . . . , v n }. We construct the following Turing machine M from (G, t, k). We create n + 1 tapes denoted by T 0 , T v1 . . . , T vn . The tapes alphabet is V ∪ {×, 1, . . . , n} plus the blank symbol 0. Initially, every tape is filled with 0. The transition function is defined hereafter. The machine M starts by writing symbol × on tape T 0 and move T 0 's head one step to the right. During the first phase, M non-deterministically chooses k vertices and write them on tape T 0 , that is, if M picks up a vertex v ∈ V then it writes symbol v on T 0 and move T 0 's head one step to the right. The previous procedure is done in k + 1 steps. During the second phase, M verifies that the selected set is a robust set as follows. First, the machine move T 0 's head one step to the left. Assume that T 0 's head reads symbol v and, for every u ∈ N (v), T u 's head reads symbol s u . If s u = t(u) -1 then M goes in rejecting state. Otherwise, M writes symbol s u + 1 on tape T u and moves the T 0 's head one step to the left. We repeat the previous procedure until T 0 's head reads symbol ×. Clearly, this checking phase is performed in at most k + 1 steps. Finally, the input word x is empty and k = 2k + 2. It is not hard to see that (G, t, k) is a Yes-instance if and only if M accepts in at most k steps. Now in order to prove the W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]-hardness of k-Robust Set, we construct a simple fpt-reduction from the problem Red/Blue Dominating Set proved W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]-hard in [START_REF] Downey | Parameterized complexity[END_REF] and defined as follows: given a bipartite graph G = (R ∪ B, E) and a positive integer k, determine if there exists a set R ⊆ R of cardinality k such that every vertex in B has at least one neighbor in R . The parameter is k.

Theorem 2. k-Robust Set is W[2]
-complete even for bipartite graphs.

Proof. Membership follows from Theorem 1. Now, let us show the W[2]-hardness. Given (G, k) an instance of Red/Blue Dominating Set, we construct an instance (G = (V , E ), t, k) of k-Robust Set as follows. We consider the complement Ḡ of the graph G, that is two vertices u ∈ R and v ∈ B are adjacent in Ḡ if and only if they are not adjacent in G. Moreover, the sets R and B remain independent sets. Graph G is obtained from this last graph by attaching max{k -d Ḡ(v), 1} forbidden edges to each vertex v ∈ B. Finally, set t(v) = k for every vertex v ∈ B and t(v) = 1 for every vertex v ∈ R. Adding several forbidden edges to the vertices of B make sure that the threshold of these vertices is less than or equal to their degree as required.

Assume that (G, k) has a solution R ⊆ R of size k. One can see that R is also a solution for (G , t, k) since every vertex in B is not adjacent to at least one vertex in R . Conversely, suppose that there is a robust set S ⊆ V of size k in G . Since S is robust, S cannot contain any vertex from B because of the forbidden edges, and thus S is entirely contained in R. Moreover, every vertex v in B is adjacent in G to at most t(v) -1 = k -1 vertices in S. Hence, every vertex in B is adjacent in G to at least one vertex in S. Therefore, S is a solution of size k for (G, k).

In the next two theorems, we show that k-Robust Set goes one level down in the W-hierarchy when all thresholds are bounded by a constant. Theorem 3. k-Robust Set is in W [START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF] if all thresholds are constant bounded.

Proof. Let (G, t, k) be an instance of k-Robust Set where t(v) ≤ c, ∀v ∈ V for some constant c > 0. We construct in O(n c )-time, where n is the number of vertices of G, a boolean circuit C of depth 3 and weft 1 as follows. We identify the inputs of the circuit with the vertices of G. Connect a ¬-gate to every input. For all v ∈ V and all subsets S ⊆ N (v) of size t(v), add a ∨-gate connected to ¬-gate of inputs in S . Finally, add a large ∧-gate connected to every ∨-gate. It is not hard to see that G admits a robust set of size k if and only if there is a weight-k assignment that satisfies C.

We establish the W[1]-hardness of k-Robust Set by an fpt-reduction from the problem Red/Blue NonBlocker [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF] defined as follows: given a bipartite graph G = (R ∪ B, E) and a positive integer k, determine if there is a set R ⊆ R of cardinality k such that every vertex in B has at least one neighbor that does not belong to R . The parameter is k. This problem remains W [START_REF] Aazami | Approximation algorithms and hardness for domination with propagation[END_REF]-hard even when every vertex in B has degree two and every vertex of R has degree at least two [START_REF] Downey | Fixed-parameter tractability and completeness II: On completeness for W[1[END_REF].

Theorem 4. k-Robust Set is W[1]-complete even 1.
For bipartite graphs and constant majority threshold. 2. For split graphs and constant threshold t(v) = 2, ∀v ∈ V .

Proof. Membership follows from Theorem 3. We now prove the W[1]-hardness.

(1): Let (G, k) be an instance of Red/Blue NonBlocker where vertices in B have degree two, we construct the graph G = (V , E ) from G as follows.

For each vertex v ∈ B, attach a forbidden edge to v.

Set t(v) = d G (v)/2 for all v ∈ V .
Assume that (G, k) has a solution R ⊆ R of size k. It is not hard to see that R is also a solution for (G , t, k). Conversely, suppose that there is a robust set S ⊆ V of size k in G . Because of the forbidden edges, the set S is entirely contained in R. Since R is a robust set, every vertex in B is adjacent to at least one vertex in R \ S. Therefore, S is a solution of size k for (G, k).

(2): Let (G, k) be an instance of Red/Blue NonBlocker where vertices in B have degree two and every vertex of R has degree at least 2, we construct the graph G = (V , E ) from G as follows. Add edges to make B a clique. Set t(v) = 2 for all v ∈ V and k = k. Without loss of generality we may assume that k ≥ 2.

Assume that (G, k) has a solution R ⊆ R of size k. One can easily verify that R is a robust set of size k for (G , k ). Conversely, suppose that there is a robust set S ⊆ V of size k in G . Notice that S ∩ B = ∅ since otherwise we would not have been able to take more than one vertex in G. Indeed, if there are two vertices u, v ∈ S with v ∈ B then there is always a vertex w ∈ B -{u, v} adjacent to both v and u. Thus, S is entirely contained in R. From now, it is not hard to see that R is also a solution for (G, k).

It is interesting to note that the ratio between the number of unbounded vertices and the number of bounded vertices of the graph in the proof of Theorem 2 can be made arbitrarily small (add many forbidden edges). This implies a sharp dichotomy between the W[2]-and W[1]-completeness of k-Robust Set regarding the thresholds.

Unanimity threshold. We consider now the k-Robust Set With Unanimity problem. First, we start with the following easy observation. In the case of unanimous threshold, any robust set is the complement of a total dominating set. Recall that a total dominating set S is a set of vertices such that every vertex has at least one neighbor in S. Moreover, we have the following theorem. Theorem 5. [START_REF] Cockayne | Total domination in graphs[END_REF] If G is a connected graph of order at least 3 then there is a total dominating set of size at most 2n/3. This implies that Max Robust Set With Unanimity always has a solution of size at least n/3 when n ≥ 3. The consequence of this result is that we directly get a linear kernel of size 3k. Indeed, let (G, t, k) be an instance of k-Robust Set With Unanimity, if k ≤ n/3 then the answer is Yes. If k > n/3 then the instance (G, t, k) is a kernel of size at most 3k. However, the parameter k is "large" in this last case. This suggests to look for other parameterizations.

Parametric dual. Now, we show that (n -k)-Robust Set is FPT with respect to parameter k for a large family of threshold functions.

Reduction rule 1 Let (G, t, k) be an instance of (n -k)-Robust Set. If there is a vertex v such that d(v) ≥ k + t(v) -1 then remove v and decrease by one the threshold of every vertex in N (v) to get a new equivalent instance (G , t , k). Lemma 1. Reduction rule 1 is sound.

Proof. Let S ⊆ V be a robust set of size at least n -k. If there is a vertex v with d(v) ≥ k + t(v) -1 then v must be in S since otherwise v has at most k -1 neighbors in V \ S and then at least t(v) neighbors in S.

Theorem 6. (n-k)-Robust Set admits a kernel of size O(k 2 ) if for all v ∈ V t(v) = α v d(v) βv + γ v for any constants α v , β v ∈ [0, 1], α v β v = 1, and γ v ∈ Q.
Proof. Let (G, t, k) be an instance of (n -k)-Robust Set. Exhaustively apply reduction rule 1 to get (G , t , k). Assume that there exists a solution S ⊆ V of size at least n -k. Because of reduction rule 1, we have that

d(v) < k + t(v) -1 = k + α v d(v) βv + γ v -1 ≤ k + α v d(v) βv + γ v We claim that d(v) ≤ θ v (k) for all v ∈ V where θ v (k) = k+γv 1-αv + (1/β v ) 1 1-βv if α v = 1, k+γv 1-βv + (1/β v ) 1
1-βv otherwise. Consider the following cases.

Case 1. If β v = 0 then obviously d(v) ≤ θ v (k) Case 2. If β v = 1 then d(v) < k+γv 1-αv < θ v (k) (since α v < 1) Case 3
. Suppose now that β v ∈ (0, 1). First, it is not hard to show that the following holds:

n βv ≤ β v n if and only if n ≥ (1/β v ) 1 1-βv for any n ≥ 1 and β v ∈ (0, 1). Hence, If d(v) ≥ (1/β v ) 1 1-βv then we have d(v) ≤ k + α v β v d(v) + γ v and thus d(v) ≤ k+γv 1-αvβv ≤ θ v (k). Otherwise d(v) < (1/β v ) 1 1-βv ≤ θ v (k).
Since every vertex from S has at least one neighbor in V -S then |S| has at most |V -S|d max ≤ kθ max (k) vertices where θ max (k) = max v∈V θ v (k) and d max is the maximum degree of vertices in V -S.

The kernelization procedure is then defined as follows. From an instance (G, t, k) of (n -k)-Robust Set, exhaustively apply reduction rule 1 to get an instance (G , t , k).

If |V | > kθ max (k) + k then return a trivial No-instance. Otherwise, return the instance (G , t , k). Notice that if α v = β v = 1 and γ v = 0, ∀v ∈ V then the (n -k)-Robust
Set problem is exactly the Total Dominating Set problem which is known to be W [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]-hard [START_REF] Golovach | Parameterized complexity of generalized domination problems[END_REF].

Algorithm for tree-like graphs

In this section we establish an O(T 2ω n) algorithm for Max Robust Set and a O((k + 1) 2ω n) for k-Robust Set where T is the maximum threshold and ω the treewidth of the input graph.

Using a nice tree decomposition together with a dynamic programming algorithm we can prove the following.

Theorem 7. Max Robust Set is solvable in time O(T 2ω n) where T is the maximum threshold and ω is the treewidth of the input graph.

Now we show that k-Robust Set is solvable in O((k + 1) 2ω n) time.
For that purpose, we introduce the following reduction rule.

Reduction rule 2 Let (G, t, k) be an instance of k-Robust Set. If there is a vertex v such that t(v) > k + 1 then set the threshold t(v) to k + 1 to get a new equivalent instance (G, t , k).
Lemma 2. Reduction rule 2 is sound.

Proof. Let (G = (V, E), k, t) be an instance of k-Robust Set. Exhaustively apply Reduction Rule 2 on (G, t, k) to get a new instance (G, t, k ). It is not hard to see that if S ⊆ V is a robust set of size at least k for (G, t, k), then any subset of size k of S is a robust set for (G, t, k ). The converse is clear.

We are now ready to prove the following. Theorem 8. k-Robust Set is solvable in time O((k + 1) 2ω n) where ω is the treewidth of the input graph.

Proof. Let (G, t, k) be an instance of k-Robust Set. Exhaustively apply Reduction Rule 2 on (G, t, k) to get a new instance (G, t, k ). Apply the algorithm from Theorem 7 on (G, t ) to get the optimal solution of value opt. If opt ≥ k return Yes; otherwise return No. Since every threshold is at most k + 1, the running time is O((k + 1) 2ω n).

Notice that if all thresholds are constant bounded then k-Robust Set is in FPT with respect to parameter treewidth.

Approximability

In this section, we show that Max Robust Set is inapproximable even for small constant thresholds. In order to prove this result, we consider the Max Clique problem: given a graph G = (V, E), find a clique C ⊆ V of maximum size. Theorem 9. If N P = ZP P , Max Robust Set is not approximable within n for any > 0 even for thresholds at most two.

We now prove the APX-completeness of Max Robust Set With Unanimity.

Lemma 3. Max Robust Set With Unanimity is 3-approximable in polynomial time.

Proof. The algorithm consists of the following two steps:

1. Compute a spanning tree T of G. 2. Compute an optimal solution S of T . Using Theorem 7, the algorithm runs in polynomial-time. Clearly, any feasible solution for T is also a solution for G. Moreover, using Theorem 5, we have |S| ≥ n/3 ≥ opt(G)/3. Theorem 10. Max Robust Set With Unanimity is APX-complete.

Proof. Membership follows from Lemma 3. In order to prove the APX-hardness we provide an L-reduction (see Definition 1) from Max E2Sat-3 proved APXhard in [START_REF] Berman | On some tighter inapproximability results (extended abstract)[END_REF] and defined as follows: given a CNF formula φ with n variables and m clauses, in which every clause contains exactly two literals and every variable appears in exactly three clauses, determine an assignment to the variables satisfying a maximum number of clauses. Notice that m = 3n/2.

Given a formula φ of Max E2Sat-3, we construct an instance I = (G = (V, E), t, k) of Max Robust Set With Unanimity as follows (see Figure 1). For every variable x i , we construct the complete bipartite graph K 3,3 (x i ) = (V -(x i ), V + (x i )) in which every edge uv is replaced by an edge-vertex e uv and two edges ue uv and e uv v. We denote by E(x i ) this set of edge-vertices. The vertices in V + (x i ) (resp. V -(x i )) represents the positive (resp. negative) literals of x i . We denote by A the set of all vertices added so far. For every clause c j in φ add two adjacent clause-vertices cj and c j . For every variable x i , if x i appears positively (resp. negatively) in a clause c j then add an edge between c j and a vertex of V -(x i ) (resp. V + (x i )). Thus, vertex cj represents the complement of the clause c j in φ. Finally, add two adjacent vertices c and c . For every vertex v ∈ V -(x i ) ∪ V + (x i ), if v is not adjacent to a clause-vertex then add the edge vc .

The optimal value in I is bounded by the number of vertices of G and thus, opt(I) ≤ 15n + 2m + 2 ≤ 16opt(φ) + 2 ≤ 18opt(φ) since opt(φ) ≥ 3/4m and opt(φ) ≥ 1.

Moreover, let x * ⊆ V be an optimal assignment for φ and let

S = ∪ x * i =1 V + (x i ) ∪ ∪ x * i =0 V -(x i ) ∪ ∪ n i=1 E(x i ) ∪ {c j : c j is satisfied by x * } ∪ {c}.
We can easily verify that S is a robust set and |S∩(V -(x i )∪V + (x i )∪E(x i )| = 12 and thus |S ∩ A| = 8m and then opt(I) ≥ |S| = 8m + opt(φ) + 1.

Let S be a robust set for I. We show in the following how to construct an assignment a S for φ from the solution S such that val(φ, a S ) = |S| -8m -1. For each variable x i , S cannot contain vertices from both V -(x i ) and V + (x i ) since otherwise an edge-vertex has both neighbors inside S. Notice also that S cannot contain any vertex c j , since c j is adjacent to the degree one vertex cj . Similarly c / ∈ S. If S contains for every i = 1, . . . , n the set E(x i ) and one of the sets V -(x i ) or V + (x i ) then |S ∩ A| = 8m and we can defined the following assignment a S :

x i = 1 ⇔ |S ∩ V + (x i )| = 0.
In this case, a clause-vertex is in S if and only if the corresponding clause is satisfied by a S . Thus, the number of clauses satisfied by a S is exactly val(φ, a S ) = |S| -8m -1.

Assume now that |S ∩ A| < 8m. We show that there exists an other solution S with |S | ≥ |S| such that |S ∩ A| = 8m. If a vertex v ∈ E(x i ) \ S for some i ∈ {1, . . . , n}, we can add v in S since v cannot have both neighbors in S. Similarly, if c is not in S, then we add c in S.

Since |S ∩ A| < 8m, there is at least one vertex either in V + (x i ) \ S or in V -(x i ) \ S for some i ∈ {1, . . . , n}. Without loss of generality, we only consider vertices in V + (x i ) \ S. A vertex v ∈ V + (x i ) \ S is either adjacent to c or to a clause-vertex c j . In the first case we add v in S. In the second case, we denote N (c j ) = {v, v , cj }. If v ∈ S and cj ∈ S then remove cj from S and add v instead, otherwise, add v in S. Thus, we obtain a new solution S such that |S | ≥ |S| and |S ∩ A| = 8m and in this case as below, we can obtain an assignment a S such that |S | -val(φ, a S ) = 8m + 1. In particular, if S is an optimal solution, then opt(φ) ≥ val(φ, a S ) = opt(I) -8m -1 and thus, we have opt(I) -opt(φ) = 8m + 1 and then opt(φ) -val(φ, a S ) = opt(I) -|S |. In the following we propose a PTAS on the class of planar graphs, using the polynomial time algorithm for graphs of bounded treewidth.

Theorem 11. Max Robust Set on planar graphs admits a PTAS.

Proof. Given a planar embedding of an input graph, we consider the set of the vertices which are on the exterior face, they will be called level 1 vertices. By induction we define level k as the vertices which are on the exterior face when we have removed the vertices of levels smaller than k [START_REF] Baker | Approximation algorithms for NP-complete problems on planar graphs[END_REF]. A planar embedding is k-level if it has no nodes of level greater than k. If a planar graph is k-level, it has a k-outerplanar embedding.

If we want to achieve an approximation within 1 + ε, let us consider k = 2(1 + 1 ε ). Let X t be the set of vertices of level t and let H i , 0 ≤ i ≤ k -1, be the graph obtained from G by considering the subgraphs formed by the set of vertices t+1≤j≤t+k X j , for t ≡ i (mod (k -2)). The subgraph containing exactly t+1≤j≤t+k X j is k-outerplanar, and so is H i , too.

Since H i is k-outerplanar, it has treewidth at most 3k -1 [START_REF] Bodlaender | A partial k-arboretum of graphs with bounded treewidth[END_REF]. We construct graph H i from H i by attaching a forbidden edge to each vertex on the boundary (that means vertices in X t+1 , X t+2 , X t+k-1 X t+k with t ≡ i(mod (k -2))). Thus, in each subgraph of H i the vertices in X t+1 , X t+2 , X t+k-1 X t+k cannot take part from any robust set.

On applying Theorem 7, we can efficiently determine an optimal robust set in each subgraph of H i . Denote by S i the union of these robust sets. Clearly S i is a robust set on H i .

Among S 0 , . . . , S k-1 we choose the best solution that we denote S and we are going to prove that S is an (1 + ε)-approximation of the optimal value on G. We can easily show that there is at least one r, 0 ≤ r ≤ k -1 such that at most 2 k of vertices in an optimal solution S opt of G are on levels X t+1 , X t+2 , X t+k-1 X t+k with t ≡ r (mod (k -2))). This means that the solution S r obtained by deleting the vertices from levels X t+1 , X t+2 , X t+k-1 X t+k from S opt will have at least

|S opt |(1 -2 k ) = k-

Conclusion

In this paper, we introduced the k-Robust Set problem. We established positive and negative results concerning its parameterized tractability and approximability. However, several questions remain open. For instance, we do not know if the problem is fixed-parameter tractable for parameter treewidth. Another interesting open question is whether k-Robust Set With Unanimity is fixedparameter tractable for parameter k when we ask to determine the existence of a robust set of size at least n 3 + k. Finally, there is room enough for improving the approximability of Max Robust Set With Unanimity.

Fig. 1 .

 1 Fig. 1. The construction of G.

2 k

 2 opt vertices. According to our algorithm, |S| ≥ |S r | ≥ opt 1+ε . The overall running time of the algorithm is k times what we need for graphs of treewidth at most k, that is O(kT 6k-2 n) = n O(1/ε) where T = max v∈V t(v).


Yvan Cuminal

Philippe Christol

Jean-Baptiste Rodriguez

André Joullié

Multiphysic FEMLAB modelling to evaluate mid-infrared photonic detector performances

  L'archive ouverte pluridisciplinaire

Introduction :

Infrared photo detectors operating in the mid infrared region find application in pollution monitoring, high speed infrared imaging systems and free space telecommunications. Currently the dominant infrared detector technology are based on HgCdTe or InSb photovoltaic devices. Because of their narrow band gap these devices show at room temperature (RT) high dark reverse current and small R0.A product, which significantly restrict the getting of high ambient performances. To reduce the darkness current and increase R0.A product, we suggested studying structures with large band gap energy. The objective of the photo detector structures modelling presented in this paper is double. It allows first to simulate and to estimate the theoretical performances of previously introduced large band gap components. As such we shall calculate, the product R0.A and the quantum efficiency to end in the specific detectivity D*. It is also a support to help in the understanding and in the interpretation of the made photo detectors characterizations.

Modelling equations:

This modelling is based on the coupled resolution of the Poisson equation ( 1), the equations of continuity for electrons and holes, respectively equations ( 2) and ( 3) and the equations of continuity under illumination, equations (4) and (5).

Where the three dependent variables are Ψ the electrostatic potential, n and p respectively electron and hole concentrations.

) ( ) ( N n p q + - ⋅ = Ψ ∇ ⋅ ⋅ ∇ -ε (1) SRH n R q J ⋅ - = ⋅ ∇ - (2) SRH p R q J ⋅ = ⋅ ∇ - (3)
With q elementary charge, N represent fixed charges associated to the acceptors and donors ionised.

n n J q n z Gop t n ∇ ⋅ + ∆ - = ∂ ∂ 1 ) ( τ (4) p p J q p z Gop t p ∇ ⋅ - ∆ - = ∂ ∂ 1 ) ( τ (5)

Modelised structures and results :

The model describes previously was applied to two kinds of structures, we present on the figure [START_REF]FEMLAB model library -Semiconductor device models[END_REF] these two structures as well as the meshing used for FEMLAB modelling. Equations (1) (2) (3) (4) (5) were solved for each structure area assuming the continuity of electric potential and electric field at all interior boundaries between each structure layer. For boundaries far from the component active zones, the normal electric field component and the carrier densities are all take as zero equals. At the electric contacts (boundaries in touch with metal), electric potential were considerate as fixed and we assume an infinite recombination velocity on these surfaces. For all the solve wee also suppose that the steady state is reached what suppress any temporal dependence in the equation ( 4) and ( 5). This modelling was done with a multiphysic parametric (1) non-linear resolving using electrostatic and diffusion FEMLAB modules.

As regards this work, we have limited studies to the influence of the active zone width and doping level on the component response. Thanks to this modelling, for both types structures, we have shown a great influence of the active zone doping level on the component detectivity, we have noted in particular an increase of R0.A product with active zone doping, what was not has waited a priori. Concerning structures with superlattice active zones, for a given doping and conduction parameters, the modelling allowed us to put in evidence an optimal thickness for which the detectivity is maximal. This result has shown a relation between carrier diffusion lengths and active zone width. We could easily from this first one model intend to study the photo detector characteristics according to other geometrical parameters such as for example the components size or contact widths. We will also intend to study in near future, the influence of surface states effects on components answer by modification of external boundary conditions in modelling.

Figure 1 :

 1 Figure 1 : Modelised diodes.

Figure 1 (

 1 Figure 1(a) : (Ga)InAsSb active layer diode. Figure 1(b) : InAs/GaSb superlattices active zone diode.

Figure 1 (

 1 Figure 1(a) : (Ga)InAsSb active layer diode. Figure 1(b) : InAs/GaSb superlattices active zone diode.


Brahim Boufoussi
email: boufoussi@ucam.ac.ma

Marco Dozzi
email: dozzi@iecn.u-nancy.fr

Raby Guerbaz
email: r.guerbaz@ucam.ac.ma.

Path properties of a class of locally asymptotically self similar processes

Keywords: Hausdorff dimension, level sets, local asymptotic self-similarity, local nondeterminism, local times. AMS classification codes : 60H10, 60H30, 35K55

Various paths properties of a stochastic process are obtained under mild conditions which allow for the integrability of the characteristic function of its increments and for the dependence among them. The main assumption is closely related to the notion of local asymptotic self-similarity. New results are obtained for the class of multifractional random processes.

Introduction

Let X = (X(t), t ∈ R + ) be a real valued separable random process with Borel sample functions. For any Borel set B, the occupation measure of X on B is defined as follows

µ B (A) = λ{s ∈ B : X(s) ∈ A} for all A ∈ B(R),
where λ is the Lebesgue measure on R + . If µ B is absolutely continuous with respect to the Lebesgue measure on R, we say that X has a local time on B and define its local time, L(B, .), to be the Radon-Nikodym derivative of µ B . Here x is the so-called space variable, and B is the time variable. Sometimes, we write L(t, x) instead of L([0, t], x).

The relation between the smoothness of the local time in its variables and the irregularity of the underlying process has been investigated by S. Berman for Gaussian processes; for instance, if L(t, x) is jointly continuous, then X is nowhere differentiable and has uncountable level sets, see for example [START_REF] Berman | Gaussian processes with stationary increments: local times and sample function properties[END_REF][START_REF] Berman | Harmonic analysis of local times and sample functions of Gaussian processes[END_REF][START_REF] Berman | Local nondeterminism and local times of Gaussian processes[END_REF] for details. The computations required to establish the joint continuity of the local time in the Gaussian case were based on the concept of local nondeterminism [START_REF] Berman | Local nondeterminism and local times of Gaussian processes[END_REF]. In Berman's papers, the smoothness of L(t, x) in time and space was important to prove the irregularity of the original process.

Geman and Horowitz have obtained in a series of papers weaker conclusions under more general conditions; for instance, the irregularity of the sample paths of X was based on the continuity of the local time only as a function of the time parameter, we refer to [START_REF] Geman | Occupation densities[END_REF] for a survey in this area. Berman has extended in [START_REF] Berman | Local nondeterminism and local times of general stochastic processes[END_REF] his definition of local nondeterminism to a wide class of stochastic processes, and has refined his previous results under an assumption of higher order integrability of the local time instead of the smoothness in the space variable. Recently, Kôno and Shieh [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF] have refined the previous results for the class of self similar processes with stationary increments under additional assumptions on the joint density of (X(t), X(s)). Their conclusions have been given in terms of the exponent of self-similarity. Our results may be considered as a continuation in this direction. The assumptions on the process X considered in this paper are framed on the characteristic function of the one-dimensional increments of X (assumption (H) in Section 2) and on the dependence among these increments (assumption (H m ) in Section 2). These assumptions are weak enough to include existing methods related to the Fourier analytic approach initiated by S. Berman, especially various notions of local nondeterminism. They are applicable to cases where the marginal laws and the dependence structure up to a certain order k are known, but where the law of the process itself is unknown, such as the weak Brownian motion of order k (cf. [START_REF] Föllmer | On weak Brownian motions of arbitrary order[END_REF]).

Assumption (H) is closely related to the notion of local asymptotic self-similarity. A real valued stochastic process {X(t), t ∈ R + } is said to be locally asymptotically self similar (lass for brevity), if there exists a non-degenerate process {Y (t), t ∈ R + }, such that for every t ∈ R + :

lim ρ→0 + X(t + ρu) -X(t) ρ H = Y (u), u ∈ R + , (1)
where the convergence is in the sense of the finite dimensional distributions and 0 < H < 1 is the lass exponent. Y is called the tangent process at t and if Y is unique in law, it has stationary increments and it is self similar with exponent H (c.f. [START_REF] Falconer | Tangent fields and the local structure of random fields[END_REF]). Conversely, note that any non degenerate H-self similar process X with stationary increments is H-lass and its tangent process is X itself. The notion of lass processes was introduced in Benassi et al. [START_REF] Benassi | Elliptic Gaussian random processes[END_REF] and Lévy-Véhel and Peltier [START_REF] Lévy-Véhel | Multifractional Brownian motion : definition and preliminary results[END_REF] in order to relax the self-similarity property of fractional Brownian motion. Various examples of lass processes appear nowadays in the literature; for example, filtered white noises [START_REF] Benassi | Identification of filtered white noises[END_REF] and the multi-scale fractional Brownian motion [START_REF] Guerbaz | Hölder conditions for the local times of multiscale fractional Brownian motion[END_REF]. An important class of lass processes are multifractional processes, for which the H-lass parameter is no more constant but a regular function of time, such as multifractional Brownian motions [START_REF] Benassi | Elliptic Gaussian random processes[END_REF][START_REF] Lévy-Véhel | Multifractional Brownian motion : definition and preliminary results[END_REF] and the linear multifractional stable process [START_REF] Stoev | Path properties of the linear multifractional stable motion[END_REF].

The paper is organized as follows. In Section 2, we introduce our assumptions and explain how they are related to the study of lass processes. The continuity of the local time and related irregularity properties of the underlying process are obtained in Section 3 under assumption (H). The joint continuity of the local time required initially in the Gaussian case and the higher order integrability in the space variable assumed in [START_REF] Berman | Local nondeterminism and local times of general stochastic processes[END_REF] are circumvented. Section 4 contains results on the Hausdorff measure and the Hausdorff dimension of the progressive level sets. In Section 5 the joint continuity and Hölder conditions of local time are shown under assumptions (H) and (H m ), and the Hausdorff dimension of level sets at deterministic levels is deduced. The higher smoothness of the local time in the space variable is studied in Section 6. In section 7 we verify (H) and (H m ) for some classes of processes, including sub-Gaussian processes and linear multifractional stable processes. We show how the lass property helps to verify the local nondeterminism of Gaussian multifractional processes. In this sense this paper may be considered as a continuation of previous work [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF][START_REF] Boufoussi | Sample path properties of the local time of multifractional Brownian motion[END_REF][START_REF] Guerbaz | Local time and related sample paths of filtered white noises[END_REF][START_REF] Guerbaz | Hölder conditions for the local times of multiscale fractional Brownian motion[END_REF] on local times of Gaussian multifractional processes. Let us finally mention that an incorrect result in [START_REF] Cohen | From self-similarity to local self-similarity : the estimation problem, Fractals: Theory and Applications in Engineering[END_REF] on the equivalence of versions of the multifractional Brownian motion has been cited in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF]. Proposition 7.2 of this paper proves the local nondeterminism for all versions and confirms therefore the correctness of the results in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF] not only for the moving average version, but also for the harmonisable version of the multifractional Brownian motion.

Assumptions

Let {X(t), t ∈ [0, T ]} be a real valued separable stochastic process with measurable sample paths. The first assumption concerns the integrability of the characteristic function of the increment X(t) -X(s), for 0 < s < t ≤ T < ∞, s and t sufficiently close. Assumption (H) : There exist positive numbers (ρ 0 , H) ∈ (0, +∞)×(0, 1) and a positive function ψ ∈ L 1 (R) such that for all λ ∈ R, t, s ∈ [0, T ], 0 < |t -s| < ρ 0 we have

E exp iλ X(t) -X(s) |t -s| H ≤ ψ(λ).
Comments 1.

1. If X is H-self similar with stationary increments, the assumption (H) is reduced to : ψ(λ) = |E e iλX (1) | belongs to L 1 (R), which is a classical condition in the investigation of local times of H-self similar processes with stationary increments (see [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF]).

2. Assumption (H) is closely related to the study of lass processes. Indeed, according to (1), we have

lim ρ→0 + E exp iλ X(t + ρ) -X(t) ρ H = E exp(iλY (1)) .
Then in view of the first comment and the fact that Y is H-self similar with stationary increments, (H) seems to be natural for the study of local times of lass processes. We refer to [START_REF] Benassi | Elliptic Gaussian random processes[END_REF] for a use of (H) for computing the Hausdorff dimension of the graph of lass processes.

The second assumption characterizes the dependence among the finite-dimensional increments of X :

Assumption (H m ) : There exist m ≥ 2 and positive constants δ and c, both may depend on m, such that for all t 1 , ..., t m with 0 := t 0 < t 1 < t 2 < ... < t m ≤ T, and |t m -t 1 | ≤ δ, we have

E exp i m j=1 u j [X(t j ) -X(t j-1 )] ≤ m j=1 E exp (icu j [X(t j ) -X(t j-1 )]) , for all u 1 , ..., u m ∈ R. Comments 2.
1. If X has independent increments, then (H m ) holds for all m ≥ 2 trivially. When (H m ) holds for all m ≥ 2, we say that X has characteristic function locally approximately independent increments (see [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF], Definition 2.5). This concept is called in the literature the local nondeterminism (LND), and classical examples of LND processes are the fractional Brownian motion (fBm) and the linear fractional stable motion (LFSM) (see [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF]). 3. According to Lemma 2.1 in Berman [START_REF] Berman | Self-intersections and local nondeterminism of Gaussian processes[END_REF], a sufficient condition for (H m ) to hold for a centered Gaussian process is as follows: There exists m ≥ 2 such that

lim ε→0 sup 0≤tm-t 1 <ε max i =j |Cov [X(t i ) -X(t i-1 ), X(t j ) -X(t j-1 )] | V ar[X(t i ) -X(t i-1 )]V ar[X(t j ) -X(t j-1 )] < 1 m -1 .
For m = 2, corresponding to (H 2 ), the preceding condition becomes

lim ε 0 sup 0<t-s≤ε |Cov[X(t) -X(s), X(s)]| V ar[X(t) -X(s)]V ar[X(s)] < 1.
According to Theorem 3.1 in [START_REF] Berman | Local nondeterminism and local times of Gaussian processes[END_REF], this is the necessary and sufficient condition for a Gaussian Markov process to be LND.

We end this section by recalling the notion of approximate moduli of continuity. First, t is said to be a point of dispersion (resp. a point of density) for a bounded Lebesgue measurable set F if

lim ε→0 λ{F ∩ (t -ε, t + ε)} ε = 0, ( resp. = 1)
where λ denotes Lebesgue measure. The approximate lim sup of a function f (s) for s → t is at least y if t is not a point of dispersion for the set {s : f (s) ≥ y}. We refer to Geman and Horowitz ( [START_REF] Geman | Occupation densities[END_REF], Appendix page 22) for details and to Example 1 in the same reference for geometric interpretation. We note that

-∞ ≤ lim inf s→t f (s) ≤ ap -lim sup s→t f (s) ≤ lim sup s→t f (s) ≤ +∞ (2)
We will use C, C 1 , ... to denote unspecified positive finite constants which may not necessarily be the same at each occurrence.

Continuity in time and applications

Our first result in this section is the following Theorem 3.1. Suppose that {X(t), t ∈ [0, T ]} satisfies (H). Then, almost surely i) X has a local time L(t, x), continuous in t for a.e. x ∈ R and L(t, .) ∈ L 2 (dx × P).

ii)

ap -lim sup

s→t |X(t) -X(s)| |t -s| 1+H φ(|t -s|) = +∞ for all t ∈ [0, T ],
where φ(r), r ≥ 0 is any right-continuous function decreasing to 0 as r 0.

Remark 3.1. It's straightforward from (i) of the previous theorem and Theorem A of Geman [START_REF] Geman | A note on the continuity of local times[END_REF] that, with probability one,

ap -lim s→t |X(t) -X(s)| |t -s| = +∞, for a.e. t ∈ [0, T ].
The following is an immediate consequence of Theorem 3.1.

Corollary 3.2. With probability one, X(., w) is nowhere Hölder continuous of any order greater than 1 + H.

Proof of Theorem 3.1. Let I be an interval of length smaller than ρ 0 . For all s, t ∈ I, we have

P (|X(t) -X(s)| ≤ ε) = P |X(t) -X(s)| |t -s| H ≤ ε |t -s| H = 1 2π ε/|t-s| H -ε/|t-s| H R E exp iλ X(t) -X(s) |t -s| H exp (-iλx) dλdx ≤ ε π|t -s| H R ψ(λ)dλ
Then,

I I sup ε>0 1 ε P (|X(t) -X(s)| ≤ ε) dsdt ≤ 1 π R ψ(λ)dλ I I 1 |t -s| H dsdt < +∞, (3)
since 0 < H < 1. Therefore, by using Theorem 21.15 in [START_REF] Geman | Occupation densities[END_REF], L(t, x) exists and it belongs to L 2 (dx × P). Furthermore, (3) implies that

I sup ε>0 1 ε P (|X(t) -X(s)| ≤ ε) ds < +∞, for a.e. t ∈ I.
Then, according to Theorem B in Geman [START_REF] Geman | A note on the continuity of local times[END_REF], the result of the theorem holds for any interval in [0, T ] of length smaller than ρ 0 . Moreover, since [0, T ] is a finite interval, we can obtain the local time on [0, T ] by a standard patch-up procedure, i.e. we partition

[0, T ] into ∪ n i=1 [T i-1 , T i ] and define L([0, T ], x) = n i=1 L([T i-1 , T i ],
x), where T 0 = 0 and T n = T .

The proof of (ii) will be an application of Theorem 1 of [START_REF] Berman | The modulator of the local time[END_REF] to the sample paths of X. Hence, we shall estimate the so called modulator of local time defined as follows

M (t) = 2 2 n j=1 R L 2 j -1 2 n , j 2 n , x dx 1/2 , (4)
whenever

2 -n-1 ≤ t ≤ 2 -n . Now, consider [α, β] ⊂ [0, T ] with β -α < ρ 0 .
It follows from the occupation density formula and Parseval equation that

E R L 2 ([α, β], x)dx = E R L([α, β], x) L([α, β], x)dx = β α β α R E exp (iu(X(t) -X(s))) dudtds. (5)
Combining the change of variable v = (t -s) H u and (H), we obtain that ( 5) is smaller than

β α t α 1 (t -s) H dsdt R ψ(x)dx ≤ C(β -α) 2-H . (6)
Therefore,

EM 2 (2 -n ) ≤ C(2 -n ) 1-H . (7)
Consequently

lim inf n→+∞ 2 n EM 2 (2 -n ) 1/2 (2 -n ) 1+H φ(2 -n ) 1/2 ≤ C lim inf n→+∞ (2 n ) 1+(1-(2-H))/2-(1+H)/2 φ 1/2 (2 -n ) = 0.
Since, by Lemma 2.1 in [START_REF] Berman | The modulator of the local time[END_REF], the modulator is increasing in t, then

lim inf t→0 t -1 EM 2 (t) 1/2 t 1+H φ(t) 1/2 = 0.
Therefore, (1.6) in Theorem 1 of Berman [START_REF] Berman | The modulator of the local time[END_REF] holds for almost all sample functions. This completes the proof of (ii) .

We can get a better result for the prescribed local regularity, at a fixed point t, as follows

Proposition 3.3. If {X(t), t ∈ [0, T ]} satisfies (H), then for every t ∈ [0, T ], the process X is a J H (t) (Jarnik) function on t; i.e. ap -lim sup s→t |X(t) -X(s)| |t -s| H φ(|t -s|) = +∞, almost surely
where φ(r), r ≥ 0 is any right-continuous function decreasing to 0 as r 0.

Now for the pointwise Hölder exponent of a stochastic process X at t 0 , defined by

α X (t 0 , ω) = sup α > 0, lim ρ→0 X(t 0 + ρ, ω) -X(t 0 , ω) ρ α = 0 , (8)
the result of the previous proposition implies Corollary 3.4. The pointwise Hölder exponent of X at any point t is almost surely smaller or equal to H.

Remark 3.2. Proposition 3.3 in [START_REF] Benassi | Identification and properties of real harmonizable fractional Lévy motions[END_REF] gives an analogous result for lass processes with exponent H.

We need the following modification of Lemma 2.2 in Berman [START_REF] Berman | Local nondeterminism and local times of general stochastic processes[END_REF] for the proof.

Lemma 3.1. Let f (t), 0 ≤ t ≤ T be a deterministic real valued measurable function which has a local time L(t, x) and let δ(s), s > 0, be a positive nondecreasing function such that for every

0 ≤ t ≤ T lim inf s→0 (δ(s)) 1/2 s R L 2 ([t -s, t + s], x)dx 1/2 = 0. (9)
Then ap -lim sup

s→t |f (t) -f (s)| δ(|t -s|) = +∞. (10)
Proof. According to Lemma 2.1 in [START_REF] Berman | Local nondeterminism and local times of general stochastic processes[END_REF], for arbitrary M > 0, 0 ≤ t ≤ T , and s > 0, we have

(2s) -1 λ{t : |t -t | ≤ s, |f (t ) -f (t)| < M δ(|t -t |)} ≤ (2M δ(s)) 1/2 2s R L 2 ([t -s, t + s], x)dx 1/2 . (11)
By ( 9), the right hand side of [START_REF] Berman | The modulator of the local time[END_REF] has lim inf equal to zero. Hence, t is not a density point for the set,

s : |f (t) -f (s)| δ(|t -s|) < M .
Therefore, it is not a dispersion point for the complementary set,

s : |f (t) -f (s)| δ(|t -s|) ≥ M .
Consequently the approximate limsup of the ratio is at least equal to M. Since M is arbitrary, the conclusion follows.

Proof of Proposition 3.3. It suffices to show that for every 0 ≤ t ≤ T , the assumption (9) holds almost surely for δ(s) = s H φ(s). This holds if the random variable

Λ(s) = (δ(s)) 1/2 s R L 2 ([t -s, t + s], x)dx 1/2
converges to 0 in probability as s tends to 0. Moreover, using Markov's inequality, we have for arbitrary ε > 0

P (Λ(s) > ε) ≤ s H φ(s)s -2 ε -2 E R L 2 ([t -s, t + s], x)dx ≤ Cs H φ(s)s -2 ε -2 (2s) 2-H ,
where the last inequality follows from ( 5) and ( 6). The last term is equal to 2 2-H Cε -2 φ(s), which tends to zero as s tends to 0 by the assumption on φ. This completes the proof.

Hausdorff measure and dimension

Firstly, we recall the definition of the φ-Hausdorff measure and dimension. Let Φ be the class of functions φ : (0, 1) → (0, 1) which are right continuous and increasing with φ(0

+ ) = 0. The φ-Hausdorff measure H φ (A) of a Borel subset A of R is defined by H φ (A) = lim inf ε 0 ∞ n=1 φ(|I n |) : {I n } n∈N is a countable cover of A by compact intervals with length |I n | ≤ ε .
And the Hausdorff dimension of A is defined by

dim A = inf{α / H φ (A) = 0, φ(r) = r α } = sup{α / H φ (A) = +∞, φ(r) = r α }. Theorem 4.1. Suppose that {X(t), t ∈ [0, T ]} satisfies (H), and let Z t = {s ∈ [0, T ]/X(s) = X(t)} be the progressive level set. Consider the measure function φ(r) = r (1-H)/2 | log(r)| θ , θ > 1/2. Then P H φ (Z t ) = +∞ for a.e. t = 1. (12)
Furthermore, if (H 2 ) holds and if, for any β < H, X satisfies a uniform Hölder condition of order β almost surely, then for almost every t ≥ 0

P(dim Z t = 1 -H) = 1. ( 13
)
Remark 4.1. Benassi et al. [START_REF] Benassi | Elliptic Gaussian random processes[END_REF] have computed the Hausdorff dimension of the graph of lass processes under similar assumptions.

Proof. The inequality [START_REF] Berman | Gaussian processes with stationary increments: local times and sample function properties[END_REF] implies

∞ n=1 EM 2 (2 -n ) [φ(2 -n )] 2 ≤ C ∞ n=1 (2 -n ) 1-H (2 -n ) 1-H n 2θ < +∞.
Then, according to Theorem 2 and (4.6) in Berman [START_REF] Berman | The modulator of the local time[END_REF], [START_REF] Berman | Self-intersections and local nondeterminism of Gaussian processes[END_REF] is proved. We prove [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF] in two steps, by finding upper and lower bounds which appear to be identical. Upper bound : We first prove that for almost every t

dim Z t ≤ 1 -H, almost surely. ( 14
)
For any t ∈ [0, T ], consider t 0 ∈ [0, T ] such that 0 < |t -t 0 | < ρ 0 . Then, according (H 2 ), we have R Ee ixX(t) dx ≤ R Ee ixX(t 0 ) Ee ix(X(t)-X(t 0 )) dx, ≤ R ψ(x)dx × 1 |t -t 0 | H .
It follows that X(t) has a bounded continuous density function p t (y). Furthermore, for any t, take t 0 = t(1 -T ρ 0 (T + ρ 0 ) 2 ), hence t 0 ∈ [0, T ], with |t -t 0 | < ρ 0 and by the inverse Fourier transform we get

P (|X(t) -x| ≤ u) ≤ C π (T + ρ 0 ) 2H u (T ρ 0 ) H × 1 t H (15)
Even though the processes considered in this paper are not necessarily Gaussian, the main ingredients needed to prove [START_REF] Boufoussi | Sample path properties of the local time of multifractional Brownian motion[END_REF] are the existence of a continuous density, the inequality (15) and the Hölder continuity of X. The proof follows now the same lines as the first part of the proof of Theorem 2.1 in Berman [START_REF] Berman | Gaussian processes with stationary increments: local times and sample function properties[END_REF]. We omit the details here.

Lower bound : Let us first recall the following property of the Hausdorff dimension: For any countable sequence of sets E 1 , E 2 , .... we have

dim ∞ i=1 E i = sup i≥1 dim E i . (16)
Now since R + is a countable union of finite intervals, it suffices to prove the result for any I of small length. Let us prove that for any |I| < ρ 0 , we have

dim{s ∈ I/X(s) = X(t)} ≥ 1 -H
We adapt the argument of Berman [START_REF] Berman | Gaussian processes with stationary increments: local times and sample function properties[END_REF]. Using Parseval's identity, we obtain

H(s, t) := R L(t, x)L(s, x)dx, = R t 0 s 0 exp (iu(X(t ) -X(s ))) ds dt du.
Furthermore, from a standard approximation, we have for any Borel function g(s, t)

I I g(s, t)H(ds, dt) = +∞ -∞ I I g(s, t)L(dt, x)L(ds, x)dx. (17)
Then by Fubini's theorem, for every 0 < γ < 1 -H, we have

E I I 1 |t -s| γ H(ds, dt) = R I I 1 |t -s| γ E exp (iu(X(t) -X(s))) dsdtdu ≤ R ψ(u)du I I 1 |t -s| H+γ dsdt, (18)
where we have used the assumption (H) to obtain the last inequality. Since 0 < γ < 1-H, the second integral in ( 18) is finite. Then by Fubini's theorem and ( 17) we have

I I 1 |t -s| γ L(ds, x)L(dt, x) < ∞,
for almost all x ∈ R, almost surely. This implies that

I I 1 |u -v| γ L(du, X(t))L(dv, X(t)) < ∞, for almost all t ∈ I almost surely. ( 19
)
According to Theorem 6.3 in Geman and Horwitz [START_REF] Geman | Occupation densities[END_REF], the measure L(., X(t)) is a positive measure on I for almost all t ∈ I, almost surely. It follows from Lemma 1.5 in Berman [START_REF] Berman | Gaussian processes with stationary increments: local times and sample function properties[END_REF] that the random measure L(., X(t)) is supported on Z t . Moreover Z t is closed, since X is continuous almost surely. Hence, combining Frostman's theorem (see e.g. Adler [START_REF] Adler | The Geometry of Random Fields[END_REF] page 196) and ( 19), we have almost surely dim Z t ≥ 1 -H for almost all t ∈ I.

Joint continuity of local times

Now, we turn to the problem of studying the existence of jointly continuous local times. Throughout this section, we assume the supplementary integrability condition [START_REF] Geman | Occupation densities[END_REF] which is verified for a wide class of stochastic processes including Gaussian and stable processes.

Theorem 5.1. Let {X(t), t ∈ [0, T ]}, be a stochastic process starting from zero and satisfying assumptions (H) and (H m ) for all m ≥ 2, where ψ satisfies

|u|≥1 |u| 1-H H ψ(u)du < ∞. ( 20
)
Then X has a jointly continuous local time L(t, x), such that for any compact K ⊂ R and any interval I with length less than ρ 0 [the constant appearing in the assumption (H)],

we have

(i) If 0 < ξ < 1 ∧ 1-H 2H , then |L(I, x) -L(I, y)| ≤ η|x -y| ξ , for all x, y ∈ K (ii) If 0 < δ < 1 -H, then sup x∈K L(I, x) ≤ η|I| δ ,
where η is a random variable, almost surely positive and finite.

Proof. It is well known that proving the joint continuity of the local times and the Hölder conditions (i) and (ii) is straightforward, when estimating the moments of local times. According to Geman and Horowitz [START_REF] Geman | Occupation densities[END_REF], equation (25.5) and (25.7), the following expressions for the moments of local times hold : for any x, y ∈ R, t, t + h ∈ [0, T ] and any m ≥ 2,

E [L(t + h, x) -L(t, x)] m = 1 (2π) m [t,t+h] m R m e -ix P m j=1 u j E e i P m j=1 u j X(t j ) du 1 ...du m dt 1 ...dt m , (21)
and for any even integer m ≥ 2,

E [L(t + h, y) -L(t, y) -L(t + h, x) + L(t, x)] m = 1 (2π) m [t,t+h] m R m m j=1 e -iyu j -e -ixu j E e i P m j=1 u j X(t j ) du 1 ...du m dt 1 ...dt m . ( 22
)
We estimate only [START_REF] Guerbaz | Hölder conditions for the local times of multiscale fractional Brownian motion[END_REF], since ( 21) is treated in a same manner. By using the elementary inequality |1 -e iθ | ≤ 2 1-ξ |θ| ξ for all 0 < ξ < 1 and any θ ∈ R, we obtain

E [L(t + h, y) -L(t, y) -L(t + h, x) + L(t, x)] m (23)
≤ |y -x| mξ π -m [t,t+h] m R m m j=1 |u j | ξ E exp i m j=1 u j X(t j ) du 1 ...du m dt 1 ...dt m .
Furthermore, in order to use (H m ), we replace the integration over the domain [t, t + h] by the integration over the subset t < t 1 < ... < t m < t + h. We deal now with the inner multiple integral over the u's. Change the variables of integration by means of the transformation

u j = v j -v j+1 , j = 1, ..., m -1; u m = v m .
Then the linear combination in the exponent in ( 23) is transformed according to

m j=1 u j X(t j ) = m j=1 v j (X(t j ) -X(t j-1 )),
where

t 0 = 0. Since |a -b| ξ ≤ |a| ξ + |b| ξ , for all 0 < ξ < 1, it follows that m j=1 |u j | ξ = m-1 j=1 |v j -v j+1 | ξ |v m | ξ ≤ m-1 j=1 (|v j | ξ + |v j+1 | ξ )|v m | ξ . (24)
Moreover, the last product is at most equal to a finite sum of terms each of the form m j=1 |v j | ξε j , where ε j = 0, 1, or 2 and m j=1 ε j = m. Combining (H), (H m ) for all m ≥ 2, and the change of variable v j (t j -t j-1 ) H = θ j , ( 23) becomes

E [L(t + h, y) -L(t, y) -L(t + h, x) + L(t, x)] m (25) ≤ C m m j=1 R |θ j | ξε j ψ(θ j )dθ j |y -x| mξ π -m t<t 1 ...<tm<t+h m j=1 (t j -t j-1 ) -H(1+ξε j ) dt 1 ...dt m .
Furthermore, for |u| ≥ 1, we have |u| ξε j ≤ |u| 2ξ , then

R |u| ξε j ψ(u)du = 1 -1 |u| ξε j ψ(u)du + |u|≥1 |u| ξε j ψ(u)du ≤ 1 -1 ψ(u)du + |u|≥1 |u| 2ξ ψ(u)du.
Combining the fact that ψ belongs to L 1 (R) and ( 20), we obtain that the last integrals are finite. Moreover, by an elementary calculation, for all m ≥ 1, h > 0 and b j < 1,

t<s 1 <...<sm<t+h m j=1 (s j -s j-1 ) -b j ds 1 ...ds m = h m- P m j=1 b j m j=1 Γ(1 -b j ) Γ(1 + m -m j=1 b j )
, where s 0 = t. It follows that ( 25) is dominated by

C m |y -x| mξ |h| m(1-H(1+ξ)) Γ(1 + m(1 -H(1 + ξ)) ,
where we have used m j=1 ε j = m. The rest of the proof follows now the lines of the proofs of Theorems 26.1 and 27.1 of Geman and Horowitz [START_REF] Geman | Occupation densities[END_REF]. Therefore it will be omitted here.

We can now establish the following result on the uniform dimension of the level set which improves [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF] under the assumption (H m ) for all m ≥ 2, Proposition 5.1. Suppose that {X(t), t ∈ [0, T ]} is β-Hölder continuous for any β < H and satisfies the assumptions of the previous theorem. Then, with probability one, for any interval I, we have

dim{t ∈ I/X(t) = x} = 1 -H,
for all x such that L(I, x) > 0.

Proof. The proof of the upper bound appears already in that of [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF], and the proof of the lower bound follows from Theorem 5.1 (ii) and Theorem 8.7.4 in Adler [START_REF] Adler | The Geometry of Random Fields[END_REF].

Regularity of the local time in the space variable

It is known that the Brownian motion local time satisfies a Hölder condition of any order smaller than 1/2, but not of order 1/2. The situation seems to be quite different for a large class of non Markovian Gaussian processes considered in the works of Berman [START_REF] Berman | Harmonic analysis of local times and sample functions of Gaussian processes[END_REF] and Geman and Horowitz [START_REF] Geman | Occupation densities[END_REF], where the authors have given several conditions that imply the higher smoothness of the local time as a function of x. These results have been extended to a wide class of self similar stochastic processes with stationary increments by Kôno and Shieh [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF]. These results extend as follows

Theorem 6.1. Assume that {X(t), t ∈ [0, T ]} satisfies (H) with R |u| 2r ψ(u)du < ∞,
for some nonnegative integer r such that H < 1 2r + 1

. Then, the k-th derivatives,

L (k) (T, x), of L(T, .) exist up to k = r almost surely. Moreover L (k) (T, x) ∈ L 2 (dx × P).
Proof. Let I ⊂ [0, T ] with length at most ρ 0 . Using the change of variables v |t -s| H = u and (H) we obtain

E +∞ -∞ I I |u| 2r exp (iu(X(t) -X(s))) dsdtdu ≤ I I dsdt |t -s| H(2r+1) R |v| 2r |ψ(v)|dv,
which is finite by the assumptions of the theorem. Then, the conclusion follows from the Fourier inversion formula (c.f. Berman [START_REF] Berman | Harmonic analysis of local times and sample functions of Gaussian processes[END_REF]) and by a standard patch-up procedure.

Remark that the function ψ plays in our proof the role of φ(x) = Ee ixX (1) for H-self similar processes with stationary increments in the proof of Theorem 5.1 in [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF]. By using this remark, we can also extend Theorem 5.2 in [START_REF] Kôno | Local times and related sample path properties of certain self-similar processes[END_REF] to Theorem 6.2. Suppose that {X(t), t ∈ [0, T ]} satisfies (H) and (H m ) for some m ≥ 2 and

R |u| 2r+2/m+ε |ψ(u)|du < ∞,
for some nonnegative integer r and some ε > 0 such that H < 1 2r + 2/m + 1 . Then, the local time L(T, x) is of class C r in x. Moreover L (r) (T, x) is Hölder continuous of a certain order.

Examples and extensions

The local time and some related sample paths properties of self similar processes with stationary increments have been studied by Kôno and Shieh [23]. This class is covered by the results of the present paper and now under weaker conditions. We give in the sequel examples of lass processes for which our results hold and we explain how the self-similarity has been relaxed for these processes. We also generalize the results of the previous sections to multifractional processes.

Multifractional Brownian motions

The multifractional Brownian motion was introduced independently by Lévy-Véhel and Peltier [START_REF] Lévy-Véhel | Multifractional Brownian motion : definition and preliminary results[END_REF] and Benassi et al. [START_REF] Benassi | Elliptic Gaussian random processes[END_REF]. The definition due to Lévy-Véhel and Peltier is based on the moving average representation of fBm, where the constant Hurst parameter H is substituted by a functional H(t) as follows :

B(t) = 1 Γ(H(t) + 1/2) 0 -∞ [(t -u) H(t)-1/2 -(-u) H(t)-1/2 ] W (du) + t 0 (t -u) H(t)-1/2 W (du) ; t ≥ 0, (26)
where

H(t) : [0, ∞) -→ [µ, ν] ⊂ (0, 1
) is a Hölder continuous function with exponent β > 0, W is the standard Brownian motion defined on (-∞, +∞). Benassi et al. [START_REF] Benassi | Elliptic Gaussian random processes[END_REF] defined the multifractional Brownian motion by means of the harmonisable representation of fBm as follows :

B(t) = R e itξ -1 |ξ| H(t)+1/2 W (dξ), (27)
where W (ξ) is the Fourier transform of the series representation of white noise with respect to an orthonormal basis of L 2 (R). However, it is proved by Lévy Véhel and Peltier ( [START_REF] Lévy-Véhel | Multifractional Brownian motion : definition and preliminary results[END_REF], Proposition 5) and by Benassi et al. ([6], Theorem 1.7) that if H is β-Hölder continuous and sup t∈R + H(t) < β, the multifractional Brownian motion is lass. That is

lim ρ-→0 + law B(t + ρu) -B(t) ρ H(t) , u ∈ R = law{B H(t) (u), u ∈ R}, (28)
where B H(t) is a fBm with Hurst parameter H(t).

In addition, Boufoussi et al. [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF] have proved that the mBm given by the moving average representation satisfies the assumptions (H) and (H m ) for all m ≥ 2. By using the lass property of the mBm, we give here a proof that both representations of mBm are LND .

Theorem 7.1. If H is β-Hölder continuous and sup t∈R + H(t) < β, then for every ε > 0, and any T > ε, the mBms given by ( 26) and ( 27) are locally nondeterministic on [ε, T ].

Proof. Let us use X to denote the two representations of the mBm. In a same way as in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF], proof of Theorem 3.3, we prove that there exists δ > 0 such that

E(X(t) -X(s)) 2 > 0, whenever 0 < |s -t| < δ; E(X(t)) 2 > 0, for all t ∈ [ε, T ].
It remains to prove that X satisfies assumption (8) in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF]. Fix t > 0, and using Lemma 3.1 in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF], we obtain

V ar(X(s) -X(t)) ≤ C H(t) |s -t| 2H(t) , ∀ s ∈ [0, T ] Consequently, lim δ→0 V ar (Y t,δ (u m )/X(t), Y t,δ (u 1 ), ...., Y t,δ (u m-1 )) = V ar B H(t) (u m )/B H(t) (t), B H(t) (u 1 ), ..., B H(t) (u m-1 ) ≥ C H(t) [(u m -u m-1 ) ∧ (t -u m )] 2H(t) ,
where the last inequality follows from Lemma 7.1 in Pitt [START_REF] Pitt | Local times for Gaussian vector fields[END_REF]. The last term is strictly positive since 0 < u 1 < u 2 < ... < u m < t.

Mixed Gaussian processes

Let {W (t), t ∈ [0, T ]} be a standard Brownian motion and {B H (t), t ∈ [0, T ]} an independent fractional Brownian motion. Cheridito [START_REF] Cheridito | Mixed fractional Brownian motion[END_REF] has introduced the mixed fBm defined by Y = {W (t) + B H (t), t ∈ [0, T ]} in order to model stock prices with long range dependence.

Since W and B H are independent and both have smooth local time, it will be easy to see that Y has smooth local time. Moreover the moduli of continuity are obtained in terms of (H ∧

). We omit the details.

In the sequel we consider {X 1 (t), t ∈ [0, 1]} and {X 2 (t), t ∈ [0, 1]} two mean zero Gaussian processes, where X 1 is LND and X 2 , not necessarily independent of X 1 , but only negligible in the sense that

E (X 2 (t) -X 2 (s)) 2 = o E [X 1 (t) -X 1 (s)] 2 , as t → s. (30)
Then, we prove that Lemma 7.1. The sum process X = X 1 + X 2 is LND on any interval J ⊂ [0, 1] of small length.

Proof. The idea of the proof is inspired from that used in Guerbaz [START_REF] Guerbaz | Local time and related sample paths of filtered white noises[END_REF] to prove that the filtered white noise is LND. We present it here for the sake of completeness.

By using the elementary inequality

(x + y) 2 ≥ x 2 2 -y 2 we obtain V ar m j=1 u j [X(t j ) -X(t j-1 )] ≥ 1 2 V ar m j=1 u j [X 1 (t j ) -X 1 (t j-1 )] -V ar m j=1 u j [X 2 (t j ) -X 2 (t j-1 )] .
Furthermore, since X 1 is LND, there exist δ m and C m such that for any

t 0 = 0 < t 1 < ... < t m < 1, with t m -t 1 < δ m , we have V ar( m j=1 u j [X(t j ) -X(t j-1 )]) (31)
≥ C m 2 m j=1 u 2 j V ar(X 1 (t j ) -X 1 (t j-1 )) -m m j=1 u 2 j V ar(X 2 (t j ) -X 2 (t j-1 ))
Moreover, according to (30), for 0 < ε m < Cm 2m , there exists δ m such that

V ar(X 2 (t j ) -X 2 (t j-1 )) V ar(X 1 (t j ) -X 1 (t j-1 )) ≤ ε m , for all t j -t j-1 ≤ δ m . Therefore V ar( m j=1 u j [X(t j ) -X(t j-1 )]) ≥ C m 2 -mε m m j=1 u 2 j V ar(X 1 (t j ) -X 1 (t j-1 ))
Furthermore, (30) implies that there exists a constant C > 0 such that V ar(X 1 (t j ) -X 1 (t j-1 )) ≥ CV ar(X(t j ) -X(t j-1 ))

Therefore, it suffices now to choose

δ m < δ m ∧ δ m ,
and to consider

C m = C m 2 -mε m ,
and the lemma is proved.

Multifractional Gaussian processes

The multifractional Gaussian process (MGP) has been introduced in [START_REF] Benassi | Identifying the multifractional function of a Gaussian process[END_REF] as follows :

X(t) = R a(t, λ)(e itλ -1) |λ| 1/2+H(t) W (dλ)
where W (dλ) is the random Brownian measure on L 2 (R).

When H is constant, this process is a Filtered White Noise ( [START_REF] Benassi | Identification of filtered white noises[END_REF], in short FWN). Moreover, if a(t, λ) = 1, a MGP is a mBm.

Assume that a(t, λ) is C 2 (R 2 ; R), and that there exists a function a ∞ (t) = 0 such that lim |λ|→∞ a(t, λ) = a ∞ (t) and that σ(t, λ) = a(t, λ) -a ∞ (t) satisfies :

∂ i+j σ(t, λ) ∂ i t∂ j λ ≤ C |λ| j+η , (32)
for i, j = 0, 1, 2 and η > 0 such that 0 < H + η < 1.

The particular case of FWN has been studied in Guerbaz [START_REF] Guerbaz | Local time and related sample paths of filtered white noises[END_REF]. We now prove that the MGP satisfies the assumptions (H) and (H m ) for all m ≥ 2. The assumption (H) may be deduced from Proposition 1 in [START_REF] Benassi | Identifying the multifractional function of a Gaussian process[END_REF]. To prove that X is LND, we first write

X(t) = a ∞ (t) B(t) + R σ(t, λ)(e itλ -1) |λ| 1/2+H(t) W (dλ),
where B is the mBm given by [START_REF] Stoev | Path properties of the linear multifractional stable motion[END_REF]. Since a ∞ (t) belongs to C 2 (R) and Theorem 7.1 implies that B is LND, we conclude easily that the Gaussian process X 1 (t) = a ∞ (t) B(t) is LND. Moreover, by using (32), we obtain that the process

X 2 (t) = R σ(t, λ)(e itλ -1) |λ| 1/2+H(t) dW (λ), satisfies E (X 2 (t) -X 2 (s)) 2 = o E (X 1 (t) -X 1 (s)) 2 , as t → s.
Then Lemma 7.1 achieves the proof.

Sub-Gaussian processes

Let X = {X(t), t ∈ [0, T ]} be a Gaussian process and let Z a nonnegative α/2-stable random variable, where 1 < α < 2, i.e., for λ > 0, E exp(-λZ) = exp(-λ α/2 ).

Assume that the random variable Z is independent of X. The α-stable process Y = {Y (t) = Z 1/2 X(t), t ∈ [0, T ]} is called a sub-Gaussian process with underlying Gaussian process X. We have the following result Proposition 7.2.

1. If V ar(X(t) -X(s)) ≥ C|t -s| 2H for some 0 < H < 1, C > 0 and t, s sufficiently close. Then Y satisfies the assumption (H).

2. If X satisfies (H m ) for some m ≥ 1, then Y satisfies the same.

Proof. 1. Since X is a centered Gaussian process

E exp iλ Y (t) -Y (s) |t -s| H = E E exp iZ 1/2 λ X(t) -X(s) |t -s| H /Z = E exp -Z λ 2 2 V ar(X(t) -X(s)) |t -s| 2H .
And since Z is α/2-stable random variable, then the last expression becomes

exp -|λ| α V ar(X(t) -X(s)) α/2 2 α/2 |t -s| αH .
Finally, the assumption on X in the first point implies that the last expression is dominated by

ψ(λ) = exp - C α/2 2 α/2 |λ| α ,
which belongs to L 1 (R). Consequently, Y satisfies the assumption (H).

2. Assume that X satisfies (H m ) for some m ≥ 2. Then, there exist two positive constants c m and δ m , such that for all 0 = t 0 < t 1 < t 2 < ... < t m ≤ T , with |t m -t 1 | ≤ δ m , we have

E exp i m j=1 u j [X(t j ) -X(t j-1 )] ≤ m j=1 E exp (ic m u j [X(t j ) -X(t j-1 )]) ,
for all u 1 , ....., u m ∈ R. Since X is a Gaussian process, the previous expression reads

exp - 1 2 V ar m j=1 u j [X(t j ) -X(t j-1 )] ≤ exp - 1 2 c m m j=1 u 2 j V ar[X(t j ) -X(t j-1 )]
Moreover, using the fact that the function u α/2 is concave for 0 < α < 2, and conditioning in the same manner as above we obtain

E exp i m j=1 u j [Y (t j ) -Y (t j-1 )] = exp   - 1 2 α/2 V ar m j=1 u j [X(t j ) -X(t j-1 )] α/2   ≤ exp - 1 2 α/2 c α/2 m m 1-α/2 m j=1 u α j (V ar[X(t j ) -X(t j-1 )]) α/2 = m j=1 E exp [iC m u j (Y (t j ) -Y (t j-1 ))] ,
where

C m = √ cm m 1-α 2α
.

Linear multifractional stable processes

The linear multifractional stable process (LMSP) is defined by the stochastic integral

Ψ α H(t) (t) = R a (t -u) H(t)-1/α + -(-u) H(t)-1/α + + b (t -u) H(t)-1/α - -(-u) H(t)-1/α - M α,β (du); t ∈ R, (33)
where M α,β (du) is a (strictly) α-stable, independently scattered random measure with control measure ds, and skewness intensity β(.) ∈ [-1, 1], u ∈ R. This process was introduced by Stoev and Taqqu in [START_REF] Stoev | Path properties of the linear multifractional stable motion[END_REF] as a natural generalization of the linear fractional stable process to the case where the self-similarity parameter H is no more constant, but a regular function of time.

According to Stoev and Taqqu ([28]), Theorem 5.1), the LMSP is a lass process. Its tangent process at each t 0 is a linear fractional stable process with parameter H(t 0 ).

We are interested in this paragraph in deriving sufficient conditions for the existence and the regularity of the local time of LMSP. We restrict ourselves for simplicity to the case a = 1 and b = β(.) = 0; i.e. we consider the process

Ψ α H(t) (t) = R (t -u) H(t)-1/α + -(-u) H(t)-1/α + dZ α (u), t ≥ 0, (34)
where Z α is a Lévy α-stable motion. Boufoussi et al. [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF] have investigated the case α = 2, corresponding the mBm, i.e., M α,β is the random Brownian measure on L 2 (R). The authors have assumed H to be κ-Hölder continuous with sup t∈R + H(t) < κ. This condition was needed to prove some estimates which imply the existence and the regularity of the local time of mBm. We extend their results here to the LMSP under weaker conditions. We can now prove the following existence result Proof. The first part will be proved if we show that the LMSP satisfies (H). On the other hand, denoting by span(Ψ α H(u) (u), u ≤ s) the subspace spanned by (Ψ α H(u) (u), u ≤ s) and with the notation of [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF], we have for any 0

≤ s ≤ t such that |t -s| < 1, Ψ α H(t) (t) -Ψ α H(s) (s) α α ≥ Ψ α H(t) (t) -Ψ α H(s) (s) -span(Ψ α H(u) (u), u ≤ s) α α = Ψ α H(t) (t) -span(Ψ α H(u) (u), u ≤ s) α α = t s (t -u) α(H(t)-1/α) du = 1 αH(t) (t -s) α(H(t)-1/α)+1 = 1 αH(t) (t -s) αH(t) (35) ≥ 1 αµ (t -s) αµ , (36)
where µ = sup t∈R + H(t). Therefore,

E exp   iu Ψ α H(t) (t) -Ψ α H(s) (s) |t -s| µ   = exp -|u| α Ψ α H(t) (t) -Ψ α H(s) (s) α α |t -s| αµ ≤ exp - |u| α αµ ,
which belongs to L 1 (R). Then, the LMSP satisfies (H), and the first part is proved. Let's now prove the second point : Let According to Theorem 2.6 in [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF], proving that the LMSP satisfies (H m ) is equivalent to prove that Proposition 7.4. The LMSP is locally nondeterministic on every interval [ , T ], for any 0 < < T < ∞.

Proof. To prove the LND for the LMSP we shall verify assumptions (a), (b) and (c) of Definition 2.4 in [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF]. First, let us denote for simplicity K(t, u) = (t -u)

H(t)-1/α + -(-u) H(t)-1/α + .
Since K(t, u) α = t H(t) K(1, u) α , then (a) holds away from the origin. The second condition in Definition 2.4 in [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF] follows from (4.11) in [START_REF] Stoev | Path properties of the linear multifractional stable motion[END_REF]. It remains to show that the LMSP satisfies the last assumption, i.e. Proof. The proof follows the same lines as in ([13], Theorem 3.5), but here we use LND in the sense of Nolan [START_REF] Nolan | Local nondeterminism and local times for stable processes[END_REF] instead of Berman [START_REF] Berman | Local nondeterminism and local times of Gaussian processes[END_REF].

lim
H(t), (45)
with positive probability.

Proof. We omit the proof which uses a chaining argument similar to that of Theorem 4.2 in [START_REF] Boufoussi | On the local time of multifractional Brownian motion[END_REF].

  [a, b] be an interval with small length. Since the local time exists on the interval [a, b], then according to Geman and Horowitz [[20], Theorem 21.9 ] the following holds R

Theorem 7 . 6 .

 76 Assume 1 ≤ α < 2 and H is ρ-Hölder continuous with 1/α ≤ H(t) < ρ for all t ≥ 0. Then, for any interval [a, b] ⊂ R + and every u ∈ R, the linear multifractional stable process Ψ α H satisfies dim{t ∈ [a, b], Ψ α H (t) = u} = 1 -min [a,b]

2 .

 2 Observe that the assumption (H m ) is decreasing in m in the sense that if (H m ) is satisfied then (H m-1 ) holds. Hence, (H 2 ) is the minimal condition. We need sometimes only (H 2 ), nevertheless we give in Section 7 examples of processes satisfying (H m ) for all m ≥ 2.

  Theorem 7.3. The LMSP {Ψ α H(t) (t), t ∈ [0, T ]} has almost surely a local time L(t, x), continuous with respect to time and such that L(T, .) ∈ L 2 (dx × P). Conversely, assume that H is continuous and denote by α H its pointwise Hölder exponent, then if H(t) ≤ α H (t), the existence of square integrable local time on small intervals implies that 0 < H(t) < 1 almost everywhere.

  (t) -Ψ α H(s) (s)] = exp -|θ| α Ψ α H(t) (t) -Ψ α H(s) (s) α αOn the other hand, by Theorem 2.1 in[START_REF] Stoev | Path properties of the linear multifractional stable motion[END_REF], for all 1 ≤ α < 2 we haveΨ α H(t) (t) -Ψ α H(s) (s) α α ≤ C α |t -s| αH(t) + |H(t) -H(s)| α . (38)Since H(t) ≤ α H (t), then for all t, s close, the expression (38) becomesHence H(t) < 1 for almost every t ∈ [a, b]. Since R is a countable union of small intervals, the result is proved.

	Moreover
	E exp iθ[Ψ α H(t) Ψ α H(t) (t) -Ψ α H(s) (s) α α ≤ C α,H |t -s| αH(t) .	(39)
	Combining (37) and (39) we obtain that
	b	b
		|t -s| -H(t) dsdt < ∞.
	a	a
			(37)

E exp iθ[Ψ α H(t) (t) -Ψ α H(s) (s)] dsdtdθ < ∞.

  inf -t m-1 ) αH(tm) ,(41)where we have used (35) to obtain the last inequality. Combining (38) and (41), we obtain that the ratio in (40) is at least equal toC α,H(tm) (t m -t m-1 ) αH(tm) |t m -t m-1 | αH(tm) + |H(t m ) -H(t m-1 )| α = C α,H(tm) 1 + |H(t m ) -H(t m-1 )| (t m -t m-1 ) H(tm) -s)H(t) = 0. Then (40) holds and Ψ α H is LND. Our main result in this paragraph reads Theorem 7.5. Assume 1 ≤ α < 2 and H is continuous with H(t) < α H (t). Then, the LMSP Ψ α H has jointly continuous local times L(t, x). It satisfies for any compact U ⊂ R (i) where γ < 1 -H(t) and |h| < η, η being a small random variable almost surely positive and finite, (ii) for any I ⊂ [0, T ],

	|H(t) -H(s)| (t sup Since H(t) ≤ α H (t), lim t-s→0 x∈U |L(t + h, x) -L(t, x)| |h| γ	< +∞ a.s.,	(43)
				sup x,y∈U,x =y	|L(I, x) -L(I, y)| |x -y| ζ	< +∞ a.s.,	(44)
							
	where ζ <		1 2 sup H(t)	-	1 2	 ∧ 1.
			I
		c 0 + 0<tm-t 1 ≤c	Ψ α H(tm) (t α	> 0.	(40)
	Since
				Ψ α H(tm) (t α
				≥	1 αµ	(t m α -1
							.	(42)

m ) -span(Ψ α H(t i ) (t i ), i = 1, ..., m -1) α α Ψ α H(tm) (t m ) -Ψ α H(t m-1 ) (t m-1 ) α m ) -span(Ψ α H(t i ) (t i ), i = 1, ..., m -1) α α ≥ Ψ α H(tm) (t m ) -span(Ψ α H(u) (u), u ≤ t m-1 ) α

Research supported by the program Volubilis : "Action intégrée MA/ 06/142".

Then, for all points t < t 1 < ... < t m < t + δt, we have V ar(X(t m ) -X(t m-1 )) ≤ 2V ar(X(t m ) -X(t)) + 2V ar(X(t m-1 ) -X(t))

V ar(X(t m )/X(t 1 ), ..., X(t m-1 ))

Moreover, if we add X(t) to the conditional set we obtain

where the last equality follows from the fact that

Let t m -t = u m δ with 0 < u m < t. Therefore, the fraction in (29) becomes

where we denote for simplicity