Rafael Andretto Castrequini
email: rafael.andretto-castrequini@ensta-paristech.fr

Francesco Russo
email: francesco.russo@ensta-paristech.fr

Path dependent equations driven by Hölder processes

Keywords: Young integration, Path-dependent, Differential equations. MSC 2010:60G22, 60H05, 60H22

This paper investigates existence results for path-dependent differential equations driven by a Hölder function where the integrals are understood in the Young sense. The two main results are proved via an application of Schauder theorem and the vector field is allowed to be unbounded. The Hölder function is typically the trajectory of a stochastic process.

Introduction

The aim of the paper is to discuss existence theorems for a path-dependent equation of the type

Y t = y 0 + ˆt 0 F (u, Y u ( )) dX u , t ∈ [0, T ], (1.1)
where X is an α-Hölder continuous n-dimensional process and F is a pathdependent m × n matrix-valued vector field defined on [0, T ] × C([0, T ] ; R m ).

The trajectories of the unknown process Y are R m -valued α-Hölder continuous functions; Y u ( ) denotes the trajectory of Y until time u, i.e, Y u (x) = Y x , if x ≤ u and Y u (x) = Y u otherwise. The integral is intended in the Young sense so that F needs of course to verify a Hölder type regularity, see Sec. 3 for details.

Path-dependent (similarly to functional dependent or delay) equations have a long story. To the best of our knowledge the first author who has contributed in this framework in the stochastic case, is [START_REF] Chojnowska-Michalik | Representation theorem for general stochastic delay equations[END_REF] motivated by [START_REF] Delfour | Controllability, observability and optimal feedback control of affine hereditary differential systems[END_REF], which is a significant contribution in the deterministic case. A relevant monograph in the subject is the one of [START_REF] Mohammed | Stochastic functional differential equations[END_REF]. Considerations about functionaldependent equations in law also appear in [START_REF] Rogers | Diffusions, Markov processes, and martingales[END_REF]. More recently several studies have been performed studying the relation between functional dependent equations and path-dependent PDEs see e.g. [START_REF] Girolami | Infinite dimensional stochastic calculus via regularization and applications[END_REF][START_REF]Clark-Ocone type formula for non-semimartingales with finite quadratic variation[END_REF][START_REF] Flandoli | An infinite-dimensional approach to pathdependent Kolmogorov's equations[END_REF][START_REF] Cosso | Functional Itô versus Banach space stochastic calculus and strict solutions of semilinear path-dependent equations[END_REF] in the framework of Banach space valued stochastic calculus and many others in the framework of path-dependent functional Itô calculus, see [START_REF] Leão | Weak functional Itô calculus and applications[END_REF] and references therein for latest developments.

Young integral was introduced first in [START_REF] Young | An inequality of the Hölder type, connected with stieltjes integration[END_REF]. A recent paper on the subject is [START_REF] Gubinelli | Controlling rough paths[END_REF] and an excellent monograph recalling Young integral in the perspective of rough paths is [START_REF] Friz | A course on rough paths[END_REF]. That integral has been implemented for the study of ordinary stochastic differential equations driven by Hölder processes (see [START_REF] Lyons | Differential equations driven by rough signals. I. An extension of an inequality of L. C. Young[END_REF][START_REF] Lejay | Controlled differential equations as Young integrals: a simple approach[END_REF]) and also SPDEs, see [START_REF] Maslowski | Evolution equations driven by a fractional Brownian motion[END_REF][START_REF] Gubinelli | Young integrals and spdes[END_REF]. As far as we know, the present paper is the first one which discusses functional-dependent equations in the framework of Young integral.

The aim of this paper is to discuss existence results under suitable minimal assumptions on F . Contrarily to most of the literature on Young differential equations even in the non-path dependent setting, the authors allow the vector field F to be unbounded. The main results about existence are Theorem 16 and Theorem 18; the latter supposes F to be bounded but with less restrictive Hölder type conditions on F . The path-dependent framework however offers other perspectives of generalization if one assumes a different type on dependence on the past trajectory. For instance in Section 6 we remark that, whenever the dependence of F with respect to the past allows a gap with respect to the present, the construction of a solution can be done iteratively.

Preliminaries

In this section we introduce some basic definitions.

Let U and V be Banach spaces and denote by L = L (V, U ) the space of continuous linear maps from V to U .

We reserve the symbols X to denote driving paths of our differential equation. Typically X : [0, T ] → V is an α-Hölder continuous. Hence there is a constant (the smallest one is denoted by X α ) such that

|X t -X s | ≤ X α |t -s| α , for all s, t ∈ [0, T ]. As usual we write, X ∈ C α ([0, T ] , V ) and X α = sup s,t∈[0,T ],s =t |X t -X s | |t -s| α .
It is sometimes useful to specify the closed interval I = [t 0 , t 1 ] where we evaluate X α . For this matter, we further define

X α;I := sup s,t∈I,s =t |X t -X s | |t -s| α .
If t 0 ≥ 0 and τ > 0 we will simply denote

X α;t 0 ,τ := X α;[t 0 ,t 0 +τ ] .
Usually we omit the symbol U in C α (I, U ) becoming simply C α (I). It is well-known that α;I induces semi-distance on the vector space C α (I), though we can endow it with a metric by setting |||Z - Since our differential equation involves a vector field acting on the whole trajectory of a path, we make use of the following notation. Given a continuous path Y : [0, T ] → U we denote by the calligraphic version of Y , namely

Y ||| α;I := Z -Y α;I + |Z t 0 -Y t 0 |, for all Z, Y ∈ C α (I).
Y, onto C ([0, T ] , U ), i.e. Y : [0, T ] t → → C ([0, T ] , U ) Yt , with Y t (x) := Y t∧x . (2.1)
We observe that, if Y is α-Hölder continuous then its lift is α-Hölder as well. Indeed, this is shown in the statement below.

Proposition 1. Let Y ∈ C α ([0, T ]). Then, for any 0 ≤ a ≤ b ≤ T , Y ∈ C α ([a, b] , C [0, T ]) we have Y α;[a,b] ≤ Y α;[0,T ] (2.2) Y t ∞;[0,T ] ≤ Y α;[0,T ] . (2.3) Proof. Fix s ≤ t in [a, b]. For any x ∈ [0, T ] we have |Y t (x) -Y s (x)| ≤      |Y x -Y x | , x ∈ [0, s] |Y x -Y s | , x ∈ [s, t] |Y t -Y s | , x ∈ [t, T ] ≤      0 , x ∈ [0, s] Y α |x -s| α , x ∈ [s, t] Y α |t -s| α , x ∈ [t, T ] ≤ Y α |t -s| α , so Y t -Y s ∞;[0,T ] ≤ Y α |t -s| α . This proves Y ∈ C α ([a, b] , C([0, T ])) with Y α;[a,b] ≤ Y α;[0,T ] i.e.

Young integral

At this level we recall the fundamental inequality characterizing Young integral. For a complete treatment we refer the reader [START_REF] Friz | Multidimensional stochastic processes as rough paths: theory and applications[END_REF]Ch. 6]. For a reference closer to our spirit we recommend [9, pp.47-48;63]. We remark that the second inequality below is a consequence of the first one.

Theorem 2. Let t 0 ∈ [0, T ], a ∈ U and let τ > 0 such that τ + t 0 ≤ T . Given W ∈ C γ ([t 0 , t 0 + τ ] , L (V, U )) and X ∈ C α ([0, T ] , V ) with α + γ > 1, the map W → I (W ) := a + ˆ t 0 W u dX u ∈ C α ([0, T ]), (3.1)
is continuous and it satisfies, for s ≤ t in [t 0 , t 0 + τ ],

ˆt s W u dX u -W s (X t -X s ) ≤ k α+γ W γ;[s,t] X α;[s,t] |t -s| α+γ , (3.2)
where k µ = 1 1-2 1-µ . If furthermore τ ≤ 1, we can write the inequality above as

I (W ) α;t 0 ,τ ≤ (k α+γ + 1) X α;t 0 ,τ W γ;t 0 ,τ + |W t 0 | . (3.3)
4 The vector field F

In this section we formally introduce the driving vector field of the equation. For every t ∈ [0, T ] and Y ∈ C([0, T ], U ), F (t, Y ) is a linear map acting on V to U . Also we will present some fundamental inequalities regarding composition maps, such as Y → F (t, Y t ).

Definition 3. Let F : [0, T ] × C ([0, T ] , U ) → L.
We will say that it is non-anticipating if it satisfies

F (t, Y ) = F (t, Y t ) , for all Y ∈ C [0, T ] and t ∈ [0, T ]
The requirement above means that F (t, Y ) does not depend on what happened on Y | [t,T ] . It will indeed fulfill the property below.

Remark 4. Given Y , Ỹ ∈ C [0, T ] such that Y | [0,s] = Ỹ | [0,s] . Then F (s, Y ) = F s, Ỹ .
We assume Hölder regularity on F as follows. The forthcoming examples will play as motivation for the definition below. Definition 5. The vector field F : [0, T ] × C α ([0, T ] , U ) → L will be said (α, β)-Hölder if there are some non-negative constants c α,β and cα,β ,

|F (t, Y ) -F (s, Y )| ≤ c α,β 1 + Y β α,[s,t] |t -s| αβ , ∀s, t ∈ [0, T ], (4.1)
F (s, Y ) -F s, Ỹ ≤ cα,β Y -Ỹ α,[0,s] + Y 0 -Ỹ0 β , ∀s ∈ [0, T ], (4.2)
for all Y, Ỹ ∈ C α ([0, T ] , U ) . Remark 6. 1. If F is (α, β)-Hölder then (4.2) implies that F is non- anticipating. 2. It is well-known that, for α ′ < α, if Y is α-Hölder then Y is α ′ -Hölder.
This follows from the inequality

Y α ′ ;[t 0 ,t 1 ] ≤ Y α;[t 0 ,t 1 ] |t 1 -t 0 | α-α ′ .
This remark motivates the lemma below, which will be useful in the next sections.

Lemma 7. Let 0 < α ′ ≤ α ≤ 1 and β ∈ (0, 1]. Suppose that F : [0, T ] × C α ′ ([0, T ] , U ) → L is an (α ′ , β)-Hölder continuous vector field. Then F is (α, β)-Hölder continuous with constants c α,β := c α ′ ,β T α ′ β ∨ 1 and cα,β := cα ′ ,β T (α-α ′ )β ∨ 1 . Proof. Let s < t belonging to [0, T ] and let Y ∈ C α ([0, T ]). Using the inequality Y α ′ ;[s,t] ≤ Y α;[s,t]
|t -s| α-α ′ and (α ′ , β)-Hölder continuity of F (below we are going to omit the sub-index β related to the constants c α,β , cα,β , c α ′ ,β and cα ′ ,β ), we obtain

|F (t, Y ) -F (s, Y )| ≤ c α ′ 1 + Y β α ′ ;[s,t] |t -s| α ′ β ≤ c α ′ 1 + Y β α;[s,t] |t -s| (α-α ′ )β |t -s| α ′ β = c α ′ |t -s| α ′ β + Y β α;[s,t] |t -s| αβ ≤ c α ′ T α ′ β + Y β α;[s,t] |t -s| αβ ≤ c α ′ T α ′ β ∨ 1 1 + Y β α;[s,t] |t -s| α ′ β , hence equality (4.1) holds with c α = c α ′ T α ′ β ∨ 1 . It remains to show (4.2). Let Y, Ỹ ∈ C α ([0, T ]) and s ∈ [0, T ]. We have F (s, Y ) -F s, Ỹ ≤ cα ′ Y -Ỹ α ′ ,[0,s] + Y 0 -Ỹ0 β ≤ cα ′ Y -Ỹ α,[0,s] s α-α ′ + Y 0 -Ỹ0 β ≤ cα ′ T (α-α ′ )β ∨ 1 Y -Ỹ α,[0,s] + Y 0 -Ỹ0 , which proves the claim with cα = cα ′ T (α-α ′ )β ∨ 1 .
Example 8. B. Dupire (see [START_REF] Dupire | Functional itô calculus[END_REF]) introduced a notion of non-anticipating functional in the sense introduced below. Denote Λ := ∪ s∈[0,T ] Λ s and Λ s := C([0, s]). We endow Λ with the metric d defined as follows. For any Z t , Y s ∈ Λ (the superscript here means that

Z t ∈ Λ t and Y s ∈ Λ s ) assuming s ≤ t, he defines d Z t , Y s := |t -s| + Z t -Y s s ∞;[0,t] ,
where similarly as at (2.1), we set

Y s u (x) := Y s u∧x , u, x ∈ [0, t].
Let f : Λ → R be a β-Hölder continuous functional with respect to d. Then the vector field F defined by

F (t, Y ) := f Y | [0,t] , ∀t ∈ [0, T ], ∀Y ∈ C α ([0, T ]),
is non-anticipating in the sense of Definition 3 and it is (α, β)-Hölder.

Indeed, for Y ∈ C α ([0, T ]), we have

|F (t, Y ) -F (s, Y )| = f Y | [0,t] -f Y | [0,s] ≤ f β d Y | [0,t] , Y | [0,s] β ≤ f α |t -s| + Y -Y s ∞;0,t β = f α |t -s| + sup x∈[s,t] |Y x -Y s | β ≤ f α |t -s| + Y α;[s,t] |t -s| α β ≤ f α T 1-α + Y α;[s,t] β |t -s| αβ .
This proves (4.1). It remains to prove (4.2). Given Y, Z ∈ C α ([0, T ]) and s ∈ [0, T ],

|F (s, Y ) -F (s, Z)| = f Y | [0,s] -f Z| [0,s] ≤ f β |s -s| + Y -Z ∞;[0,s] β ≤ f β 0 + Y -Z α;[0,s] s α + |Y 0 -Z 0 | β . Example 9. Young integral functional. Let α, γ ∈ (0, 1] with α + γ > 1. Fix a function g in C γ ([0, T ]). Define the vector field F g by setting F g (t, Y ) := ´t 0 g u dY u , for each Y ∈ C α ([0, T ]). Then F g is (α, 1)-Hölder continuous. Indeed, using Young integral inequality (3.2) with W (and X) instead of g (and Y ), for any s, t ∈ [0, T ] and Y ∈ C α ([0, T ]), it follows that |F g (t, Y ) -F g (s, Y )| = ˆt s g u dY u ≤ k α+γ g γ;[s,t] Y α;[s,t] |t -s| α+γ + |g s | |Y t -Y s | ≤ k α+γ g γ;[0,T ] T γ + g ∞;[0,T ] Y α;[s,t] |t -s| α ,
which proves (4.1). Now, given any Y, Z ∈ C α ([0, T ]) and s ∈ [0, T ], we apply previous inequality with Y -Z instead of Y and for s = 0. Thus, we obtain

|F g (s, Y ) -F g (s, Z)| = ˆs 0 g u d(Y -Z) u ≤ k α+γ g γ;[0,T ] T γ + g ∞;[0,T ] Y -Z α;[0,s] T α ,
which proves (4.2).

Example 10. Young Integral functional (continued). More generally, we consider the vector field F (t, Y ) := h t, ´t 0 g 1 u dY u , . . . , ´t 0 g N u dY u , where

g i ∈ C γ i ([0, T ]) with α + γ i > 1, 1 ≤ i ≤ N, and h : [0, T ] × R N → R such there is a constant K > 0 with |h (t, b) -h (s, a)| ≤ K |t -s| αβ + max i=1,...,N |b i -a i | β , ∀t ∈ [0, T ], ∀a, b ∈ R N .
Then F is (α, β)-Hölder. Indeed, it is easy to see that F satisfies the inequalities

|F (t, Y ) -F (s, Y )| ≤ K 1 + max i=1,...,N c i Y β α;[s,t] |t -s| αβ , |F (s, Y ) -F (s, Z)| = |F (s, Y -Z)| ≤ K max i=1,...,N c i Y -Z β α;[0,s] T αβ , for any Y, Z ∈ C α and s, t ∈ [0, T ] where c i := k α+γ i g i γ i T γ i + g i ∞ β .
Remark 11. In the proposition below, we will use a simple technique involving Hölder norms inequalities. It is called geometric interpolation (in contrast to the linear one, a ≤ θa + (1θ) b ≤ b) which states that, whenever W ∈ C α and θ ∈ (0, 1), then

W αθ ≤ W 1-θ 0 W θ α , (4.3)
recalling the notation

W 0 = sup s,t |W t -W s |. The proof of (4.3) is a con- sequence of the equality |Wt-Ws| |t-s| αθ = |W t -W s | 1-θ |Wt-Ws| |t-s| α θ
. In particular we get

W αθ ≤ 2 1-θ W 1-θ ∞ W θ α . (4.4) Proposition 12. Let F : [0, T ] × C α ([0, T ] , U ) → L be a non-anticipating and (α, β)-Hölder continuous vector field. Fix t 0 , t 1 ∈ [0, T ]. Given Y, Z ∈ C α ([0, t 1 ] , U ) the inequality F ( , Y ) αβ;[t 0 ,t 1 ] ≤ c α,β 1 + Y β α;[t 0 ,t 1 ] (4.5) holds. Moreover, if Y α;[t 0 ,t 1 ] , Z α;[t 0 ,t 1 ] ≤ R, for any θ ∈ (0, 1), it follows F ( , Y ) -F ( , Z) αβθ;[t 0 ,t 1 ] ≤ 2c 1-θ α,β c θ α;β 1 + R β θ Y -Z α;0,t 1 + Y 0 -Ỹ0 β(1-θ) , (4.6)
where c α,β and cα,β are the constants introduced in Definition 5. Proof. For s < t in [t 0 , t 1 ], and Y ∈ C α ([0, t 1 ]), (4.5) follows directly from the definition of (α, β)-Hölder continuous.

We prove now (4.6). We set

I := [t 0 , t 1 ]. Given Y, Z ∈ C α ([0, t 1 ]) with Y α;I , Z α;I ≤ R, we write W t := F (t, Y ) -F (t, Z), t ∈ I.
Fix an arbitrary θ ∈ (0, 1); using (4.4) we obtain

W αβθ;I ≤ 2 1-θ W 1-θ ∞;I W θ αβ;I , (4.7)
so it remains to bound W ∞;I and W αβ;I . On the one hand, since F is (α, β)-Hölder continuous, we have

W ∞;I = sup t∈[t 0 ,t 1 ] |F (t, Y ) -F (t, Z)| ≤ cα,β Y -Z α,[0,t 1 ] + |Y 0 -Z 0 | β . (4.8)
On the other hand, using (4.5) and recalling Y α;I , Z α;I ≤ R, it follows

W αβ;I ≤ F (t, Y ) αβ;I + F (t, Z) αβ;I ≤ c α,β 1 + Y β α;I + c α,β 1 + Z β α;I ≤ 2c α,β 1 + R β . (4.9)
Finally inequality (4.6) follows substituting (4.8) and (4.9) into (4.7), recalling that

W t := F (t, Y ) -F (t, Z) , t ∈ [0, T ].

The Existence Results

In this section we present the main results of this paper. We introduce formally the equation and its statements regarding existence of solutions.

We state a version of Schauder fixed point theorem that we are using.

Theorem 13. Let M be a non-empty, closed, bounded, convex subset of a Banach space, and suppose S : M → M is a continuous operator which maps M into a compact subset of M . Then M has a fixed point.

Proof. See [1, Th. 2.2].
The next two lemmas will will help us gluing Hölder functions.

Lemma 14. Let I and J denote two compact intervals of R such that I ∩J is non-empty. Let Y :

I ∪ J → U a path such that Y ∈ C α (I) and Y ∈ C α (J). Then Y ∈ C α (I ∪ J) and Y α;I∪J ≤ 2 Y α;I + Y α;J .
Proof. See [START_REF] Gubinelli | Controlling rough paths[END_REF]Lemma 3].

Lemma 15. Fix τ > 0. Let 0 =: t 0 < t 1 < • • • < t N +1 := T be a partition of [0, T ],
where every sub-interval has length τ , i.e., t i -t

i-1 = τ , ∀i = 1, . . . , N . Let Y : [0, T ] → U such that Y α;t i ,τ ≤ R,
for all i = 1, . . . , N . Then

Y α;[0,T ] ≤ 4R 1 ∨ T 1-α τ α-1 . Proof. Let s, t ∈ [0, T ]. If |t -s| ≤ τ then s and t belong to (at most) two consecutive interval [t i , t i+1 ]. Hence, |Y t -Y s | ≤ 2(R + R) |t -s| α , see Lemma 14 above. Otherwise, t K < s ≤ t K+1 < • • • < t < t K+r+1 with τ r < t -s ≤ τ (r + 1) for some r ≥ 1. Then |Y t -Y s | ≤ r+1 j=1 Y t∧t K+j -Y s∨t K+j-1 ≤ R r j=1 |t ∧ t K+j -s ∨ t K+j-1 | α ≤ Rτ α (r + 1) = Rτ α-1 τ (r + 1) ≤ 2Rτ α-1 τ r ≤ 2Rτ α-1 |t -s| ≤ 2Rτ α-1 T 1-α |t -s| α . In conclusion Y α;[0,T ] ≤ 4R 1 ∨ T 1-α τ α-1 .
Now we state and prove the first existence theorem for global solutions in time. We insist on the fact that our assumptions do not imply that F is bounded. This particular case will be investigated in the subsequent Theorem 18.

Theorem 16. Let U and V be finite dimensional linear spaces. Let α > 1 2 and X : [0, T ] → V an α-Hölder path. Let β ∈ (0, 1)

such αβ + α > 1. Let F : [0, T ] × C α ′ ([0, T ] , U ) → L (V, U
) for some α ′ < α with the property F is also (α ′ , β)-Hölder continuous. Given an initial condition y 0 ∈ U, there is a solution Y ∈ C α ([0, T ] , U ) for the equation

Y t = y 0 + ˆt 0 F (u, Y ) dX u , t ∈ [0, T ] . (5.1)
Remark 17.

1. A more general framework of (5.1) is a path-dependent equation with initial condition at t 0 instead of 0, for t ∈ [t 0 , t 1 ] with t 1 ∈ [t 0 , T ]. In that case the initial condition will be a function

η ∈ C α [0, t 0 ].
In correspondence to this we introduce Z η : [0, t 1 ] → U setting

Z η t := η t ; t ∈ [0, t 0 ] Z t ; t ∈ [t 0 , t 1 ] . (5.
2)

The equation of our interest is

Y t = η t 0 + ´t t 0 F (u, Y η ) dX u , t ∈ [0, t 1 ] , Y s = η s , s ∈ [0, t 0 ]. (5.3)
We remark that (5.1) is a particular case of (5.3) setting t 0 = 0 and t 1 = T .

2. The strategy employed in the proof will be first to construct a solution of (5.1) replacing T with a small time τ . Then given t 0 , which will be of the type t 0 = kτ for k = 0, 1, . . . ,, and η ∈ C α ([0, t 0 ]) we will inductively construct a solution of (5.3) with t 1 = t 0 + τ . For the general induction step we consider the so called solution map, i.e. a functional S η :

M → C α ′ ([t 0 , t 1 ]
), where M is a suitable subset of C α ′ ([t 0 , t 1 ]) which will be introduced later, so that S η (M ) ⊂ M , defined by

S η (Z) t := η t 0 + ˆt t 0 F (u, Z η ) dX u , t ∈ [t 0 , t 0 + τ ] (5.4)
and Z ∈ M . We will prove that S η has a fixed point through Schauder's Theorem 13), which of course solves (5.3) in [t 0 , t 1 ]. This would imply the existence of a solution on the whole time interval [0, T ], by patching solutions together.

Proof.

Step 1. We can assume without loss of generality that

α ′ β + α ′ > 1, (5.5)
and moreover, that there is θ ∈ (0, 1) such that F is α ′ θ 2 , β -Hölder continuous and

α ′ θ 2 β + α ′ θ 2 > 1, (5.6)
as well.

For this we are going to fabricate constants α larger than α ′ and θ such that F is αθ 2 , β -Hölder continuous and (α, θ) fulfill (5.5) and (5.6) with α ′ replaced by α. Indeed, since by hypothesis, α is strictly greater than 1 2 and because of the inequality αβ + α > 1, we can first choose α ∈

1 β+1 , α ∩ 1 2 , α . θ ∈ (0, 1) such that θ 2 α ∈ 1 β+1 , α ∩ 1
2 , α , which is possible by a similar reasoning. Now, we have α ′ < θ 2 α < α < α so Lemma 7 guarantees that F is αθ 2 , β -Hölder continuous, with α and θ fulfilling the inequalities (5.5) and (5.6) with α ′ replaced with α.

Morally this step consists in restricting the domain of the vector field F into a suitable smaller set C α, i.e., C α ⊂ C α ⊂ C α ′ . The choice of a suitable α does not play any role regarding the space where the solution Y lives, as we can see in the next step.

Step 2. Looking for a solution of

(5.3) in C α ([t 0 , t 1 ]), it is enough to show that there is a solution Y ∈ C α ′ ([t 0 , t 1 ]). Indeed, if Y ∈ C α ′ ([t 0 , t 1 ]) solves (5.
|Y t -Y s | = ˆt s F (u, Y ) dX u ≤ k α ′ β+α c 1 + Y β α ′ ;[s,t] X α;[0,T ] |t -s| α ′ β+α + |F (s, Y )| X α;[0,T ] |t -s| α ≤ k α ′ β+α c 1 + Y β α ′ ;[0,t 1 ] T α ′ β + F ( , Y ) ∞ X α;[0,T ] |t -s| α ,
where c = c α ′ ,β as defined in (4.2).

Step 3. Discussion about set the M ⊂ C α ′ ([t 0 , t 0 + τ ]), anticipated in the Remark 17 item 2. M will be of the type

M := M α ′ t 0 ,τ,R,a := Z ∈ C α ′ ([t 0 , t 0 + τ ]) | Z t 0 = a,
and Z α ′ ;t 0 ,τ ≤ R , (5.7) for fixed R, τ > 0 and a ∈ U . We will indeed set a = η t 0 ∈ U , and R, τ will be suitable parameters, see (5.12) and (5.13), in order to guarantee that

S η M α ′ t 0 ,τ,R,ηt 0 ⊂ M α ′ t 0 ,τ,R,ηt 0 .
Step 4. Let R > 0, t 0 ∈ [0, T ), τ ∈ (0, 1], a ∈ U , which will be arbitrary in this step, the set M α ′ t 0 ,τ,R,a is compact in C θα ′ -topology. This is a standard result, however though we present its proof for the sake of completeness.

We recall the set M α ′ t 0 ,τ,R,a is a subset of C θα ′ ([t 0 , t 0 + τ ]) with a fixed initial condition, hence C θα ′ -topology in M α ′ t 0 ,τ,R,a is induced by α ′ θ;t 0 ,τ . Now we prove the claim, let (Z n ) be a sequence in M α ′ t 0 ,τ,R,a , n ∈ N. This is an equicontinuous family in

[t 0 , t 0 + τ ], since |Z n t -Z n s | ≤ R |t -s| α ′ , s, t ∈ [t 0 , t 0 + τ ] for each n. Also, the sequence is uniformly bounded since |Z n t | ≤ |Z n 0 | + R |t -0| α ′ = |a| + R |t| α ′ .
Hence, by the classical Arzelà-Ascoli Theorem, there is Z ∈ C([t 0 , t 0 + τ ]) such that, for a subsequence (also denoted by Z n ), Z n -Z ∞;t 0 ,t 0 +τ → 0, as n → ∞. So, in particular Z t 0 = a, on the one hand. On the other hand, it is easy to see that Z α ′ ;t 0 ,τ ≤ R, since

|Z t -Z s | = lim n→∞ |Z n t -Z n s | ≤ lim n→∞ R |t -s| α ′ .
Therefore Z ∈ M α ′ t 0 ,τ,R,a . In order to show Z n -Z θα ′ ;t 0 ,τ → n→∞ 0, we use the geometric interpolation, see Remark 11, so

Z n -Z θα ′ ≤ 2 1-θ Z n -Z 1-θ ∞;t 0 ,τ Z n -Z θ α ′ ;t 0 ,τ ≤ 2 1-θ Z n -Z 1-θ ∞;t 0 ,τ Z n α ′ ;t 0 ,τ + Z α ′ ;t 0 ,τ θ ≤ 2 1-θ Z n -Z 1-θ ∞;t 0 ,τ (
2R) θ and we observe that the right-hand side converges to zero as n goes to ∞.

Step 5. Let R > 0, t 0 ∈ [0, T ), τ ∈ (0, 1], a ∈ U and η ∈ C α ([t 0 , t 0 + τ ]), which will be arbitrary in this step. Let θ as introduced in Step 1. Then the map S η :

M α ′ t 0 ,τ,R,a → C α ′ ([t 0 , t 0 + τ ]) is continuous under the C α ′ θ ([t 0 , t 0 + τ ])-topology. We recall that α ′ θ 2 β + α ′ θ 2 > 1, see (5.6). Since M α ′ t 0 ,τ,R,a is compact, it is a closed subset of C α ′ θ ([t 0 , t 0 + τ ]).
Fix an arbitrary W ∈ M α ′ t 0 ,τ,R,a . We will show S η (Z) -S η (W ) θα ′ ;t 0 ,τ → 0 as Z -W θα ′ ;t 0 ,τ → 0, Z ∈ M α ′ t 0 ,τ,R,a . We use now Young integral inequality (3.3) with α replaced with α ′ θ and γ replaced with α ′ θ 2 β. We observe that the sum µ := α ′ θ 2 β + α ′ θ 2 which is strictly larger than 1 so Theorem 2 can be applied and by (3.3)

S η (Z) -S η (W ) θα ′ ;t 0 ,τ = ˆ t 0 F (u, Z η ) -F (u, W η ) dX u θα ′ ;t 0 ,τ
Moreover by (4.2), it also holds that

|F (0, Z)| ≤ |F (0, 0)| + cα ′ ,β |Z 0 -0| β = |F (0, 0)| + cα ′ ,β |y 0 | β .
(5.17)

Plugging (5.16),(5.17) into (5.15), using X α ′ ;0,τ ≤ X α;0,T τ α-α ′ and |y 0 | , Z α ′ ;0,τ ≤ R, also recalling c F = max |F (0, 0)| ; c α ′ ,β ; cα ′ ,β , definitions from τ and R, (see (5.12), (5.13)), we have

S (Z) α ′ ;0,τ ≤ k α ′ β+α ′ + 1 X α;0,T τ α-α ′ c 1 + R β + |F (0, 0)| + cR β ≤ k α ′ β+α ′ + 1 X α;0,T τ α-α ′ 2c F 1 + R β ≤ Kτ α-α ′ 1 + R β = ε 1 + R β ≤ R.
This proves Step 6.

Let R > 0 as in (5.13) and (5.14) together with τ selected in (5.11) until the end of the proof.

Step 7. There is a solution Y ∈ C α ([0, τ ]) for (5.1) replacing T with τ , with Y 0 = y 0 and Y α ′ ;0,τ ≤ R. This constitutes the first stage of a statement which will be proved by induction in Step 9. below. This simply follows from Steps 4., 5., 6. which allow us to use Theorem 13 and finally Step 2.

From Step 6. the map S : M α ′ 0,τ,R,y 0 → M α ′ 0,τ,R,y 0 is well-defined and Step 5. shows us it is continuous under C α ′ θ -topology. Since M α ′ 0,τ,R,y 0 is compact under C α ′ θ -topology, see Step 4., Schauder's Theorem 13 claims that there is a fixed point for the map S, denoted by Y ∈ M α ′ 0,τ,R,a . In other words, there is Y ∈ M α ′ 0,τ,R,a , such that

Y t = S (Y ) t = y 0 + ˆt 0 F (u, Y ) dX u , t ∈ [0, τ ] . Finally, from Step 2., we conclude that Y ∈ C α [0, τ ].
Step 8. Now we prove the general statement announced in step 6. Let

t 0 = N τ for some N = 1, 2, . . .. Assume that η ∈ C α ([0, t 0 ]) such that η α ′ ;kτ,τ ≤ R for k = 0, 1, . . . , N -1, we have S η M α ′ t 0 ,τ,R,ηt 0 ⊂ M α ′ t 0 ,τ,R,ηt 0 . (5.18) Indeed, let Z ∈ M α ′ t 0 ,τ,R,ηt 0
. From Young integral inequality (3.3) using α ′ β (and α ′ ) instead of δ (and α),

S η (Z) α ′ ;t 0 ,τ ≤ k α ′ β+α ′ + 1 X α ′ ;t 0 ,τ F ( , Z η ) α ′ β;t 0 ,τ + |F (t 0 , Z η )| . (5.19)
Since F is (α ′ , β)-Hölder continuous, by (4.5) from Proposition 12 with α ′ instead of α and noting that Z α ′ ;t 0 ,τ ≤ R it follows

F ( , Z η ) α ′ β;t 0 ,τ ≤ c α ′ ,β 1 + Z η β α ′ ;t 0 ,τ ≤ c α ′ ,β 1 + Z β α ′ ;t 0 ,τ ≤ c α ′ ,β 1 + R β .
(5.20)

Regarding |F (t 0 , Z η )|, we split it as

|F (t 0 , Z η )| = |F (t 0 , η)| ≤ |F (t 0 , η) -F (0, η)| + |F (0, η) | =: A + B. (5.21)
On the one hand, by (4.5) from Proposition 12, Lemma 15 together with hypothesis η α ′ ;kτ,τ ≤ R, recalling again that c F = max |F (0, 0)| ; c α ′ ,β ; cα ′ ,β and also that t 0 = N τ ≤ T and 4 β < 5, it follows that

A = |F (N τ, η) -F (0, η)| ≤ c α ′ ,β 1 + η β α ′ ;0,N τ (N τ ) α ′ β ≤ c α ′ ,β 1 + 4R 1 ∨ T 1-α ′ τ α ′ -1 β T α ′ β ≤ c F T α ′ β 1 + 5R β 1 ∨ T 1-α ′ τ α ′ -1 β . (5.22)
On the other hand, since F is (α ′ , β)-Hölder continuous using 5 β ≤ 5 and the hypothesis η α ′ ;kτ,τ ≤ R,

|y 0 | ≤ R it follows that B ≤ |F (0, 0)| + |F (0, η) -F (0, 0)| ≤ F (0, 0) + cα ′ ,β η -0 α ′ ;0,N τ + |η 0 -0| β ≤ c F 1 + η α ′ ;0,N τ + |y 0 | β ≤ c F 1 + 4R 1 ∨ T 1-α ′ τ α ′ -1 + R β ≤ c F 1 + 5R 1 ∨ T 1-α ′ τ α ′ -1 β ≤ c F 1 + 5R β 1 ∨ T 1-α ′ τ α ′ -1 β , (5.23)
where we have used Lemma 15 in the fourth inequality. Hence, from (5.22) and (5.23) we conclude

|F (t 0 , Z η )| ≤ c F 1 + T α ′ β 1 + 5R β 1 ∨ T 1-α ′ τ α ′ -1 β .
(5.24) Now, plugging (5.20) and (5.24) into (5.19), using X α ′ ;t 0 ,τ ≤ X α;0,T τ α-α ′ and recalling the definitions of τ and R given in (5.12), (5.13), it yields

S η (Z) t α ′ ;0,τ ≤ k α ′ β+α ′ + 1 X α;0,T τ α-α ′ 2c F 1 + T α ′ β 1 + 5R β 1 ∨ T 1-α ′ τ α ′ -1 β = ε 1 + 5R β 1 ∨ T 1-α ′ τ α ′ -1 β ≤ R.
This proves (5.18).

Step 9. There is a solution Y ∈ C α ([0, (N + 1)τ ]) for the (5.1) replacing T with (N + 1)τ , with Y 0 = y 0 and Y α ′ ;kτ,τ ≤ R, each k = 0, 1, . . . , N . This constitutes the induction stage which we announced in Step 7.

Indeed, the case N = 0 was proved in Step 7. Now, assume there is a solution η ∈ C α ([0, N τ ]) (replacing T with N τ ) of (5.1) with η α ′ ;kτ,τ ≤ R, each k = 0, 1, . . . , N -1. The solution η fulfills the conditions of the Step 8. with

t 0 = N τ , hence S η M α ′ t 0 ,τ,R,ηt 0 ⊂ M α ′ t 0 ,τ,R,ηt 0
. Reasoning as at Step 7., the map S η : M α ′ t 0 ,τ,R,ηt 0 → M α ′ t 0 ,τ,R,ηt 0 has a fixed point denoted by W , which in particular solves (5.3):

W t = S η (W ) t = η N τ + ˆt N τ F (u, W η ) dX u , t ∈ [N τ, (N + 1) τ ] , (5.25)
where we remind that the notation W η was introduced in (5.2). Finally, we define Y := W η ∈ C α ([0, (N + 1)τ ]) which trivially extends η. We show below that Y solves equation (5.1). Indeed, on the one hand for each t ∈ [0, N τ ] , recalling F (u, η) = F (u, Y ) for u ∈ [0, N τ ] and that η is a solution in the interval [0, N τ ], we have

Y t = W η t = η t = y 0 + ˆt 0 F (u, η) dX u = y 0 + ˆt 0 F (u, Y ) dX u .
On the other hand, arguing as above and using (5.25), we have, for t ∈ [N τ, (N + 1) τ ],

Y t = W η t = W t = η N τ + ˆt N τ F (u, W η ) dX u = y 0 + ˆNτ 0 F (u, η) dX u + ˆt N τ F (u, W η ) dX u = y 0 + ˆNτ 0 F (u, Y ) dX u + ˆt N τ F (u, Y ) dX u = y 0 + ˆt 0 F (u, Y ) dX u .
This concludes that Y is a solution to (5.1) on the interval [0,

N τ + τ ]. Moreover, Y α ′ ;kτ,τ = W η α ′ ;kτ,τ ≤ R for k = 0, 1, . . . , N . Indeed for = c α ′ ,β 1 + Z β α ′ ;t 0 ,τ ≤ c α ′ ,β 1 + 1 β ≤ 2c α ′ ,β .
(5.29) Also, since F is bounded it holds

|F (t 0 , Z η )| = |F (t 0 , η)| ≤ F ∞ .
(5.30)

We substitute (5.29) and (5.30) into (5.28). Using X α ′ ;t 0 ,τ ≤ X α;0,T τ α-α ′ , ε ≤ 1 and recalling that τ satisfies (5.10), it follows that

S η (Z) α ′ ;t 0 ,τ ≤ k α ′ β+α ′ + 1 X α;0,T τ α-α ′ 2c α ′ ,β + F ∞ = Kτ α-α ′ = ε ≤ 1, henceforth S η M α ′ t 0 ,τ,1,ηt 0 ⊂ M α ′ t 0 ,τ,1,ηt 0
. This concludes the proof of (5.27). The sequel of the proof consists in treating simultaneously the corresponding Steps 7. and 9. of the proof of Theorem 16. We claim that S η : M α ′ t 0 ,τ,1,ηt 0 → M α ′ t 0 ,τ,1,ηt 0 has a fixed point. Indeed, we already know that M α ′ t 0 ,τ,1,ηt 0 is a compact set with respect α ′ θ-Hölder topology (see Step 4. in the proof of Theorem 16) and S η is continuous with respect α ′ θ-Hölder topology (see Step 5. in the proof of Theorem 16). So S η verifies the hypothesis of Schauder's Theorem 13, hence there is a fixed point for S η , which we denote by W ∈ C α ′ ([t 0 , t 0 + τ ]); W also belongs to C α ([t 0 , t 0 + τ ]) by Step 2. in the proof of Theorem 16. In other words,

W t = η t 0 + ˆt t 0 F (u, W η ) dX u , t ∈ [t 0 , t 0 + τ ]. (5.31)
Finally, we can conclude the proof showing that there is a solution Y ∈ C α ([0, T ]) to (5.1) proceeding similarly as after (5.25).

6 On a particular path-dependent structure of the vector field.

We conclude the paper showing that, in some cases, the solution to our pathdependent equation can be constructed directly. In this case the method leads us to an existence (and even uniqueness) statement under weaker assumptions than in Theorems 16 and 18. This happens when the past dependence structure of the vector F allows a gap (of size δ > 0) between the past and the present, see Definition 19 below for the precise meaning.

Definition 19. Let F : [0, T ] × C ([0, T ] , U ) → L be an vector field. We will say that it is δ-non-anticipating if it satisfies

F (t, Y ) = F t, Y (t-δ) + , (6.1)
for all Y ∈ C ([0, T ] , U ) and t ∈ [0, T ].

Under this assumption we can construct a solution step by step on intervals [0, δ], [0, 2δ], . . . and so on only supposing, for instance, that for each

Z ∈ C α ([0, T ]), t → F (t, Z) is γ-Hölder continuous with α + γ > 1.
The theorem below holds even when U and V are generic Banach spaces.

Theorem 20. Let F : [0, T ] × C α ([0, T ] , U ) → L be a δ-non-anticipating vector field for some δ > 0. Suppose that for each Although we need to define Y n t only for t ∈ [0, nδ], we have chosen to extend it to the whole interval t ∈ [0, T ] since this simplifies the formulation of some arguments during this proof.

Z ∈ C α ([0, T ], U ), t → F (t, Z) is γ-Hölder continuous with α+γ > 1. Let X ∈ C α ([0, T ] , V ). Then for each y 0 ∈ U there is a unique solution Y ∈ C α ([0, T ]) for the equation Y t = y 0 + ˆt 0 F (u, Y ) dX u , t ∈ [0, T ] . ( 6
The expression (6.3) is well-defined via Theorem 2 with W t = F t, Y n-1 . Indeed, suppose that (6.3) holds replacing integer n with n-1. Since Y n-1 ∈ C α ([0, T ]), the hypothesis implies that the path t ∈ [0, T ] → F t, Y n-1 is γ-Hölder continuous hence we can define Y n t := y 0 + ´t∧nδ 0 F u, Y n-1 dX u , for t ∈ [0, T ].

At this point our aim is to prove that Y := Y N solves equation (6.2). For this we will show that for n = 1, . . So, using (6.1) and taking in account (6.7), yields

F (u, Y n ) = F u, Y n (u-δ) + = F u, Y n-1 (u-δ) + = F u, Y n-1 .
It remains to show (6.6); we will do it by induction on n. The case n = 1 is an obvious consequence of (6.3) evaluated for t = 0. We suppose now that (6.6) holds replacing n with n -1.

Let t ∈ [0, (n-1)δ] for an integer n with n ≥ 2. By (6.1), the construction (6.3), the induction hypothesis related to (6.6) and the recurrence (6.

  An important closed subset of C α (I) is obtained by fixing an initial condition. That is, for a fixed a ∈ U , we define C α a (I) := {Y ∈ C α (I) | Y t 0 = a} and this is a closed subset of C α (I). Moreover, the metric |||Z -Y ||| α;I on C α a (I) coincides with α;I , i.e. |||Z -Y ||| α;I = Z -Y α;I , for all Z, Y ∈ C α (I). For the sake of clarity, when we refer to C α -topology we mean the topology induced by ||| ||| α;I , which coincides with α;I in the subset C α a (I). The set C (I) is the usual Banach space of continuous functions equipped with the sup-norm, Y ∞;I := sup t∈I |Y t |.

  3), then by (3.2) in Theorem 2 and (4.1), it follows

. 2 )

 2 Proof. We start discussing existence. Without restriction of generality we can suppose that T = N δ for some integer N . We denote by Y 0 the constant function t → y 0 ∈ U on [0, T ]. By recurrence arguments we construct a sequence Y 1 , . . . , Y N in C α ([0, T ]) verifying, for n = 1, . . . , N , Y n t := y 0 + ˆt∧nδ 0 F u, Y n-1 dX u , t ∈ [0, T ]. (6.3)

0 F

 0 (u, Y n ) dX u , t ∈ [0, T ]. (6.4)Taking into account the construction (6.3), it will be enough to show by recurrence that, for every n = 1, . . . , NF (u, Y n ) = F (u, Y n-1 ), u ∈ [0, nδ] . (6.5)Suppose for a moment that, for every n = 1, . . . , N ,Y n t = Y n-1 t , t ∈ [0, (n -1)δ]. (6.6) Then (6.5) will follow. Indeed let u ∈ [0, nδ], for some n; then t := (uδ) + belongs to [0, (n -1)δ]; thus from (6.6), recalling Y r (x) := Y r∧x it follows Y n (u-δ) + = Y n-1 (u-δ) + , u ∈ [0, nδ]. (6.7)

.

  [START_REF] Girolami | Infinite dimensional stochastic calculus via regularization and applications[END_REF] with n -1 replacing n, we obtainY t = y 0 + ˆt∧nδ 0 F u, Y n-1 dX u = y 0 + ˆt∧(n-1)δ 0 F u, Y n-1 dX u = y 0 + ˆt∧(n-1)δ 0 F u, Y n-2 dX u = Y n-1 tThis concludes the proof of the induction step in (6.6). The existence part of the theorem is finally established.Uniqueness follows easily by an obvious induction argument.ACKNOWLEDGEMENTS. The first named author was supported by the (Brazilian) National Council for Scientific and Technological Development (CNPq), under grant Nr. 232925/2014-3. Part of the work was done during a visit of the second author to the University of Bielefeld, SFB 701. He is grateful to Prof. Michael Röckner for the kind invitation.

≤ (k µ + 1) X θα ′ ;t 0 ,τ F ( , Z η ) -F ( , W η ) θ 2 α ′ β;t 0 ,τ .

(5.8)

We recall that F is (α ′ θ 2 , β)-Hölder continuous, see Step 1.

From Proposition 12, see (4.6), using α ′ θ (and t 0 + τ ) instead of α (and t 1 ), it follows that

θα ′ ;t 0 ,τ .

(5.9)

From (5.8) and (5.9) we conclude that S η is continuous with respect to C α ′ θtopology.

Step 6. We prove now that S η M α ′ t 0 ,τ,R,y 0 ⊂ M α ′ t 0 ,τ,R,y 0 in the case when t 0 = 0, with η : {0} → U , η 0 = y 0 for any y 0 ∈ U and suitable R, τ > 0 introduced below. We will extend this property at Step 8. for t 0 = N τ , N = 1, 2, . . .. We set

and c F := max |F (0, 0)| ; c α ′ ,β ; cα ′ ,β . We can assume K > 0, otherwise either X α;0,T = 0 or F = 0, thus the constant function Y t := y 0 solves (5.1). Let ε ∈ 0, K 2 be fixed and τ is defined by

so that, 0 < τ < 1 and Kτ α-α ′ = ε.

(5.12)

Let R > 0 big enough such that

)

which is always possible since β < 1. Indeed, given a function g : R → R defined by g(R) = c + dR β , c, d > 0, the limit of g(R) R when R → ∞ is zero. From now on in this step we set S := S η . We prove now that S M α ′ 0,τ,R,y 0 ⊂ M α ′ 0,τ,R,y 0 . Indeed, given Z ∈ M α ′ 0,τ,R,y 0 , from Young integral inequality (3.3), it follows that

(5.15) Since F is (α ′ , β)-Hölder continuous, by Proposition 12 it follows that

(5.16) k = 0, 1, . . . , N -1, this holds by assumption and for k = N it comes from (5.18). Hence this establishes the induction step and it concludes Step 9.

The theorem below shows that when F is bounded the coefficient β is also allowed to be 1. We remark that in Theorem 16 we have required that β < 1.

Theorem 18. Let U and V be finite dimensional linear spaces. Let α, β ∈ (0, 1] such that α > 1 2 and αβ + α > 1. Let X : [0, T ] → V be an α-Hölder path and F : [0, T ] × C α ′ ([0, T ] , U ) → L (V, U ) be a bounded and (α ′ , β)-Hölder continuous vector field for some α ′ < α. Given an initial condition y 0 ∈ U , there is a solution Y ∈ C α ([0, T ] , U ) for the equation

Proof. This proof is simpler than the one of Theorem 16 (where F is not bounded) and we will explain here the significant changes. We start reintroducing the objects. First, as explained in Step 1. of Theorem 16 we can assume that 1 2 < α ′ < α and also that there is θ ∈ (0, 1) such that F is α ′ θ 2 , β -Hölder continuous and the inequalities (5.5) together with (5.6) are still in force.

Second, we re-define the parameters K, ε and τ . So, differently from (5.10) in Step 6., we set

We fix ε ∈ 0, K 2 ∧ 1 and define again τ as in (5.11) so that τ ∈ (0, 1) and (5.12) still holds.

For an arbitrary t 0 ∈ [0, T ) and η ∈ C α ([0, t 0 ]) with η 0 = y 0 , similarly as in the proof of Theorem 16, we will find a solution of (5.3) with t 1 = t 0 + τ . This can be done performing the same program of Steps 2. to 5. in the proof of Theorem 16. The notation M α ′ t 0 ,τ,1,a will denote the same ball as in (5.7). We define Z η as in (5.2) and S η : (5.4). In order to show that S η has a fixed point (which therefore solves (5.3)) we need to prove first that

(5.27)

This will replace Steps 6. and 8. of the proof of Theorem 16 which will merge, since it will not be necessary to distinguish t 0 = 0 from t 0 = N τ, N ≥ 1. Indeed, given Z ∈ M α ′ t 0 ,τ,1,ηt 0 , from Young integral inequality (3.3), replacing γ there by α ′ β as for (5.15), it follows that S η (Z) α ′ ;t 0 ,τ ≤ k α ′ β+α ′ + 1 X α ′ ;t 0 ,τ F ( , Z η ) α ′ β;t 0 ,τ + |F (t 0 , Z η )| .

(5.28) Since F is (α ′ , β)-Hölder continuous, it follows from Proposition 12, see (4.5) with α ′ (resp. Z η ) instead of α (resp. Y ) that F ( , Z η ) α ′ β;t 0 ,τ ≤ c α ′ ,β 1 + Z η β α ′ ;t 0 ,τ


Alessio Conte
email: conte@di.unipi.it

Roberto Grossi
email: grossi@di.unipi.it

Andrea Marino
email: marino@di.unipi.it

Luca Versari
email: luca.versari@sns.it

Sublinear-Space Bounded-Delay Enumeration for Massive Network Analytics: Maximal Cliques *

Keywords: 1998 ACM Subject Classification E.1 Data Structures -Graphs and networks, G.2.2 Graph Theory -Graph algorithms Enumeration algorithms, maximal cliques, network mining and analytics, reverse search, space efficiency Digital Object Identifier 10.4230/LIPIcs.ICALP.2016.148

Due to the sheer size of real-world networks, delay and space become quite relevant measures for the cost of enumeration in network analytics. This paper presents efficient algorithms for listing maximum cliques in networks, providing the first sublinear-space bounds with guaranteed delay per enumerated clique, thus comparing favorably with the known literature.

Introduction

The design of efficient algorithms for enumerating all possible solutions of a given problem dates back to the 1950s [START_REF] Bierstone | Cliques and generalized cliques in a finite linear graph[END_REF][START_REF] Eo | Enumeration of labelled graphs[END_REF][START_REF] Trent | A note on the enumeration and listing of all possible trees in a connected linear graph[END_REF]. Enumeration algorithms have the purpose of either counting the number of solutions or listing the solutions one by one. Their study originated in the area of complexity and optimization [START_REF] Fukuda | Note on new complexity classes ENP, EP and CEP[END_REF][START_REF] Johnson | On generating all maximal independent sets[END_REF][START_REF] Valiant | The complexity of computing the permanent[END_REF], and then spread over several other application domains, including bioinformatics, machine learning, network analytics, and social analysis [START_REF] Nesreen | Efficient graphlet counting for large networks[END_REF][START_REF] Milo | Network motifs: simple building blocks of complex networks[END_REF][START_REF] Shervashidze | Efficient graphlet kernels for large graph comparison[END_REF]. For instance, a number of papers described how to enumerate triangles [START_REF] Björklund | Listing triangles[END_REF][START_REF] Alon | Color-coding[END_REF][START_REF] Itai | Finding a minimum circuit in a graph[END_REF][START_REF] Schank | Finding, counting and listing all triangles in large graphs, an experimental study[END_REF] and their generalizations such as cliques or other dense subgraphs [START_REF] Bron | Finding all cliques of an undirected graph (algorithm 457)[END_REF][START_REF] Chang | Fast maximal cliques enumeration in sparse graphs[END_REF][START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF][START_REF] Comin | An improved upper bound on maximal clique listing via rectangular fast matrix multiplication[END_REF][START_REF] Du | Parallel algorithm for enumerating maximal cliques in complex network[END_REF][START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF][START_REF] Henry | Transactions on Rough Sets XVI, chapter Maximal Clique Enumeration in Finding Near Neighbourhoods[END_REF][START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF][START_REF] Pan | An anytime-anywhere approach for maximal clique enumeration in social network analysis[END_REF][START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF][START_REF] Uno | An efficient algorithm for solving pseudo clique enumeration problem[END_REF]. Among the first problems attacked is the enumeration of maximal cliques [START_REF] Akkoyunlu | The enumeration of maximal cliques of large graphs[END_REF][START_REF] Bierstone | Cliques and generalized cliques in a finite linear graph[END_REF][START_REF] Bron | Finding all cliques of an undirected graph (algorithm 457)[END_REF][START_REF] Gerhards | Clique detection for nondirected graphs: Two new algorithms[END_REF][START_REF] Johnston | Cliques of a graph-variations on the Bron-Kerbosch algorithm[END_REF][START_REF] Mulligan | Corrections to Bierstone's algorithm for generating cliques[END_REF], where a maximal clique is a subset of pairwise connected vertices that is maximal under inclusion. This paper focuses on two worst-case efficiency measures, namely, delay and space, that become relevant for enumeration in massive networks. The delay is the maximum latency between any two consecutively reported solutions. The space is the maximum amount of extra memory that should be allocated to enumerate all the solutions, besides the amount required by the input graph. This paper

Õ(m) Õ(min{md, qd∆}) α Õ(min{md, qd∆}) O(d) n = #vertices ∆ = max degree α = #maximal cliques m = #edges d = degeneracy q = largest clique size
ordering can be computed in O(n + m) time by repeatedly removing the vertex of minimum degree from G. Also, it can be proved that d = O( √ m), and that the size q of the maximum clique in G and the maximum degree in the graph ∆ satisfy q -1 ≤ d ≤ ∆ ≤ n -1.

The last two rows in Table 1 report our bounds in terms of the above parameters, where the Õ() notation ignores log O (1) (n + m) factors. We observe that our bounds are expressed in terms of the parameters q, d, ∆ instead of m, n, whenever possible, as they are actually smaller than m or n. For example, network eu-2005 has q = 387, d = 388 and ∆ = 68 963. Also, since both q and d are always O( √ m), our space is provably sublinear (around 20 kilobytes for eu-2005!). Note that ∆ is not always sublinear in the graph size as real-world networks are sparse and could have ∆ = Θ(n), as shown in Table 2 (see also [START_REF] Conte | Finding all maximal cliques in very large social networks[END_REF]). Also, our O(q) space is close to optimal as we have to single out a subset of q vertices from G.

The other rows in Table 1 report the bounds for the main results in the state of the art (see below for a discussion). The setup time is the preprocessing cost before starting to list the solutions, and ours is comparable to that of previous results. As for the delay, the cost in the last row is asymptotically smaller in many cases, except for dense graphs, where matrix multiplication based algorithms [START_REF] Comin | An improved upper bound on maximal clique listing via rectangular fast matrix multiplication[END_REF][START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF] are preferable (but massive networks can hardly be processed by quadratic space algorithms). As for the overall time, we have a similar improvement for output-sensitive bounds where the α term appears. Moreover, we observe that [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] has great time performance in practice (see Section 7) but it is not output-sensitive as α does not appear in the complexity, and cannot guarantee sublinear space. Summing up, our algorithms can compete with the state of the art when suitably implemented, with the additional bonus of guaranteeing small space and bounded delay.

Related work.

The idea of using small space in enumeration algorithms is not new, as witnessed by the notion of "compactness" introduced in Fukuda [START_REF] Fukuda | Note on new complexity classes ENP, EP and CEP[END_REF]: however, his goal is not sublinear space as in our paper, but polynomially bounded space in terms of the input size and the maximum output size of a solution. It is also worth mentioning that the class of CAT (constant amortized time) enumeration algorithms described in Ruskey's book [START_REF] Ruskey | Combinatorial Generation[END_REF] seems to be very promising but our algorithms cannot fall within this class as their amortized cost per solution is non-constant.

Our algorithms are based on the reverse search paradigm introduced by Avis and Fukuda [START_REF] Avis | Reverse search for enumeration[END_REF] as it has been conceived to be space-efficient by its authors. Also, we reuse some of the machinery introduced by Tsukiyama et al. [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] and Makino and Uno [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF]. In the reverse search the solutions are the nodes of a virtual digraph, for which a "successor" function is defined to jump from one solution to the other. (Gély et al. [START_REF] Gély | Enumeration aspects of maximal cliques and bicliques[END_REF] study new combinatorial properties of this virtual digraph.) A spanning tree represents all the solutions, where the depth corresponds to the number of nested levels of the corresponding recursion. To achieve sublinear space, our algorithms employ the stateless reverse search to avoid using the stack, plus other properties that exploit the structure of the maximal clique enumeration problem.

Turning to the state of the art for the maximal clique enumeration problem, Table 1 summarizes the main results. The papers by Bron and Kerbosch [START_REF] Bron | Finding all cliques of an undirected graph (algorithm 457)[END_REF] and Tsukiyama et al. [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] have defined the main lines of research for algorithms using polynomial space, and they are currently at the heart of many other algorithms. The Bron-Kerbosch algorithm relies on a backtracking scheme that is adopted in several efficient algorithms [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF][START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF][START_REF] Xu | Distributed maximal clique computation[END_REF]. The algorithm by Tsukiyama et al. has been originally conceived for the enumeration of maximal independent sets, which is a problem equivalent to that of maximal cliques, and inspired at least in part the algorithm by Johnson et al. [START_REF] Johnson | On generating all maximal independent sets[END_REF], which produces solutions in lexicographic order but requires exponential space (see also [START_REF] Gély | Enumeration aspects of maximal cliques and bicliques[END_REF]). The approach has been subsequently adapted to clique enumeration by Chiba-Nishizeki [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF], and Makino-Uno [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF] has reinterpreted [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] in the paradigm of reverse search.

Bron-Kerbosch scheme. The Bron-Kerbosch based algorithms are a popular choice for enumerating cliques due to their simplicity and good performance in practice. The original version [START_REF] Bron | Finding all cliques of an undirected graph (algorithm 457)[END_REF] does not provide any guarantee. The version in [START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF] guarantees a total running time of O(3 n/3 ), which is optimal for Moon-Moser graphs as they have 3 n/3 cliques [START_REF] Cazals | A note on the problem of reporting maximal cliques[END_REF][START_REF] Moon | On cliques in graphs[END_REF]. The version in [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] further refines and improves the work for sparse graphs, which may have up to (n -d)3 d/3 cliques, by producing an algorithm with O(d(n -d)3 d/3 ) time. All of these approaches use O(n + q∆) space to store sets of candidates and visited vertices. It is possible to modify these algorithms to decrease their space usage (e.g. by modifying the data structure in [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF]) but, to the best of our knowledge, with state of the art techniques they would still require Ω(∆), which is not sublinear as ∆ can be Θ(n) in sparse graphs. Algorithms that follow this scheme are characterized by their complexity being related to the worst-case number of cliques in a graph (instead of α), and give no guarantees on the cost per solution nor the delay: these can be shown to be both Ω(n 3 ) for [START_REF] Tomita | The worst-case time complexity for generating all maximal cliques and computational experiments[END_REF], while [START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] can have a delay of Ω(3 n/6 ) for some families of graphs.

Tsukiyama et al. scheme.

The motivation behind algorithms in this class is to achieve an output-sensitive cost that is proportional to the number α of maximal cliques times a function that depends on the graph parameters. The original algorithm by Tsukiyama et al. [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] is a backtracking procedure that enumerates maximal independent sets in O(mn) time per solution. As a maximal independent set is a maximal clique in the complementary graph, this gives an algorithm for enumerating maximal cliques in O((n 2 -m)n) time per solution. The adaptation of the algorithm to maximal cliques has been improved by Chiba and Nishizeki [START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF], who bring the delay down to O(md): 1 this algorithm is still based on a stateful backtracking procedure in which the recursion tree has depth Ω(n), making the required space Ω(n). Makino and Uno [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF] take a step towards statelessness by adapting [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] and [START_REF] Johnson | On generating all maximal independent sets[END_REF] to the paradigm of reverse search. The algorithm is still a stateful recursive approach, which takes Ω(n) space (the depth of the recursion tree). Differently from its predecessors, each node of the tree corresponds to a unique maximal clique whose children can be computed as a function of the graph and the clique itself. The Makino-Uno algorithm is provided in two versions, one combinatorial with delay O(∆ 4 ) and one based on matrix multiplication with delay O(n 2.37 ). The former has been improved to O(∆h 3 ) by Chang et al. [START_REF] Chang | Fast maximal cliques enumeration in sparse graphs[END_REF], where h is the smallest integer such that |{v ∈ V : |N (v)| ≥ h}| ≤ h: since the reverse search is not stateless, here the space remains Ω(n). The latter has been improved to O(n 2.09 ) by Comin and Rizzi [START_REF] Comin | An improved upper bound on maximal clique listing via rectangular fast matrix multiplication[END_REF] using matrix multiplication but requiring higher space usage and setup time.

Preliminaries

Let G(V, E) be an undirected graph with |V | = n and |E| = m. We assume that G is connected and represented using ordered adjacency lists. A clique is a subset K ⊆ V of pairwise connected vertices: we will use K to denote both this subset of vertices and the subgraph induced by them. Given G, let ∆ be the maximum vertex degree, d the degeneracy, and q be the maximum clique size, where

q -1 ≤ d ≤ ∆ ≤ n -1 ≤ m and d = O( √ m); also, let v 1 .
. . v n be the vertices of V labelled in a degeneracy ordering (see the introduction). We denote by V ≤i the set of vertices v 1 . . . v i . Let us define N (v) as the set of neighbors of v and N > (v) as {x ∈ N (v) : x > v}. We define N < (v) analogously. Note that |N > (v)| ≤ d as the graph is labelled in degeneracy ordering. Given a set of vertices A ⊂ V , we define N (A) = v∈A N (v) as the set of neighbors common to all the vertices in A. We call heads the vertices v such that N < (v) = ∅. Moreover, for any v ∈ V , A ≤v = A ∩ V ≤v and A <v = A ≤v \ {v}. Given two set of vertices A and B, we say that A < B if A is lexicographically smaller than B. Given a set X ⊆ V , we define complete(X) as the lexicographically smallest maximal clique that contains X.

Lemma 1. If X 1 ⊆ X 2 , then complete(X 1 ) ≤ complete(X 2 ).
Proof. Let C 1 and C 2 be the set of maximal cliques containing respectively X 1 and X 2 . Clearly C 1 ⊇ C 2 , and as complete(X) returns the lexicographically smallest maximal clique that contains X we have complete(X 1 ) = min(C 1 ) ≤ min(C 2 ) = complete(X 2 ).

Reverse Search Revisited

We sketch a reverse search algorithm for the maximal clique enumeration that revises and simplifies the algorithm by Makino and Uno [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF], which is itself a reinterpretation of the works of Tsukiyama et al. in [START_REF] Tsukiyama | A new algorithm for generating all the maximal independent sets[END_REF] and Johnson et al. in [START_REF] Johnson | On generating all maximal independent sets[END_REF] for maximal independent sets. The rationale of the algorithm can be summarized as follows. Suppose we iteratively add the vertices of G to a graph G , which is initially empty. Each time a vertex v is added, the new maximal cliques can be computed by looking at the maximal cliques of G : an existing clique K ⊆ G can be extended partially or totally by v. Of course computing all 1 The work actually exploits the arboricity, but we use d for simplicity as the arboricity is Θ(d).

for i ∈ {1, . . . , j} do Ri ← complete({vi}) spawn(Ri) Function complete(K) choose any v ∈ K foreach increasing w ∈ N (v) do if K ⊆ N (w) then K ← K ∪ {w} return K Function spawn(K) cand ← w ∈ u∈K N>(u) K : w > pi(K) foreach v ∈ cand do K v ← K<v ∩ N (v) D ← complete(K v ∪ {v}) if complete(K v ) = K and D<v = K v then spawn(D)
the cliques of G in this way requires keeping most of the cliques of the graph in memory (as for independent sets in [START_REF] Johnson | On generating all maximal independent sets[END_REF]), which takes exponential space. In order to avoid to store the cliques, we address the following question: given the clique K, maximal for G , which vertices in G \ G expand K and which cliques do they produce in G? This "production" relationship gives us the "successor" function of the reverse search paradigm. Technicalities are needed to avoid expanding K with candidates leading to the same clique more than once.

It is worth observing that, differently from [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF], our algorithm assumes that the vertices of G are given in degeneracy ordering and begins the recursion from a set of root cliques (instead of the lexicographically minimum one), where each root R i corresponds to complete run on the head v i . Moreover, we alter the given degeneracy ordering in such a way that the heads are at the beginning. This is always possible: as heads have no backward edges, when moved backwards they will not change the number of forward edges of any vertex (see Section 6).

The pseudocode is shown in Algorithm 1. The function spawn makes use of the notion of parent index, borrowed from [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF]: Definition 2 (Parent Index). Given a maximal clique K, pi(K) is the smallest x such that complete(K ≤x ) = K.

The cand set contains the vertices that partially extend K and that are greater than pi(K). For each vertex in cand we try to generate a child clique; the check in spawn corresponds to conditions (c) and (d) from Lemma 2 in [START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF], which guarantees that each child clique is only generated once. We remark that each call of spawn returns at least a clique.

Space usage and delay. Referring to Algorithm 1, we observe that the complete function only needs to store the set K, whose size is O(q), and performs O(∆) iterations that take Õ(q) time each. The cost of an iteration on vertex w is also bounded by Õ(|N (w)|), so the cost of all the iterations is bounded by Õ(m). Since pi can be computed by running complete q times, we can conclude the following: Lemma 3. Function complete in Algorithm 1 takes O(q) space and Õ(min{q∆, m}) time. Moreover, computing pi takes O(q) space and Õ(q min{q∆, m}) time.

For the sake of clarity, we will refer to the vertices in G and to the nodes in the recursive tree induced by our approach. The space requirement of each recursive node is bounded by the size of cand, as all other lines take O(q) space. As cand ⊆ V is the union of up to q sets of vertices each of size at most d, we have |cand| ≤ min{qd, n}. The recursion depth of Algorithm 1 is O(n), for a total space requirement of O(n min{qd, n}).

Consider now the delay of Algorithm 1. Note that selecting the next head takes constant time as heads are contiguous. By making use of alternative output [START_REF] Uno | Two general methods to reduce delay and change of enumeration algorithms[END_REF], as we have no dead ends, the delay of the algorithm is bounded by the cost of O(1) recursive nodes. The function spawn performs |cand| iterations, whose cost is dominated by complete. The total cost of the loop is thus Õ(min{qd, n} min{q∆, m}), which corresponds to the total cost of the recursion node as it dominates the cost of computing cand. As a consequence we have some new interesting bounds shown in Lemma 4, which we improve in the rest of the paper.

Improved Algorithm

Algorithm 1 does not meet our space requirements; still, it is the starting point to build our space efficient scheme. The first issue is its recursive nature: in function spawn, each time a recursive call is performed the status of the current call needs to be saved. As a result, we require the space needed by each recursive node multiplied by the height of the recursion tree. Note that the standard stack-based transformation of recursive programs into iterative ones, as done in [START_REF] Chang | Fast maximal cliques enumeration in sparse graphs[END_REF], does not solve the issue, as the stack size would be Ω(n). We will therefore navigate implicitly the recursion tree induced by the reverse search, without using a stack. The other important issue to achieve sublinear space is the cand set, whose size can be min{qd, n}. Hence, we need to traverse cand without materializing it.

To address the first issue, we represent the state of the computation with the pair: the current clique K the "bookmark" vertex v in cand for K (where initially v = pi(K)).

We remark that the bookmark vertex allows us to resume the computation in the parent without the need of storing information for each recursive level.

Fact 1. The state K, v requires O(q) space.

Furthermore, we implicitly traverse the recursion tree using these navigation primitives: is-root(K) checks if K is the root of current recursion tree. parent-state(K) returns the state for the parent node of K in the recursion tree. get-next-cand(K, v) finds the candidate following v in cand for the current K. child-exists(K, v) checks whether the current state will lead to a child maximal clique.

Algorithm 2 shows how to implement and use the above primitives, and Lemmas 5, 6, 7, 10 prove their correctness.

Lemma 5. Let K be any maximal clique examined in Algorithm 1: K is a root iff pi(K) = min(K). As a corollary, roots have no parent.

Proof. Let v i be the head of the recursion tree containing K and R i = complete(v i ) the relative root. By definition we have that v i is a head iff N < (v i ) = ∅, so a head must be the smallest vertex of any clique. We then have v i = min(R i ), and since min(D) ∈ K for any child D of K, there cannot be heads other than v i in the current recursion tree. From this it immediately follows that no other roots are found in the subtree of the root R i , and hence roots have no parent.

I C A L P 2 0 1 6

get-next-cand and let us assume that z 1 , . . . , z j are the first j vertices of cand. Then min{w ∈ u∈K N > (u) \ K : w > z j } is the the (j + 1)-th element of cand if |cand| > j, null otherwise. The check done in child-exists(K, v) is equivalent to the check done in spawn. We will prove this in Lemma 10 using Lemmas 8 and 9.

Lemma 8. N (K v ) ∩ B K = ∅ is equivalent to complete(K v ) = K, where B K = {u ∈ V \ K : K <u ⊆ N (u)}. Proof. Let us first prove that if ∃w ∈ N (K v ) ∩ B K then complete(K v ) = K. Note that w is adjacent to all the vertices in K <w and in K v . complete(K v ) will iteratively add to K v the smallest vertex z that is a neighbor of all the vertices in K v , so clearly z ≤ w. If z ∈ K we have complete(K v ) = K; if z ∈ K then z ∈ K <w , thus z ∈ N (w)
and w is still a candidate for the complete procedure. As w remains a candidate when z ∈ K, the process will eventually add either w or another z ∈ K. Hence, complete(K v ) = K.

We now prove that if complete

(K v ) = K then N (K v )∩B K = ∅.
Let z be the first vertex not in K selected by complete(K v ). Since all vertices in K <z were added to K v before z, we have K <z ⊆ N (z) and hence z ∈ B K . Moreover, since z has been selected by the complete procedure,

K v ⊆ N (z), which implies z ∈ N (K v ). It follows that N (K v ) ∩ B ⊇ {z} = ∅. Lemma 9. N (K v ) ∩ N < (v) = ∅ is equivalent to complete(K v ∪ {v}) <v = K v . Proof. We prove that if N (K v ) ∩ N < (v) = ∅ then complete(K v ∪ {v}) <v = K v . Let z be the smallest vertex in N (K v ) ∩ N < (v). Note that z ∈ K v , since z ∈ N (K v ). The first iteration of complete(K v ∪ {v}) selects the smallest vertex in N (K v ∪ {v}), which is z, since N (K v ∪ {v}) = N (K v ) ∩ N (v). Since z < v, we have z ∈ complete(K v ∪ {v}) <v , which implies complete(K v ∪ {v}) <v = K v .
We now prove that if complete(

K v ∪ {v}) <v = K v then N (K v ) ∩ N < (v) = ∅. Note that K v ⊆ complete(K v ∪ {v}) <v since K v ⊆ V <v . Let z = min(complete(K v ∪ {v}) <v \ K v ).
Since z has been selected by function complete, we have z

∈ N (K v ∪ {v}), that is z ∈ N (K v ) ∩ N (v). Since z < v, we have N (K v ) ∩ N < (v) ⊇ {z} = ∅. Lemma 10. N (K v ) ∩ (B K ∪ N < (v)) = ∅ iff complete(K v ) = K and complete(K v ∪ {v}) <v = K v
Using Lemmas 5, 6, 7 and 10, we finally obtain the following result: Lemma 11. Function spawn in Algorithm 1 and function improved-spawn in Algorithm 2 are equivalent.

Proof. Setting D = complete(K v ∪ {v}) we observe that improved-spawn(K) simulates the preorder traversal of the recursion tree induced by spawn(K). When all the children of the current clique K have been explored during the traversal, childless is set to true. In this case, if K is the root of the current tree there are no more maximal cliques to be generated with the given head v i ; otherwise, the state of the parent is restored.

Analysis

Analogously to Section 3, the delay of Algorithm 2 is the sum of the running times of all the iterations corresponding to the same K. Specifically, the number of iterations of the while loop is |cand| ≤ min{qd, n} (see Lemma 7). The space usage of improved-spawn, thanks I C A L P 2 0 1 6 148:10 Sublinear-Space Bounded-Delay Enumeration to its statelessness, corresponds to that of a single iteration. In order to give space and time bounds, let us analyze the costs of our navigation primitives. Since computing pi(K) dominates the space and time costs of functions is-root and parent-state, we use the bounds in Lemma 3. The next candidate can be obtained from K and the bookmark v as follows: for each element x ∈ K, perform a binary search in N (x) to obtain the smallest vertex greater than v; the minimum of these vertices is the next candidate. Thus we obtain the bounds below: Lemma 12. is-root(K) and parent-state(K) take Õ(q min{q∆, m}) time and O(q) space. get-next-cand uses Õ(q) time and constant space.

Next we give a careful analysis of child-exists, the dominating cost of improved-spawn.

Cost of testing if a child exists. Function child-exists makes use of the sets B K and N (K v ). Due to our memory constraints, we cannot store N (K v ) explicitly, since it would take Ω(∆) space. For this reason, we need to iterate over N (K v ) without materializing it.

Analogously, we cannot store B K = {v ∈ V \ K : K <v ⊆ N (v)}, whose size can be Ω(n). The following lemma will allow us to overcome this issue:

Lemma 13. The set B K is equal to V <min(K) ∪ {u ∈ N > (min(K)) \ K : K <u ⊆ N (u)}.
Proof. vertices in V <min(K) are in B K as K <min(K) = ∅, thus they can be stored implicitly. All other vertices must clearly be forward neighbors of min(K).

We denote the non-trivial part of B K , i.e. {u ∈ N > (min(K)) \ K :

K <u ⊆ N (u)}, as B K . We can compute it by testing |N > (min(K))| ≤ d candidates in O(|K|) = O(q) time.
Lemma 14. Computing (or iterating over) B K can be done in Õ(qd) time.

We will now analyze the cost of iterating over N (K v ), and two possible ways of managing B K (storing it or iterating it implicitly) leading to two different bounds.

Iterating over N (K v ). Iterating over N (K v ) using constant space can be done as follows. Let w be the vertex of K v with lowest degree: iterate over the vertices z ∈ N (w) and for each check whether K v ⊆ N (z). This costs Õ(|N (w)||K v |) = Õ( y∈K v |N (y)|), since w is the lowest degree element of K v .

Lemma 15. The total cost of iterating over all of the sets

N (K v ) for v in x∈K N > (x) is Õ(d min{q∆, m}) time. Proof. Let C K = x∈K N > (x)
. Since the cost of iterating over a given N (K v ) is bounded by Õ( y∈K v |N (y)|), the following steps prove the lemma:

v∈C K y∈K∩N<(v) |N (y)| = v∈C K y∈K |N (y)|I {y∈N<(v)} = y∈K v∈C K |N (y)|I {v∈N>(y)} = y∈K v∈N>(y) |N (y)| = y∈K |N > (y)| • |N (y)| ≤d y∈K |N (y)| ≤ d min{q∆, m}

Setup

Algorithm 3 gives some details on how to modify the degeneracy ordering of the vertices so as to place the heads at the beginning in Õ(m) time and O(1) space. As already noted, the resulting order is still a degeneracy ordering. The main idea is to maintain a sliding window over the list of adjacency lists. The window incrementally collects the heads while moving from the last vertex to the first one in the ordering, so that its final position is the beginning of the ordering. The window is moved by swapping the greatest vertex before the window, which is called s and the greatest vertex in the window, which is called e. In case s is a head, the window is not shifted but simply enlarged to include s. While moving the window, the occurrences of the labels of the swapped vertices s and e must be updated accordingly. To this aim just the occurrences of s in N > (v) are relabeled, for each v neighbor of s. At the end, the backward neighborhoods can be updated by looking at the forward ones.

It is straightforward to see that the time needed by Algorithm 3 is Õ(m). Indeed, in the loop in line 2, each adjacency list is iterated at most once. The loop in line 8 has the same time bound, i.e. Õ(m): it traverses the adjacency lists of all vertices performing replace operations, which can be done in logarithmic time on ordered lists. The constant space usage follows from the fact that just O(1) variables are stored.

Experimental Evaluation

In this section, we report some preliminary experiments on some large real-world networks that have been taken from lasagne (lasagne-unifi.sourceforge.net/). Our computing platform is a 24-core machine with Intel(R) Xeon(R) CPU E5-2620 v3 at 2.40GHz, with 128GB of shared memory. The operating system is a Ubuntu 14.04.2 LTS, with Linux kernel version 3.16.0-30. The code has been written in C++ and forced to run on a single core. Table 2 reports the results of the comparison between our algorithm and existing algorithms which use at most linear space and are output-sensitive, i.e. the ones providing a bounded delay or cost per solution, namely cn, mu, and cxq (see Table 1). We limited the running time to two hours. The algorithm ralg2 refers to a recursive version of Algorithm 2. alg2 refers to Algorithm 2 which takes O(q) memory by using Lemma 17 (similar results

Algorithm 1 :

 1 Enumerate all maximal cliques (a.k.a. revisitedMakino-Uno) Input : Graph G(V, E) where vertices are labeled in degeneracy ordering Output : Maximal cliques in G Let v1, v2, . . . vn ∈ V be the vertices labeled in degeneracy ordering, such that v1, . . . , vj are heads, where j is the number of heads (1 ≤ j ≤ n).

Lemma 4 .

 4 Algorithm 1 uses O(n min{qd, n}) space and has Õ(min{qd, n} min{q∆, m}) delay.

Table 1

 1 Bounds for maximal clique enumeration, where q-1 ≤ d ≤ ∆ ≤ n -1 ≤ m, d = O( √ m). : it does not list cliques, but outputs a compressed representation. + : h is the smallest integer such that |{v ∈ V : |N (v)| ≥ h}| ≤ h, where d ≤ h ≤ ∆. * : it uses matrix multiplication. A lower bound in the column for the delay means that there exists a family of graphs with that delay.

			Time
	Algorithm	Setup	Delay	Overall	Space
	Bron-Kerbosch [7]	O(m)	unbounded	unbounded	O(n + q∆)
	Tomita et al. [34] †	O(m)	Ω(n 3 )	O(3 n/3 )	O(n + q∆)
	Eppstein et al. [16]	O(m)	Ω(3 n/6 )	O(d(n -d)3 d/3 )	O(n + d∆)
	Johnson et al. [23]	O(mn)	O(mn)	α O(mn)	O(αn)
	Tsukiyama et al. [36] O(n 2 )	O((n 2 -m)n)	α O((n 2 -m)n)	O(n 2 )
	Chiba-Nishizeki [11]	O(m)	O(md)	α O(md)	O(m)
	Makino-Uno [25]	O(mn)	O(∆ 4 )	α O(∆ 4 )	O(m)
	Chang et al. [9] +	O(m)	O(∆h 3 )	α O(∆h 3 )	O(m)
	Makino-Uno [25] *	O(n 2 )	O(n 2.37 )	α O(n 2.37 )	O(n 2 )
	Comin-Rizzi [12] *	O(n 5.37 ) O(n 2.09 )	α O(n 2.09 )	O(n 4.27 )
	This paper	Õ(m)	Õ(qd(∆ + qd))	α Õ(qd(∆ + qd))	O(q)

†

Table 2

 2 Experimental results of our comparison with output-sensitive algorithms in the state of the art. For the graph statistics (upper part), we refer to Table1. For the comparison (lower part) we have considered the total time (time), the delay (delay), and the space (mem).

			dblp-2008		Amazon-0505		in-2004			eu-2005
	n		511 163			410 236			1 353 703			862 664
	m		1 871 070			2 439 436			13 126 172			16 138 468
	α		447 563			1 034 135			3 384 922			5 727 256
	∆		576			2 760			21 869			68 963
	d		114			10			488			388
	q		115			11			489			387
		time delay mem	time delay mem	time	delay	mem	time delay	mem
	algo.	sec	ms	MiB	sec	ms	MiB	sec	ms	MiB	sec	ms	MiB
	cn >2h	475 97.56	>2h	636 78.26	>2h	5 285 258.21	>2h	4 077 164.54
	mu	39.5	18	3.01	16.9	22	3.01 6 102.7	3 691	52.62	>2h 11 395	30.52
	cxq	21.2	4	0.11	60.7	12	0.25	>2h	6 004	1.02	>2h	621	3.15
	ralg2	1.8	0.6	1.57	3.1	0.8	0.81	66.6	401	6.46 237.4	245	3.16
	alg2	2.3	15	0.01	4.4	0.9	0.01	100.7	410	0.03 363.8	277	0.02

cn: Chiba-Nishizeki

[START_REF] Chiba | Arboricity and subgraph listing algorithms[END_REF]

mu: Sparse graph Makino-Uno

[START_REF] Makino | New algorithms for enumerating all maximal cliques[END_REF]

cxq: Chang et al.

[START_REF] Chang | Fast maximal cliques enumeration in sparse graphs[END_REF]

ralg2: Recursive Algorithm 2 alg2: Algorithm 2

148:8

Sublinear-Space Bounded-Delay Enumeration

* Work partially supported by the Italian Ministry of Education, University, and Research (MIUR) under PRIN 2012C4E3KT research project AMANDA -Algorithmics for MAssive and Networked DAta.

Algorithm 2: Improved enumeration of maximal cliques

Assume min(∅) = null, and adopt the following shorthands for maximal clique K: sub-clique K v ≡ K<v ∩ N (v) and vertex set BK ≡ {u ∈ V \ K : K<u ⊆ N (u)}.

Function improved-spawn(K)

v ← pi(K) while true do childless ← true while v ← get-next-cand(K, v) =null do if child-exists(K, v) then

Function is-root(K) return pi(K) = min(K)

We now show that N < (min(K)) = ∅ and K = complete({min(K)}) iff pi(K) = min(K). This concludes the proof as the first condition correspond to the definition of a root (min(K) being the corresponding head). Since {min(K)} = K ≤min(K) , we have pi

The next lemma states that given a clique D, the parent index allows us to identify the clique that generated D and the vertex in cand used to produce D. Lemma 6. Let K, D, and v be defined as in spawn when the recursive call is performed on D. Then parent-state(D) = K, v in improved-spawn.

Proof. We prove that, given a maximal clique D which is not a root, the parent of D in the computational tree is complete(D <pi(D) ) and the vertex used by the algorithm spawn to produce D is pi(D). Since K is the parent of D, we have D = complete(K v ∪ {v}). From the conditions tested on K v and D, we have complete(D <v ) = complete(K v ) = K. Now we only need to prove that v = pi(D). We have that D

Since the candidates are examined in increasing order, when returning from the current child of K, we are able to provide all the remaining children of K. Indeed let v be pi(D): as a consequence of Lemma 6 we know that D was generated from K using candidate v and that K = complete(D <v ). By using the next lemma, we can provide and test all the remaining candidates, i.e. the ones greater than v. Lemma 7. For a given maximal clique K, let cand = {w ∈ x∈K N > (x)\K : w > pi(K)} in spawn and let z 1 , . . . , z r be the sequence of vertices generated by get-next-cand in improved-spawn. Then cand = {z 1 , . . . , z r }.

Proof. We give the proof by induction. The first time get-next-cand is invoked v is pi(K), meaning that z 1 is the minimum element of cand. Let z j be the last vertex generated by Algorithm 3: In-place algorithm for moving heads to the beginning of V Input : G(V, E), with V in degeneracy ordering and E as ordered adjacency lists L1 . . . Ln. Output : G(V, E) with V relabeled in degeneracy ordering so that the j heads are v1, . . . , vj. Observe that the cost of child-exists is dominated by that of the computation of 1) time for each element of N (K v ). Applying Lemma 15, we can conclude that: Lemma 16. Function child-exists can be implemented such that the cumulative cost of all the calls to child-exists(K, v) for a fixed K is O(d) space and Õ(d min{q∆, m}) time.

Iterating over B K . In order to avoid storing B K , we can compute the intersection between N (K v ) and B K iterating over both sets. The iterator for B K works as described in Lemma 14. Since the elements of both N (K v ) and B K are iterated in increasing order, the cost of computing their intersection for each call of child-exists is the sum of the costs of the two iterations. Consider the sum of these costs over all the calls of child-exists: applying Lemma 14 and Lemma 15, we obtain a total cost of Õ(d min{q∆, m} + qd min{qd, n}), since |cand| ≤ min{qd, n}. As a result, we have the following lemma: Lemma 17. Function child-exists can be implemented such that the cumulative cost of all the calls to child-exists(K, v) for a fixed K is O(q) space and Õ(d min{q∆, m} + qd min{qd, n}) time.

The final algorithm corresponds to plugging Algorithm 2 into Algorithm 1, i.e. replacing spawn with improved-spawn. In order to show that the final algorithm takes O(q) or O(d) space as well, we should also perform the setup described in Section 6. Using Algorithm 3 as setup, and applying Fact 1 and Lemmas 12, 16, and 17, we obtain our final result (recall that q

Theorem 18. Let G be an undirected connected graph with n vertices and m edges, whose adjacency lists are ordered and whose vertices are labeled in degeneracy ordering. Let ∆ be the maximum degree of its vertices, q the size of its largest clique, and d its degeneracy. Then there exists an algorithm that lists all the maximal cliques in G that has Õ(m) setup time, O(q) space usage, and Õ(qd(∆ + qd)) delay. The latter bound improves to Õ(qd∆) if space usage is increased to O(d). Space is always sublinear in the size of G. can be found for the iterative version which uses Lemma 16). For each algorithm and for each graph, we report the total time, the maximum delay found while running, and the memory usage (excluding the input size). Note that both ralg2 and alg2 are significantly faster than cn, mu, and cxq. It is worth observing that the results highlight how the delay of ralg2 and alg2 depends on d and q as shown in Theorem 18.

The running times of alg2 are in general higher than ralg2, even though its performance is competitive. On the other hand, alg2 uses the smallest amount of memory, namely always less than 0.03 MiB even when these graphs have hundreds of thousands of vertices and millions of edges. The most striking result is for eu-2005, having more than 850 thousands of vertices and more than 16 millions of edges, where our algorithm uses just 0.02 MiB. Finally, observe that the memory seems to be proportional to d and q, since in-2004 and eu-2005 have relatively higher memory consumption.

For the sake of completeness, we also considered the state of the art for Bron-Kerbosch based algorithms. In particular, we ran the algorithm in [START_REF] Eppstein | Listing all maximal cliques in sparse graphs in near-optimal time[END_REF][START_REF] Eppstein | Listing all maximal cliques in large sparse real-world graphs[END_REF] using the code provided by the authors (we are grateful to them). Even though its cost per solution can be higher than ours and its delay can be exponential, this algorithm is on the average 3.7 times faster than alg2. On the other hand, as this algorithm uses linear memory, its memory consumption is on the average 878.9 times larger than the memory of alg2.