Stefan Balev

Yoann Pigné

Eric Sanlaville

Jason Schoeters

Temporally connected components

Keywords: 2012 ACM Subject Classification Theory of computation → Problems, reductions and completeness, Networks → Network components, Mathematics of computing → Graph algorithms, Mathematics of computing → Paths and connectivity problems temporal graph theory, NP-complete problem, polynomial-time reduction, algorithm, connected component, temporal connectivity

We discuss a variety of extensions of connected components in temporal graphs, focusing on extensions using connectivity over time through temporal paths (or journeys). Starting with components induced by temporal sources or sinks, we build up to components induced by multiple sources or sinks, and eventually components where all vertices are sources and sinks, i.e. temporally connected components. Our contributions mainly include structural results on the number of components, and algorithmic and complexity results of corresponding decision problems.

Introduction

Temporal graphs have become increasingly more popular in the literature over the years, and with good reason. Dynamic settings, whether failure-prone systems or highly mobile entities, which static graphs fail to model, can be modeled naturally with temporal graphs [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF][START_REF] Hayes | A graph model for fault-tolerant computing systems[END_REF][START_REF] Yu | Dynamic evolution of shipping network based on hypergraph[END_REF]. Many problems in temporal graphs can be solved by extending static graph structures and related problems and algorithms into the dimension of time, resulting in various more complicated extensions. The structures considered in this paper use journeys (also called temporal paths) which allow for connectivity over time through increasing time labels on successive edges of the path [START_REF] Casteigts | Sharp thresholds in random simple temporal graphs[END_REF][START_REF] Himmel | Adapting the bron-kerbosch algorithm for enumerating maximal cliques in temporal graphs[END_REF][START_REF] Ibiapina | Mengerian temporal graphs revisited[END_REF][START_REF] Kempe | Connectivity and inference problems for temporal networks[END_REF][START_REF] Klobas | The complexity of computing optimum labelings for temporal connectivity[END_REF]. Concerning the problems, often these become harder in terms of time and/or space complexity [START_REF] Eleni C Akrida | The complexity of optimal design of temporally connected graphs[END_REF][START_REF] Balev | Complexité du problème de Steiner dynamique[END_REF][START_REF] George B Mertzios | Computing maximum matchings in temporal graphs[END_REF]. Naturally, this leads to results considering specific classes of temporal graphs, often restraining the underlying graph (or footprint), approximation results, and/or fixed-parameter tractability results (or, in the negative case, W [START_REF] Eleni C Akrida | The complexity of optimal design of temporally connected graphs[END_REF] or even W [START_REF] Anagnostopoulos | Algorithms on evolving graphs[END_REF] hardness results) [START_REF] Casteigts | Temporal cliques admit sparse spanners[END_REF][START_REF] Crescenzi | Approximating the temporal neighbourhood function of large temporal graphs[END_REF][START_REF] Deligkas | Minimizing reachability times on temporal graphs via shifting labels[END_REF][START_REF] Enright | Counting temporal paths[END_REF][START_REF] Ilcinkas | Exploration of constantly connected dynamic graphs based on cactuses[END_REF][START_REF] Zschoche | The complexity of finding small separators in temporal graphs[END_REF]. Temporal graph theory has also natural links with gossip theory [START_REF] Baker | Gossips and telephones[END_REF][START_REF] Fujita | Neighbourhood gossiping in hypercubes[END_REF][START_REF] Göbel | Label-connected graphs and the gossip problem[END_REF], and with rainbow structures in edge-colored static graphs [START_REF] Bradshaw | A Rainbow Connectivity Threshold for Random Graph Families[END_REF][START_REF] Chen | The complexity of determining the rainbow vertex-connection of a graph[END_REF][START_REF] Krivelevich | The rainbow connection of a graph is (at most) reciprocal to its minimum degree[END_REF].

In temporal graphs, a natural extension of paths exists, in which even though two vertices may admit no path in any of the snapshots, over time they might still be connected thanks to some structures called temporal paths or journeys. More formally, a journey from s to t in G is a path from s to t in the footprint G with non-decreasing labels on successive edges (see Figure 1). We then say s can reach t and t can be reached by s. We denote a journey, or the existence of a journey, from u to v, as u v. Journeys, as opposed to paths, are neither symmetrical nor transitive, i.e. u v and v w does not necessarily imply u w.

The notation u v w implies that journey v w takes place later in time than journey u v (which also implies u w). When a temporal graph G admits journeys from all vertices to all other vertices, the graph is said to be temporally connected, or T C. We use the notation u v for a round-trip journey u v u Besides the footprint, another useful structure concerning temporal graphs is the transitive closure, which represents the reachability (through journeys) of all vertices of the graph.

Formally, the transitive closure of a temporal graph G corresponds to the directed graph

H(G) = (V, A ⊆ V × V ), with A = {(v, v ) : v v }.
Note that this definition introduced by [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF] uses the notion of closure in a temporal sense: as stated previously, u v and v w implies u w only if the second journey takes place later than the first one. So H(G) is not, as usual, the transitive closure of some relation, for instance the relation associated to the existence of journeys between vertex couples, but precisely the graph of this relation. When clear from the context, we simply denote H(G) as H. 1 If for some temporal graph G we have m < n, i.e. the footprint admits multiple connected components V , precomputation allows us to reduce to O(n) cases of temporal graphs G = G[V ] where m ≥ n .

For example, the transitive closure of the temporal graph G 1 from Figure 1 corresponds to a complete bidirectional graph (all arcs in both directions exist) except for arc (t, s) which is missing, meaning the only journey missing for G 1 to be temporally connected is from t to s.

Constructing the transitive closure can be done in time O(n(m log T + n log n)) through n calls of an adaptation of Dijkstra's algorithm [START_REF] Bui | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF], or in time O(max(|E i |)nT ) through an online algorithm gradually building the transitive closure snapshot by snapshot [START_REF] Barjon | Testing temporal connectivity in sparse dynamic graphs[END_REF]. The latter is more efficient in specific cases when the lifetime T = O(n) and when the snapshot density

max(|E i |) = o(m).
For simplicity, we will consider the former time complexity throughout this paper, and we will refer to the adaptation of Dijkstra's algorithm as the temporal Dijkstra algorithm.

Hierarchy of connectivity properties for temporal graphs

In [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], and recently revisited in [START_REF] Casteigts | A Journey Through Dynamic Networks (with Excursions)[END_REF], Casteigts et al. introduce a hierarchy of temporal properties, including among others temporal connectivity, T C. The properties are given mnemonic names using key concepts e.g. J for "journey", and T C for "temporal connectivity".

Superscript adds restraints, for example B meaning "in each bounded time window", and ∀1 meaning "from all vertices to one". This gives rise to properties such as J 1∀ , having a vertex which is connected through journeys to all other vertices, and T C B , each window of some given size ∆2 being temporally connected. The properties of interest for this paper are formally defined in Sections 3 and 4 when we define their corresponding components.

For clarity, we've opted to change some mnemonic names of the hierarchy for shorter ones without superscript (so we may add superscript later on). S for "source" will replace J 1∀ , and since "sink" unfortunately also starts with an S, T for "target" will replace J ∀1 . By slight abuse of notation, we will often use the mnemonic names to denote the property as well as the set of graphs admitting the property.

From connectivity properties to temporal components

The rest of the paper is organized to define and study, for every journey-based temporal property X , the analogue of a connected component corresponding to this property, which we will simply refer to as a X component.

Definition 1 (X component). Given a temporal graph G, a X component is a maximal subset V ⊆ V such that X is respected by V in G.
Note the maximality requirement for V , which mimics the maximality requirement for static connected components. It is natural to look for largest components also in the temporal case.

Theorem 1 can be ambiguous concerning the latter part, since technically X is a property of temporal graphs, not of a set of vertices in a temporal graph. For now, it is sufficient to say that we simply aim to present the difference between X components and closed X components, Theorem 1 and Theorem 2 resp. Also, these definitions are formal and clear when presented using concrete properties in Sections 3 and 4.

Using terminology from [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF][START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF][START_REF] Vernet | A study of connectivity on dynamic graphs: Computing persistent connected components[END_REF], we say a X component V' is closed if journeys between vertices u, v ∈ V necessary for property X , do not use vertices from V \ V . In other words, to verify if V is a closed X component, it suffices to verify the X property on G[V ], and this verification does not depend on the rest of G.

Definition 2 (Closed X component). Given a temporal graph G, a closed X component is a maximal subset V ⊆ V such that X is respected by G[V ].
Open X components are defined as X components in which there exists at least one journey necessary for X which goes outside of the component. Most of the components studied in static graphs are closed (an exception being k-connected components [START_REF] Wen | Enumerating k-Vertex Connected Components in Large Graphs[END_REF] which may be open). We give the following results for X components, and if applicable, also for closed X components.

For each property X , we start by studying the worst-case number of X components, i.e. the maximum number of X components which may exist in a given temporal graph. This can be useful for enumeration and partition problems.

For each property X , the corresponding decision problem X Component is defined as follows.

Definition 3 (X Component decision problem).

Input: temporal graph G, integer k (and integer ∆ if X is a windowed property).

Question: does G admit a X component of size at least k?

Algorithms and complexity results for X Component are presented. As stated in Section 1, depending on property X , some results may already exist in the literature. However we additionally determine the boundary (if one exists) between polynomial-time solvability and N P -hardness depending on the lifetime of the graph. To obtain such results, we modify reductions from the literature or use different reductions altogether.

Regarding hardness implications, Bhadra et al. [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF] give the following argument for T C components and closed T C components, which we generalize for any temporal properties

X 1 , X 2 .
Although X 1 components are a special case of X 2 components, the N P -hardness of X 1 Component does not directly imply that X 2 Component is N P -hard as well. This is because a possible polynomial time algorithm for X 2 Component need only answer the decision problem and not identify the components of size at least k, thus potentially making it difficult to verify if at least one such a component is a X 1 component. Also, the same temporal graph may contain both a X 1 component (of indeterminate size) and a X 2 component of size k, so the decision problem for the latter would always return "yes", ignoring the presence or absence of a X 1 component of size k, thereby leaving its decision problem unsolved. Of course, the other way around, since X 1 components are a special case of X 2 components, if

X 2 Component is N P -hard, then X 1
Component is not necessarily N P -hard either. Since hardness results do not transfer one way or the other, note that this implies that neither do results on polynomial-time solvability.

Regarding hardness proofs, i.e. reductions, we do however use a trick from [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF] making one reduction work for both X Component and Closed X Component, which is to make sure all X components in the transformed instance are closed.

3

One to/from all (S, S B , S D , T , T B , T D )

A temporal source is a vertex u such that all other vertices v in the temporal graph admit a journey u v. The concept is mainly useful to model a network over which one agent, say the leader, can control the entire network, diffusing information, messages or influence throughout the network using peer-to-peer broadcasting [START_REF] Chuzhoy | A new algorithm for decremental single-source shortest paths with applications to vertex-capacitated flow and cut problems[END_REF][START_REF] Kapoor | Examining covid-19 forecasting using spatio-temporal graph neural networks[END_REF][START_REF] Zang | Discovering Multiple Diffusion Source Nodes in Social Networks[END_REF]. The property of having a temporal source is denoted by S.

Definition 4 (S component

). An S component of a temporal graph G is a maximal subset

V ⊆ V such that ∃u ∈ V , ∀v ∈ V , u v in G.
Adding the natural constraint of time windows has mainly two advantages, first a time bound after which one is ensured all other vertices can be reached from the source, and second the possibility for the source to reach other vertices multiple times over the lifetime of the network. The property of having a vertex which is a temporal source for each time window is denoted by S B .

Definition 5 (S B component). An S B component of duration ∆ of a temporal graph G is a maximal subset V ⊆ V such that ∃u ∈ V , ∀t ≤ T -∆ + 1, ∀v ∈ V , u v in G [t,t+∆-1] .
A natural relaxation of the latter allows for any vertex to be the source in a time window, not necessarily the same vertex for all time windows. In other words, the source may be dynamic and change over time. This property is denoted by S D .

Definition 6 (S D component). An S D component of duration ∆ of a temporal graph G is a maximal subset V ⊆ V such that ∀t ≤ T -∆ + 1, ∃u ∈ V , ∀v ∈ V , u v in G [t,t+∆-1] .
Closely related to source vertices are sink vertices, where other vertices are able to reach such a vertex, leading to properties T , T B , and T D . While often studied independently and having its own specific applications such as collecting and analysing data (e.g. [START_REF] Jiang | A wireless sensor network-based monitoring system with dynamic convergecast tree algorithm for precision cultivation management in orchid greenhouses[END_REF][START_REF] Khan | A comprehensive study of data collection schemes using mobile sinks in wireless sensor networks[END_REF][START_REF] Yomo | On-demand data gathering with a drone-based mobile sink in wireless sensor networks exploiting wake-up receivers[END_REF]), we simplify this paper through the following observation. T -.

Proof. Any journey in G from vertex u to v is reversed in G . Thus, a vertex able to reach all vertices in G (or in some G [t,t+∆-1] ) can be reached by all vertices in G (or in some

G [t ,t +∆-1]
) and vice versa.

Theorem 7 allows us to focus only on S components, since any structural result transfers to T components, and algorithmic results transfer too, with a polynomial overhead of O(mT )

to build the reversed graph (but they can be adapted easily without any overhead). The same holds for S B components and T B components, as well as for S D components and T D components.

S components

Lemma 8. S components are necessarily closed.

Proof. In an S component, all vertices on a journey from the source to some other vertex also admit a journey from the source, and are thus by maximality included in the component as well.

Lemma 9.

A vertex can only be a source for one S component.

Proof. If a vertex was a source for two distinct S components, then at least one wouldn't be maximal since their union would result in a larger S component. Lemma 15. A vertex can only be a source for one S B component.

Proof. If a vertex was a source for two distinct S B components, then at least one wouldn't be maximal since their union would result in a larger S B component.

Theorem 16 ( ). The worst-case number of

S B components is n. Theorem 17 ( ). S B Component is solvable in polynomial time O((T -∆)n(m log ∆ + n log n)).
Theorem 18 ( ). The worst-case number of closed S B components is n.

Theorem 19 ( ). Closed S B Component is solvable in polynomial time O(n(n -k)(T - ∆)(m log ∆ + n log n)).

S D components

Some results from S B components transfer for S D components, or give bounds, since S B components are S D components in which the source for every window is the same vertex. Proof. If such a set of vertices were sources for two distinct S D components, then at least one wouldn't be maximal since their union would result in a larger S D component.

Theorem 22 ( ). The worst-case number of S D components is at least n, and at most

min(2 n , n T -∆+1 ). Theorem 23 ( ). S D Component is solvable in time O(n min(k,T -∆+2) (T -∆)k(m log ∆+ n log n)). Theorem 24 ( ). S D Component is NP-complete.
Theorem 25 ( ). The worst-case number of closed S D components is at least n, and at most min(2 n , n T -∆+1 ).

Theorem 26 ( ). Closed

S D Component is solvable in time O(min(2 n , n T -∆+1 )(T - ∆)n(m log ∆ + n log n)). Theorem 27 ( ). Closed S D Component is NP-complete.

All to/from all (T C, T C B , T C )

A graph is said to be temporally connected if there exists a journey from each vertex to every other vertex. In other words, over time, each vertex is able to connect to the whole temporal graph, and is used for example in contexts with multi-hop message passing, distributed mobile agents, or social communication networks [START_REF] Holme | Network reachability of real-world contact sequences[END_REF][START_REF] Kossinets | The structure of information pathways in a social communication network[END_REF][START_REF] Vassilis | Temporal graphs[END_REF].

Definition 28 (T C component). A T C component of a temporal graph G is a maximal subset V ⊆ V such that ∀u, v ∈ V , u v.
Similar to S B , time windows add multiple advantages to temporal connectivity. Gomez et al. suppose a T C B component exists in their work on agreement in dynamic systems in [START_REF] Gómez-Calzado | A connectivity model for agreement in dynamic systems[END_REF].

In [START_REF] Casteigts | Computing parameters of sequence-based dynamic graphs[END_REF], Casteigts et al. present a general framework for computing parameters in temporal graphs, one of which being ∆ for which the given graph is T C B . Closed T C B components are studied by Huyghues-Despointes et al. in [START_REF] Huyghues-Despointes | Forte deltaconnexité dans les flots de liens[END_REF]. They propose polynomial-time algorithms for computing lower and upper bounds on the maximum component size.

Definition 29 (T C B component). A T C B component of duration ∆ of a temporal graph G is a maximal subset V ⊆ V such that ∀v, v ∈ V , ∀t ≤ T -∆ + 1, v v in temporal graphs G [t,t+∆-1] .
Another parameter Casteigts et al. are interested in is the round trip temporal diameter, being the shortest duration for which there exist round trip journeys between every pair of vertices. More generally, round-trip connectivity can represent systems in which feedback or acknowledgements are needed in a connection, such as Transmission Control Protocol (TCP).

Definition 30

(T C component). A T C component of a temporal graph G is a maximal subset V ⊆ V such that ∀u, v ∈ V , u v in G.

T C components

Observation 31. T C components can be open such as shown in Figure 4. Theorem 32 ( ). The worst-case number of T C components is at least 2 0.52 √ n , and at most 2 0.53n . Note (see appendix) that the exact bounds are 3 ( √ n+1+1)/3 and 3 n/3 respectively. We used 2 0.52k < 3 k/3 < 2 0.53k so that results are comparable with results using powers of 2.

n + 1 1 3, n -4 n ... 2, n -3 1, n -2 2, n -3
An algorithm is mentioned by Bhadra et al. [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF] and implemented and experimented on by Nicosia et al. [START_REF] Nicosia | Components in time-varying graphs[END_REF]. To the best of our knowledge, no complexity analysis of this algorithm has been performed.

Theorem 33 ( ). T C Component is solvable in time

O(nm log T + min(n k k 2 , 2 0.25n )).

Bhadra et al. prove that T C Component is NP-complete. They use a reduction from

Clique in which they produce a temporal graph with a lifetime T = 4 (so using labels between 1 and 4 included). This leaves the N P -hardness question open for lifetimes 1 < T < 4 (T = 1 being polynomial-time solvable). We treat the case of T = 2, filling the gap and proving general N P -hardness for T > 1.

Theorem 34 ( ). T C Component is N P -complete, for all constant lifetimes T > 1.

Theorem 35 ( ). The worst-case number of closed T C components is at least 2 0.52 √ n , and at most 2 0.53n .

Theorem 36 ( ). Closed T C Component is solvable in time O(2 n n(m log T + n log n)).

Temporally connected components

Theorem 40 ( ). T C

B Component is solvable in time O((T -∆)n(m log ∆ + n log n) + min(n k k 2 , 2 0.25n )).
Again, since T C components are T C B components by setting window size ∆ = T , NP-hardness transfers. We however prove a more general hardness for T C B Component regarding any constant lifetime and window size.

T C components

Observation 45. T C components can be open, such as shown in Figure 5. Theorem 53 ( ). Closed T C Component is N P -complete, for all constant lifetimes T > 2.

4n+1 4n + 2 ... 1, 2n -1, 2n + 1 2, 2n -2, 2n + 2 3, 2n -3, 2n + 3 n -2, n + 2, 3n -2 n -1, n + 1

Conclusion

Summary of this paper

A first summary of this paper is given in the following

O(n(m log T + n log n)) P S B n O((T -∆)n(m log ∆ + n log n)) P Closed S B n O(n(T -∆)(n -k)(m log ∆ + n log n)) P S D [n, min(2 n , n T -∆+1 )] O(n min(k,T -∆+2) (T -∆)k(m log ∆ + n log n)) NPC Closed S D [n, min(2 n , n T -∆+1 )] O(min(2 n , n T -∆+1 )(T -∆)n(m log ∆ + n log n)) NPC T C [2 0.52 √ n , 2 0.53n ] O(nm log T + min(n k k 2 , 2 0.25n )) NPC (T > 1) Closed T C [2 0.52 √ n , 2 0.53n ] O(2 n n(m log T + n log n)) NPC (T > 1) T C B [2 0.52 √ n , 2 0.53n ] O((T -∆)n(m log ∆ + n log n) + min(n k k 2 , 2 0.25n )) NPC (T &∆ > 1) Closed T C B [2 0.52 √ n , 2 0.53n ] O(2 n (T -∆)n(m log ∆ + n log n)) NPC (T &∆ > 1) T C [2 0.52 √ n , 2 0.53n ] O(n 2 (m log T + n log n) + min(n k k 2 , 2 0.25n )) NPC (T > 2) Closed T C [2 0.52 √ n , 2 0.53n ] O(2 n (n 2 (m log T + n log n)) NPC (T > 2)
Temporal graphs with lifetime T = 1 trivially admit polynomial-time algorithms for all these problems (since they reduce to finding connected components in the static graph), so they are not presented. Note that all these results are to be found in this paper, although some parts were first presented in related works. We also prove T C Component and Closed T C Component can be solved in polynomial time for temporal graphs with lifetime T = 2.

A short discussion about optimisation of windowed components

This paper provided algorithms (polynomial or not) to solve the windowed versions of our problems. Some of these consider treat the windows in the specific order ([

A quick note on parameterised complexity

Among the NP-hard problems in this paper, all but two are para-NP-hard concerning the lifetime parameter, i.e. for some constant value of T the problem is NP-hard. The Proof. In other words, we prove that at most n 2 S components may exist in any temporal graph without isolated vertices, and we prove this is tight. Figure 7 shows a graph family which admits n 2 S components, which by Theorem 54 and Theorem 55 finishes the proof.

... Theorem 56. For a given temporal graph, all S components can be enumerated in time O(nm log T + n 3 ).

Proof. Start by computing the transitive closure H, taking time O(n(m log T + n log n)).

Then, let the set of S components be composed of vertex v with all its out-neighbours in H, for all vertices v ∈ V . Now, some of these S components may be included in others, meaning they may be non-maximal. To remove non-maximal S components, start by sorting the vertices in each S component, taking time O(n 2 log n). Then, for each pair of S components, of which there are O(n 2 ), check whether one is a subset of the other, and remove it if so, which can be done in time O(n). All in all, enumeration of S components can be done in

time O(n(m log T + n log n) + n 2 log n + n 3 ) = O(nm log T + n 3 ).

A.2 S B components

Theorem 16. The worst-case number of S B components is n.

Proof. Theorem 15 implies at most n S B components may exist, which is tight for example for the empty temporal graph. In fact, it is tight even for much denser graphs; a temporal graph with one window of size ∆ containing only empty snapshots is sufficient to obtain n S B components of size 1, meaning even a temporal graph with a complete graph as footprint may attain n S B components.

Theorem 17. S B Component is solvable in polynomial time O((T -∆)n(m log ∆ + n log n)).
+ n log n) + (T -∆)n(m log ∆ + n log n + n(n log n))) = O((T -∆)n(m log ∆ + n log n)).
Theorem 57. For a given temporal graph, all S B components can be enumerated in time apply the temporal Dijkstra algorithm from vertex s to obtain its reachability which is done in time O(min(m, k 2 ) log ∆ + k log k). If for all windows, its reachability covers the whole vertex set S s , then S s is a solution, else it is not. This process is repeated in case the component is not closed and a shrunken component has to be tested which again isn't closed but contains another shrunken component to be tested etc. This can happen at most n -k times, since the size of a component is at most n and we're not interested in components of size less than k. Hence, all together, we obtain

O((T -∆)n(m log T + n log n) + n 3 ).
Theorem 19. Closed S B Component is solvable in polynomial time O(n(n -k)(T - ∆)(m log ∆ + n log n)).

Proof. We propose the following algorithm for

a complexity of O(n(T -∆)(m log ∆ + n log n) + n(n -k)(T -∆)(m log ∆ + n log n)) = O(n(n -k)(T -∆)(m log ∆ + n log n)).
∆)(k(m log ∆ + n log n) + k 2 ) = O((T -∆)k(m log ∆ + n log n)). Theorem 23. S D Component is solvable in time O(n min(k,T -∆+2) (T -∆)k(m log ∆ + n log n)).
Proof. We present two algorithms, the first being the brute force algorithm of testing all possible subsets of vertices of size k, the other a generalization of the algorithm for

S B Component
k 2 = m 1 + n 1 + k 1 . Let's construct the footprint G 2 , initially the empty graph. Suppose V (G 1 ) = {v 1 , v 2 , ..., v n1 }. For each vertex v i ∈ V (G 1 )
, add vertices v i and v i,i with edge {v i , v i,i } to G 2 . We refer to vertices v i in G 2 as original vertices, and to vertices v i,i as satellite vertices. Then, for each edge {v i , v j } ∈ E(G 1 ), add vertex v i,j = v j,i and edges {v i , v i,j }, {v i,j , v j } to G 2 . These edges will allow for v i to reach v j and/or vice versa, depending on the labelling. We refer to vertices v i,j as intermediary vertices. Finally, This concludes the construction of G 2 . Note that n 2 = m 1 + 2n 1 . Concerning λ 2 (see also Figure 8), for each vertex v a ∈ V (G 1 ) with 1 ≤ a ≤ n 1 , we create a temporal graph G va using labels 3a -2 and 3a -1. Afterwards, we take the union of these temporal graphs and add some extra labels to all edges to obtain G 2 . For now, construct each G va by placing label 3a -1 on all edges {v i , v i,a } and on the background edges, and label 3a -2 on all other edges. Note that the intermediary vertices allow for v i and v j to reach each other, except for temporal graphs G vi in which only v i can reach v j , and vice versa for G vj . Now, let G 2 be the union of all G va , for all 1 ≤ a ≤ n 1 , and add labels 3a on all edges, for all 1 ≤ a ≤ n 1 -1.

∀v i,j , v h,k ∈ G 2 , add edges {v i,j , v h,k } (
This concludes the polynomial-time transformation.

G 1 v 2 v 3 v 4 v 1 G 2 =
∪G va and add labels 3, 6 and 9 to all edges.

v 2 v 1 v 4 v 3 G v1 = G 2[1,2] v 1,2 v 2,4 v 2,3 v 3,4 v 1,4 v 1,1 v 2,2 v 3,3 v 4,4 G v2 = G 2[4,5] G v4 = G 2[10,11] G v3 = G 2[7,8]
Figure 8 Example of transformation from a Clique instance graph G1 to a S D Component instance temporal graph G2. For visibility, for all Gv a , blue full edges correspond to edges with label 3a -2, red dashed edges to edges with label 3a -1, and orange dotted edges to background edges with label 3a -1. Also for visibility, not all background edges are represented.

Temporally connected components

Now let's show that the instance of Clique, being (G 1 , k 1 ), is positive if and only if the

instance of S D Component, being (G 2 , ∆ 2 , k 2 ), is positive. (G 1 , k 1 ) is positive =⇒ (G 2 , ∆ 2 , k 2 ) is positive: Suppose that a clique exists in G 1 of size k 1 , composed of vertices V = v h , v h+1 , ...v h+k1 .
Note that in all windows of size ∆ 2 = 2 in G 2 , either the window contains 3a for some a and thus all vertices can reach each other in this window using only edges with label 3a, or the window does not contain 3a in which case it must contain 3a -1, meaning m 1 + n 1 vertices can reach each other by using the background edges with label 3a -1. In either case, this implies a S D component of size at least m 1 + n 1 must exist in G 2 . To prove a larger S D component exists, of size k 2 = m 1 + n 1 + k 1 , we can ignore windows containing 3a, since in these windows a S component of size n 2 ≥ k 2 exists and can thus be shrunk to adapt to any S D component suitable for the other windows. The remaining windows correspond exactly to the temporal graphs G vi for all 1 ≤ i ≤ n 1 . Now, all edges {v i , v j } composing our clique in G 1 exist by definition as edges {v i , v i,j } and {v i,j , v j }, with either labels 1 and 1 resp. or 1 and 2 resp., or 2 and 1 resp. in temporal graphs G va . Let us iterate over these temporal graphs (with variable b), in which two cases are distinguished:

If the edges of the clique in G 1 are all transformed in edges with label 1 in the temporal graph G v b , then vertex v h is a source able to reach V in G v b , for a total of at least

m 1 + n 1 + k 1 = k 2 vertices.
1 + n 1 + k 1 = k 2 existing in G 2 follows directly. (G 2 , ∆ 2 , k 2 ) is positive =⇒ (G 1 , k 1 ) is positive:
Again, observe that any S D component in G 2 must contain the m 1 + n 1 vertices which the background edges cover. Let us look at the other k 2 -(m 1 + n 1 ) = k 1 vertices. These vertices must be v i for some i (since vertices v i,j are already contained through the background edges), meaning they correspond directly to vertices v i of G 1 . Let's denote these vertices as V .

Consider temporal graph G v b for some v b , and observe that any vertex v i can, by construction, only reach other vertices v j by traversing intermediary vertices v i,j . Also, at most one original vertex v j can be reached by a journey starting at a vertex v i . This implies all vertices in V must be linked pairwise through intermediary vertices in G v b . By construction, intermediary Proof. Consider Figure 9, in which an infinite family of temporal graphs is presented. For each of these graphs, say G, a closed S D component exists of size n, with any vertex as source for both windows. However, no (non-maximal) closed S D component exists of size

vertices between vertices V can only exist in G v b if the corresponding edges exist between V in G 1 . Thus a clique of size |V | = k 1 must exist in G 1 .
O((T -∆)(k(min(m, k 2 ) log ∆ + k log k) + k 2 ) = O(k(T -∆)(min(m, k 2 ) log ∆ + k log k)).
n -1, since considering any such set of vertices V would result in either G(G[V ] [1,∆] ) or G(G[V ] [2,∆+1]
) to be disconnected, implying no temporal source can exist in that window.

1 ∆ + 1 ... 1, ∆ + 1 1, ∆ + 1 1, ∆ + 1 1, ∆ + 1 1, ∆ + 1 1 1 1 ... 1 1 1 ∆ + 1 ... ∆ + 1 ∆ + 1 ∆ + 1 ∆ + 1 ∆ + 1
O(min(2 n , n T -∆+1 )(T -∆)n(m log ∆ + n log n)). Theorem 27. Closed S D Component is NP-complete.
Proof. To prove Closed S D Component is in NP, we show how to verify a solution V ⊆ V in polynomial time. For every window [t, t + ∆ -1] , compute the transitive closure of temporal graph G[V ] [t,t+∆-1] and check if at least one source, i.e. a vertex able to reach all others, exists. If this is the case in all windows, then V is a solution, and else it is not.

To prove NP-hardness, the same reduction as in Theorem 24 is used, since all the S D components in the transformed instance of the reduction are closed S D components.

A.4 T C components

Theorem 32. The worst-case number of T C components is at least 2 0.52 √ n , and at most 2 0.53n .

Proof. The lower bound has been obtained by Casteigts et al. [START_REF] Casteigts | A Journey Through Dynamic Networks (with Excursions)[END_REF] by adapting a Moon and Moser graph [START_REF] Moser | On cliques in graphs[END_REF] on n vertices and n 2 -n edges admitting 3 n/3 cliques. Every edge of this graph is replaced by a semaphore gadget (see Figure 10) creating a temporal graph on

N = n 2 -2n vertices in which every initial clique is now a T C component, obtaining a total of 3 n/3 = 3 ( √ N +1+1)/3 > 3 √ N /3 > 2 0.52 √ N T C components. (a)
-→

Figure 10 A graph with at least 2 0.52 √ n T C components is constructed by taking a Moon and Moser graph (left) admitting 3 n/3 cliques, and replacing each edge with a semaphore gadget (right). All initial cliques now correspond to T C components, which are maximal when including semaphore vertices.

Outside of the trivial upper bound of 2 n , a better upper bound can be obtained as follows.

Since T C components of G correspond to bidirectional cliques in the transitive closure of G (see [START_REF] Bhadra | Computing multicast trees in dynamic networks and the complexity of connected components in evolving graphs[END_REF]), modify the transitive closure as follows. For all arcs (u, v) such that (v, u) exists as well, replace both arcs by one (undirected) edge {u, v}. All other arcs are removed. The corresponding graph is undirected and cliques in this graph correspond to T C components.

By Moon and Moser [START_REF] Moser | On cliques in graphs[END_REF], at most 3 n/3 cliques can exist in undirected graphs, which implies the same upper bound 3 n/3 < 2 0.53n holds for T C components in temporal graphs. Proof. We use a specific version of Clique, in which one has to decide if a clique of size k = n 3 exists in a given graph on n vertices. This specific problem was indirectly proven N P -hard by Erickson [START_REF] Erickson | Algorithms[END_REF] through his reduction from 3-SAT to IndependentSet (in [START_REF] Karp | Reducibility among Combinatorial Problems[END_REF],

Karp reduces SAT to Clique in a similar fashion). Let us refer to this problem as n 3 Clique.

We show how to reduce n 3 Clique to T C Component in polynomial time. Given a graph G = (V, E) for the n 3 Clique problem, create temporal graph G with (initially) the same vertex set V . For each edge (u, v) ∈ E, add a semaphore gadget between u and v in G, with semaphore "intermediary" vertices uv and vu (see Figure 11). See Figure 12 for an example of how to construct G.

{v i v j : v i , v j ∈ K, v i = v j }. Let's refer to this set of vertices in G as V , which is of size k + 2 k(k-1) 2 = k 2 . V is a T C component, since all
vertices can reach each other: a vertex v i can reach all other vertices v j through journey (v i , v i v j , v j ) using time steps

(1, 2) respectively; a vertex v i can reach all intermediary vertices v j v k , through journey

(v i , v i v k , v k , v j v k )
with time steps (1, 2, 2) respectively;

an intermediary vertex v i v j can reach all vertices v k through journey (v i v j , v i , v i v k , v k ) using time steps (1, 1, 2) respectively;

an intermediary vertex v i v j can reach all other intermediary vertices v k v through journey

(v i v j , v i , v i v , v , v k v ) using time steps (1, 1, 2, 2) respectively. T C Component =⇒ n 3 Clique If a T C component V of size k 2 = n 2 9 exists in G, then consider all vertices K = V ∩ V .
Trivially |K| > 0, furthermore |K| > 1 since otherwise the lone vertex v ∈ K is part of a T C component of size at most 2∆ + 1 (including all adjacent intermediary vertices), which leads to the asymptotic contradiction k 2 = n 2 9 ≤ 2∆ + 1 < 2n + 1. We prove that K forms a clique of size k in G:

for all pairs of vertices v i , v j ∈ K, intermediary vertex v i v j (resp. v j v i ) must be included in V , since otherwise no journey v i v j (resp. v j v i ) exists in V ; for all v k ∈ K, vertices v k v (resp. v v k ) cannot reach (resp. be reached by) vertices v i v j where v i , v j ∈ V , thus v k v ∈ V (resp. v v k ∈ V );
since V is composed solely of vertices K and all their corresponding intermediary vertices, we have that Proof. Consider Figure 13, in which an infinite family of temporal graphs is presented.

|V | = k 2 = |K| + 2
) log T + k log k) + k 2 ) = O(k(min(m, k 2 ) log T + k log k)).
For each of these graphs, say G, a closed T C component exists of size n. However, no (non-maximal) closed T C component exists of size n -1, since considering any such set of vertices V \ u i (resp. v i ) would result in v i (resp. u i ) not being able to reach any vertex v j (resp. u j ). The upper bound is obtained in a similar manner as for Theorem 32. Start by creating an adaptation of the transitive closure, in which an arc (u, v) is present if and only if a journey exists from u to v in every window of size ∆. (This can be computed easily using temporal Dijkstra algorithms from [START_REF] Bui | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF] in each windowed graph.) Then, for all arcs (u, v) such that (v, u) exists as well, replace both arcs by one (undirected) edge {u, v}. All other arcs are removed. The corresponding graph is undirected and cliques in this graph correspond to T C B components. By Moon and Moser [START_REF] Moser | On cliques in graphs[END_REF], at most 3 n/3 cliques can exist in undirected graphs, which implies the same upper bound 3 n/3 < 2 0.53n holds for T C B components in temporal graphs. Proof. The lower bound can be obtained as follows. Take a Moon and Moser graph [START_REF] Moser | On cliques in graphs[END_REF] on n vertices and n 2 -n edges admitting 3 n/3 cliques. Every edge of this graph is replaced by a semaphore gadget (see Figure 10) creating a temporal graph on N = n 2 -2n vertices in which every initial clique is now a T C component, obtaining a total of 3 n/3 > 2 0.52

1 1 1 1 1 2 2 2 2 2 2 ... u 1 u 2 u 3 u n 2 -1 u n 2 v 1 v 2 v 3 v n 2 -1 v n 2
Theorem 40. T C B Component is solvable in time O((T -∆)n(m log ∆ + n log n) + min(n k k 2 , 2 0.25n )).
√ N T C components. (a) -→ 2 1, 3 2 1, 3 (b)
Figure 14 A graph with at least 2 0.52 √ n T C components is constructed by taking a Moon and Moser graph (left) admitting 3 n/3 cliques, and replacing each edge with a semaphore gadget (right). All initial cliques now correspond to T C components, which are maximal when including semaphore vertices.

Outside of the trivial upper bound of 2 n , a better upper bound can be obtained as follows.

Consider the following adaptation of the transitive closure: instead of adding an arc between vertices u and v when a journey exists, add an arc when a round trip exists. By contradiction, let us suppose one such a T C component exists, say V . For any two vertices u, v ∈ V , if a journey using only labels 1 (resp. 2) does not exist between u and v, then a journey using only labels 2 (resp. 1) must exist between u and v (or V would not be a T C component). Let us simplify this as a graph G with a copy of V in which an edge with label i is drawn between vertices u and v if the corresponding journey between u and v uses only labels i. G is thus a complete graph with some arbitrary labelling of one label per edge, being either 1 or 2. We finish by showing that in G there is necessarily a spanning structure using only label 1, or using only label 2, implying that in fact V is not a T C component needing both labels 1 and 2, as a spanning structure using only labels 1 or only labels 2 exists which is sufficient for T C .

G contains a spanning structure using only labels 1 or only labels 2:

We prove this property by induction. A K 2 graph trivially admits such a spanning structure. Now, if a K n graph has this property, suppose w.l.o.g. that the spanning structure has only labels 1. Adding a vertex so as to obtain a K n+1 implies adding n edges connecting this vertex to the other vertices. To avoid having this property in the newly constructed K n+1 , none of these edges can have label 1 (since otherwise a spanning structure with only labels 1 exists), but they cannot all have label 2 either (since otherwise a spanning structure with only labels 2 exists), which is impossible.

Theorem 49. T C Component is N P -complete, for all constant lifetimes T > 2.

Figure 1

 1 Figure 1Example of temporal graph G1 (presented in the compact representation), with two journeys (in red) but no static path from vertex s to vertex t in any of the snapshots.

Lemma 7 .

 7 T (resp. S, T B , S B , T D , S D ) components in temporal graph G = (G, λ) of lifetime T correspond to S (resp. T , S B , T B , S D , T D ) components in temporal graph G = (G, λ ) of lifetime T , where ∀e ∈ E(G), λ (e) = ∈λ(e)

Figure 2 A

 2 Figure 2 A graph family admitting an open S B component for ∆ = 2 (in dashed and red with vertex s as source) and an open T B component for ∆ = 2 (in dashed and red with vertex t as sink).

Observation 20 .

 20 Even S D components where sources change between successive windows can be open, such as shown in Figure 3.

Figure 3 A

 3 Figure 3 A graph family admitting an open S D component for ∆ = 2 (in dashed and red with vertex s as source for windows [odd, even] and t as source for windows [even, odd]).

Figure 4 A

 4 Figure 4 A graph family admitting an open T C component (in dashed and red).

Bhadra

  et al. also prove Closed T C Component is N P -complete through the same reduction as for T C Component. We use the same trick to show Closed T C Component is NP-complete for all constant lifetimes T > 1. Theorem 37 ( ). Closed T C Component is N P -complete, for all constant lifetimes T > 1.

4. 2

 2 T C B components Lemma 38. T C B components can be open. Proof. Since T C components are T C B components for the specific setting of ∆ = T , Theorem 32 transfers directly. Theorem 39 ( ). The worst-case number of T C B components is at least 2 0.52 √ n and at most 2 0.53n .

Theorem 41 (

 41 ). T C B Component is N P -complete, for all constant lifetimes T > 1 and window sizes ∆ > 1. Theorem 42 ( ). The worst-case number of closed T C B components is at least 2 0.52 √ n and at most 2 0.53n . Theorem 43 ( ). Closed T C B Component is solvable in time O(2 n (T -∆)n(m log ∆ + n log n)). Theorem 44 ( ). Closed T C B Component is N P -complete, for all constant lifetimes T > 1 and window sizes ∆ > 1.

Figure 5

 5 Figure 5 Graph family admitting an open T C component (in red and dashed).

Theorem 46 (

 46 ). The worst-case number of T C components is at least 2 0.52 √ n , and at most 2 0.53n .Theorem 47 ( ). T C Component is solvable in timeO(n 2 (m log T +n log n)+min(n k k 2 , 2 0.25n )).Outside of the trivial case of lifetime T = 1, T C Component can be solved in polynomial time for lifetime T = 2 as well. Theorem 48 ( ). T C Component is solvable in polynomial time O(n + m) on temporal graphs with constant lifetimes T ≤ 2. Theorem 49 ( ). T C Component is N P -complete, for all constant lifetimes T > 2. Theorem 50 ( ). The worst-case number of closed T C components is at least 2 0.52 √ n , and at most 2 0.53n . Theorem 51 ( ). Closed T C Component is solvable in time O(2 n (n 2 (m log T + n log n)). Theorem 52 ( ). Closed T C Component is solvable in polynomial time O(n + m) on temporal graphs with constant lifetimes T ≤ 2.

Figure 6

 6 Figure 6Example graph family for which Theorem 54 does not induce an equality between the number of S components (only one exists composed of all vertices with source either u or v) and the number of locally minimum edge sets (two such sets exist: {u, v} and {s, t}).

Figure 7 A

 7 Figure 7 A graph family with n 2 S components. A component with its corresponding source is marked in red.

Proof.

  We propose the following algorithm for S B Component. Start by enumerating the S components of the windowed temporal graph G [1,∆] , which by Theorem 56 can be done in time O(nm log ∆ + n 3 ). However, we are not interested in maximal S components, so the added O(n 3 ) can be removed. Thus, we enumerate S components, some of which may not be maximal, in time O(n(m log ∆ + n log n)). Keep only those of size at least k. These are candidate components for S B components. Let us denote these candidate components as S s by their unique corresponding source vertex s (Theorem 9). Then, for each windowed temporal graph G [t,t+∆-1] , of which there are O(T -∆), obtain their S components in the same manner, again in time O(n(m log ∆ + n log n)

Proof.Theorem 18 .

 18 Run the algorithm from Theorem 17 and at the end add the verification and removal of non-maximal S B components, doable as in Theorem 56 in time O(n 3 ), for a total of O((T -∆)n(m log T + n log n) + n 3 ). The worst-case number of closed S B components is n. Proof. Theorem 16 directly adapts for closed S B components, since n S B components of size 1 are necessarily closed. Lemma 58. Verifying a solution vertex subset S s of source s and of size k for Closed S B Component takes time O((T -∆)(min(m, k 2 ) log ∆ + k log k)). Proof. For each windowed temporal subgraph G[S s ] [t,t+∆-1] , of which there are O(T -∆),

A. 3

 3 S D components Theorem 22. The worst-case number of S D components is at least n, and at most min(2 n , n T -∆+1 ). Proof. The lower bound comes from Theorem 18, with an example being the empty temporal graph. For the upper bounds, since S D components are subsets of vertices which may intersect, at most 2 n S D components may exist. By Theorem 21, representing components through their sources, i.e. ordered sets of vertices (one source per window), another bound of n T -∆+1 is found. Lemma 59. Verifying a solution vertex subset V of size k for S D Component takes time O((T -∆)k(m log ∆ + n log n)). Proof. For each window [t, t + ∆ -1], of which there are T -∆, one constructs a partial transitive closure H of G [t,t+∆-1] in which only reachability for the vertices V is computed. This takes time O(k(m log ∆ + n log n)). For each induced subgraph H [V ], checking if a vertex with outdegree k -1 exists takes time O(k 2 ). In total, this takes time O((T -

Theorem 24 .

 24 S D Component is NP-complete. Proof. Theorem 59 proves S D Component is in NP. To prove NP-hardness, we give a polynomial-time reduction from Clique to S D Component, i.e. we show how to transform any instance of Clique to an instance of S D Component such that the instance of Clique is positive if and only if the instance of S D Component is positive. Given an instance of Clique, being a graph G 1 of n 1 vertices and m 1 edges and an integer k 1 , we describe the following polynomial-time transformation to an instance of S D Component, being a temporal graph G 2 = (G 2 , λ 2 ) of lifetime T 2 and integers ∆ 2 and k 2 . Set T 2 = 3n 1 -1, ∆ 2 = 2 and

  essentially creating a clique of all intermediary and satellite vertices, of size m 1 + n 1 ). Let us refer to these last edges as the background edges.

  If some edges of the clique in G 1 are transformed into edges with label 2 in the temporal graph G v b , then v b must be a part of the clique in G 1 , since by definition only adjacent edges to v b are transformed into edges with label 2 in G v b (outside of background edges). Also, v b (and only v b amongst the original vertices) corresponds to a source able to reach V in G v b , for a total of at least m 1 + n 1 + k 1 = k 2 vertices. In both cases, and thus for all G va , a S component exists containing the aforementioned m 1 + n 1 vertices, as well as the k 1 vertices from the clique in G 1 . The result of a S D component of size m

Theorem 25 .

 25 The worst-case number of closed S D components is at least n, and at most min(2 n , n T -∆+1 ). Proof. The lower bound from Theorem 22 works as S D components of size 1 are closed. The upper bounds transfer directly from Theorem 22. Lemma 60. Verifying a solution vertex subset V of size k for Closed S D Component takes time O((T -∆)k(min(m, k 2 ) log ∆ + k log k)). Proof. For each window [t, t + ∆ -1], of which there are T -∆, constructing the transitive closure of G[V ] [t,t+∆-1] takes time O(k(min(m, k 2 ) log ∆+k log k)). In each transitive closure, checking if a vertex with outdegree k -1 exists takes time O(k 2 ). In total, this takes time

Lemma 61 .

 61 The existence of a closed S D component of size > k does not necessarily imply the existence of a (non-maximal) closed S D component of size k.

Figure 9

 9 Figure 9 Temporal graph family in which a closed S D component of size n exists but no nonmaximal component of size n -1 exists. The temporal graphs corresponding to time window [1, ∆] and time window [2, ∆ + 1] are shown in the middle and on the right respectively.

Theorem 33 .

 33 T C Component is solvable in time O(nm log T + min(n k k 2 , 2 0.25n )).Proof. The algorithm starts by constructing the transitive closure of the input temporal graph. This is done in time O(n(m log T + n log n)). Then, it searches for bidirectional cliques (a subset of vertices with arcs in both directions between vertices) in the transitive closure. This has the same asymptotic complexity as searching for cliques. Since we're interested in cliques of size at least k, the brute force algorithm of testing each subset of size k runs in time O(n k k 2 ). Also, one can obtain a maximum-size clique in time O(2 n/4 )[START_REF] John M Robson | Finding a maximum independent set in time o (2n/4)[END_REF]. All together,T C Component can thus be solved in time O(n(m log T + n log n) + min(n k k 2 , 2 n/4 )) = O(nm log T + min(n k k 2 , 2 0.25n )).Theorem 34. T C Component is N P -complete, for all constant lifetimes T > 1.

Figure 11 Figure 12 9 exists in G. n 3

 111293 Figure[START_REF] Casteigts | Temporal cliques admit sparse spanners[END_REF] An edge is replaced by a semaphore gadget, adding two intermediary vertices.

Lemma 63 .

 63 The existence of a closed T C component of size > k does not necessarily imply the existence of a (non-maximal) closed T C component of size k.

Figure 13

 13 Figure 13 Temporal graph family in which a closed T C component of size n exists but no non-maximal component of size n -1 exists.

Theorem 44 .

 44 Closed T C B Component is N P -complete, for all constant lifetimes T > 1 and window sizes ∆ > 1.Proof. By Theorem 64, a vertex subset can be verified to be a solution for Closed T C B Com-ponent in time O((T -∆)n(m log ∆ + n log n)). Closed T C B Component is thus in NP.In the reduction used in Theorem 41, all T C B components in the transformed instance are closed. This suffices to prove that Closed T C B Component is NP-hard, for any constant lifetime T > 1 and window size ∆ > 1.A.6 T C componentsTheorem 46. The worst-case number of T C components is at least 2 0.52 √ n , and at most 2 0.53n .

  (Detecting round trips between all pairs of vertices is easily done adapting the temporal Dijkstra algorithm from [46].) By definition, T C components of G correspond to bidirectional cliques in this adapted transitive closure of G. Further modify the transitive closure as follows. For all arcs (u, v) such that (v, u) exists as well, replace both arcs by one (undirected) edge {u, v}. All other arcs are removed. The corresponding graph is undirected and cliques in this graph correspond to T C components. By Moon and Moser [41], at most 3 n/3 cliques can exist in undirected graphs, which implies the same upper bound 3 n/3 < 2 0.53n holds for T C components in temporal graphs. Theorem 47. T C Component is solvable in time O(n 2 (m log T +n log n)+min(n k k 2 , 2 0.25n )).

Proof.

  We start by constructing a modified version of the transitive closure H, where an arc (u, v) represents u v instead of u v. Initialize H with vertex set V . For all pairs of vertices, of which there are O(n 2 ), do the following. Apply the temporal Dijkstra algorithm from [46] starting from u to obtain the smallest label at which v is reached from u through a journey, suppose label t. If v is unreachable from u, suppose t = ∞. This takes time O(m log T + n log n). Then, if t = ∞, on temporal graph G [t,T ] , apply again the temporal Dijkstra algorithm to check if u is reachable from v. This again takes time O(m log T +n log n). If t = ∞ and if u is reachable from v in G [t,T ] , then add arc (u, v) to H. Apply the same process in the other direction to check if v u. After having done this for all pairs of vertices, modify H as follows. For all arcs (u, v) such that (v, u) exists as well, replace both arcs by an (undirected) edge {u, v}. Remove all other arcs. H is now an undirected graph in which cliques correspond to T C components. Since we're interested in cliques of size at least k, the brute force algorithm of testing each subset of size k runs in time O(n k k 2 ). Also, one can obtain a maximum-size clique in time O(2 n/4 ) [43]. All together, T C Component can thus be solved in time O(n 2 (m log T + n log n) + min(n k k 2 , 2 0.25n )). Theorem 48. T C Component is solvable in polynomial time O(n + m) on temporal graphs with constant lifetimes T ≤ 2. Proof. The case of T = 1 trivially reduces to finding connected components in the snapshot, doable in time O(n + m).For the case of T = 2, note that three possible T C components can exist. The first (resp. second) type of T C components are those which use only labels 1 (resp. 2). These T C components correspond to connected components in the corresponding snapshot, and can thus be computed in time O(n + m) as well. The third, and final, type of T C components use both labels 1 and 2. We continue by proving such T C components do not exist, finishing the proof.

Theorem 52 .T > 2 .

 522 Closed T C Component is solvable in polynomial time O(n + m) on temporal graphs with constant lifetimes T ≤ 2. Proof. In Theorem 48, we prove that all T C components in temporal graphs of lifetime T ≤ 2 correspond to connected components in G 1 or G 2 . Connected components are necessarily closed, thus all T C components in temporal graphs of lifetime T ≤ 2 are necessarily closed. Since T C Component can be solved in time O(m + n) on such temporal graphs, Closed T C Component can be solved in time O(m + n) as well. Theorem 53. Closed T C Component is N P -complete, for all constant lifetimes Proof. By Theorem 65, a vertex subset can be verified to be a solution for Closed T C Component in time O(k 2 (min(m, k 2 ) log T + k log k)). Closed T C Component is thus in NP. In the reduction used in Theorem 49, all T C components in the transformed instance are closed. This suffices to prove that Closed T C Component is NP-hard, for any constant lifetime T > 2.

  We note this order isn't necessary, in the sense that the result would remain unchanged if it considered the time windows in other orders. A consequence potentially useful for optimisation is that one could reorder the time windows in the most "favorable" way.For example, for S B , start with the window in which the corresponding temporal graph may have few and small candidate components, and start the intersection process with windows in which the corresponding temporal graphs may have very distinct S components from the candidate components. Of course, theoretically this would only be useful if such an estimation and reordering of time windows could be done in time O((T -∆)(n(m log ∆ + n log n))) as well, and even then practically this may still induce a significant change in running time.Another possible optimisation concerns some bounded versions of problems related to T C,

1, ∆], [2, ∆ + 1], ...[T -∆ + 1, T ]).

where transitive closures are computed for each time window. Can one do better by computing a modified transitive closure over the whole graph, which iteratively keeps track of how old journeys' starting dates are, and removes them over time if too old? Our first investigations did not allow to show this idea brings a breakthrough.

Both of these directions we leave as open research avenues in this paper.

  ). Denote these S components as S s [t, t + ∆ -1]. For each candidate component S s , of which there are O(n), update S s by setting it to the intersection of S s and S s [t, t + ∆ -1] which is doable in time O(n log n). Remove S s from the candidate components if its size is less than k. If no candidate components remain at some point, the instance is negative, otherwise it is positive. All in all, this gives a total time complexity of O(n(m log ∆

  Closed S B Component. Run the algorithm for S B Component. At the end of the algorithm, the set of candidates contains all S B components S s of size at least k. For all S s , test if it is closed, i.e. if for all t ≤ T -∆ + 1, S s is an S component of temporal graph G[S s ] [t,t+∆-1] . If some component is, then the instance is positive. If however S s is open, meaning at some time t ≤ T -∆ + 1, vertex s cannot reach all vertices in G[S s ] [t,t+∆-1] , then S s can be shrunk down to contain only the reachable vertices in G[S s ] [t,t+∆-1] . This shrunken down S s can now be tested again: if it is of size at least k and closed, then the instance is positive, and if not we can again shrink S s etc. If no closed S B component remains of suitable size, then the instance is negative. The algorithm for S

B Component runs in time O((T -∆)n(m log ∆ + n log n)), after which O(n) candidate components are to test whether they contain a large enough closed S B component. For each of these, testing if they are closed, takes time O((T -∆)(m log ∆ + n log n)) by Theorem 58.

  . Let us start by analysing the brute force algorithm first. For all possible Concerning the generalization of the algorithm for S B Component, only one change needs to be made. Instead of shrinking candidate component S s at every window by taking the union with S s [t, t + ∆ -1], we will need to instead shrink the candidate component with all S v [t, t + ∆ -1] for all v ∈ S s (which could all correspond to a source for that time window),

	subsets of vertices of interest, of which there exist n k = O(n k ), we verify if it is a suitable
	solution. By Theorem 59, one verification takes time O((T -∆)k(m log ∆+n log n)), meaning
	the brute force algorithm runs in time O(n k (T -∆)k(m log ∆ + n log n)).

splitting a candidate component up into potentially O(n) distinct components every time window. A result of this is that at every time window [t, t + ∆ -1], not O(n) candidate components S s exist from previous windows, but at most n t = O(n T -∆+1 ) candidate components S (s,t,u,...,v) . Analysing the complexity gives O(n T -∆+1 n(T -∆)(m log ∆ + n log n)).

  |K|(|K|-1) 2 = |K| 2 , leading to |K| = k;finally, since all intermediary vertices of K are present in V which can only be created through a semaphore gadget, which in turn can only be created if a corresponding edge is present in G, K forms a clique in G.

	Theorem 35. The worst-case number of closed T C components is at least 2 0.52	√	n , and at
	most 2 0.53n .
	Proof. Theorem 32 directly adapts for closed components, as the components obtained by
	the lower bound's construction are closed.

Lemma 62. Verifying a solution vertex subset V of size k for Closed T C Component

takes time O(k(min(m, k 2 ) log T + k log k)).

Proof. To verify a solution V , we construct the transitive closure of temporal graph G[V ] and check if it is a (bidirectional) complete graph, doable in time O(k(min(m, k

2

In this paper, ∆ will by default be used to denote the size of a time window, and ∆(G) for the maximum degree of a static graph G.

= |K| 2 , leading to |K| = k; finally, since all intermediary vertices of K are present in V which can only be created through a semaphore gadget, which in turn can only be created if a corresponding edge is present in G, K forms a clique in G.

A Auxiliary proofs

A.1 S components Theorem 11. The worst-case number of S components is n.

Proof. Theorem 9 implies that at most n S components can exist, which by Theorem 10 is tight when considering the trivial case of the empty temporal graph, i.e. a temporal graph composed of empty graph snapshots G i = (V, ∅).

For Theorem 12, we establish a relation between S components and locally minimum label edge sets, i.e. connected edge sets sharing a label which have no incident edges with lower labels other than themselves.

Lemma 54. The number of S components is at most the number of locally minimum edge sets in a temporal graph without isolated vertices.

Proof. For any locally minimum label edge set E = {{u 1 , u 2 }, ...{u j , u k }}, observe that S components S ui with source u i ∈ V (E ) are identical (in terms of their vertex set), since all vertices u i can reach all vertices reachable by all other vertices of E through the locally minimum label edge set. Note that there is not necessarily equality for Theorem 54, for example when one component induced by a locally minimum label edge set is included in another, such as shown in Figure 6.

Lemma 55. At most n 2 locally minimum label edge sets may exist in any temporal graph, which is tight.

Proof. Since locally minimum label edge sets cannot be incident by definition, and cover at least two vertices each, at most n 2 locally minimum label edge sets exist in any graph. This is shown tight as follows. Take a complete graph on n vertices K n = (V, E) without any labels. Now, take a maximum matching in K n and assign small labels to it, and to the rest of the edges, either assign large labels or remove these edges. The result is a temporal graph with exactly n 2 locally minimum label edge sets, corresponding to the maximum matching's n 2 edges.

Temporally connected components

Proof. For all windowed temporal graphs Proof. For each window [t, t + ∆ -1], compute the transitive closure

all vertices can reach each other and then reach back: a vertex v i can reach all other vertices v j and back through journey

using time steps (1, 2, 2, 3) respectively; a vertex v i can reach all intermediary vertices v j v k and back through journey

with time steps (1, 2, 2, 2, 2, 3) respectively;

an intermediary vertex v i v j can reach all vertices v k and back through journey

using time steps (1, 1, 2, 2, 3, 3) respectively;

an intermediary vertex v i v j can reach all other intermediary vertices v k v and back through journey

T

Trivially |K| > 0, furthermore |K| > 1 since otherwise the lone vertex v ∈ K is part of a T C component of size at most 2∆ + 1 (including all adjacent intermediary vertices), which leads to the asymptotic contradiction k 2 = n 2 9 ≤ 2∆ + 1 < 2n + 1. We prove that K forms a clique of size k in G:

for all intermediary vertices v j v k : v j ∈ K, v k ∈ K (thus having labels 1 and 3), round trip

since V is composed solely of vertices K and all their corresponding intermediary vertices, we have that

Temporally connected components Proof. Consider Figure 15, in which an infinite family of temporal graphs is presented.

For each of these graphs, say G, a closed T C component exists of size n. However, no (non-maximal) closed T C component exists of size n -1, since considering any such set of vertices V \ u i (resp. v i ) would result in v i (resp. u i ) not being able to reach any vertex v j (resp. u j ) and back. Proof. We present the brute force algorithm. Due to Theorem 66, we know it may not be sufficient to verify only the subsets of size exactly k; we may need to verify all subsets of size at least k, of which there exist O(2 n ). By Theorem 65, verifying such a subset requires O(n 2 (m log T + n log n)) time. In total, the brute force algorithm thus takes time O(2 n (n 2 (m log T + n log n)).


Sylvain Jacques

A Guette

F Langlais

R Naslain

C(B) MATERIALS AS INTERPHASES IN SiC/SiC MODEL MICROCOMPOSITES

Keywords: Microcomposites, C(B) interphase, Gradient composition interphase, SiC/SiC, Lifetime under load, Tensile behaviour. preprint

HAL is

INTRODUCTION

In SiC-SiC ceramic matrix composites (CMCs), the mechanical tensile failure strength is mainly controlled by the crack propagation mode at the interface between the fiber and the matrix, i.e. by the strength of fiber-matrix bonding. The fiber/matrix coupling can be tailored by depositing on the fiber (before the deposition of the matrix) a sub-micrometer thin film referred to as the "interphase" and consisting of a material with a low stiffness and a low shear strength. SiC-SiC composites including a pyrolytic carbon interphase are known to exhibit a non-brittle behaviour, related to the anisotropic microtexture of PyC [START_REF] Naslain | Fiber-matrix interphases and interfaces in ceramic-matrix composites processed by CVI[END_REF][START_REF] Evans | The physics and mechanics of fibre-reinforced brittle matrix composites[END_REF].

Nevertheless, an important drawback of this interphase material is its ability to be gasified as carbon oxides under oxidizing atmospheres above about 750 K. To improve the oxidation resistance of PyC, it was interesting to introduce boron in this material [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF]. Owing to the liquid state of B 2 O 3 and to its low volatility in the 800-1400 K temperature range, the oxidation of the interphase could be at least partially inhibited without reducing the mechanical fuse properties of pyrocarbon responsible for the toughness of SiC/PyC/SiC composites.

The aim of the present contribution was to study the ability of the C(B) materials prepared by CVD as described in reference [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF] to play the role of interphase in SiC/SiC composite materials. The experimental study was carried out by using microcomposites.

A microcomposite is a model composite consisting of one single fiber coated with the interphase and embedded in the matrix. It represents one of the possible elementary cells of the composite and can be easily prepared by CVD. The various microcomposites were characterized in terms of (i) tensile strength at ambient temperature and (ii) high temperature lifetime in air under load, for which a specific test procedure has been developed.

EXPERIMENTAL

preparation of microcomposites

The fibers used for the fabrication of the microcomposites are Nicalon 1* fibers and have received a pre-treatment in order to improve the fiber-interphase bonding (by eliminating the silica layer from the fiber surface) [START_REF] Droillard | Elaboration et caractérisation de composites à matrice SiC et à interphase séquencée C/SiC[END_REF]. The C(B) interphases were deposited by LPCVD on the fibers by using the conditions defined in reference [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF] (i.e. precursor gas compositions in the system C 3 H 8 -BCl 3 -H 2 , temperature, pressure). The coating-times were adjusted in order to obtain interphases with a total thickness of 0.4 or 0.5 µm. LPCVD interphase deposition was followed by growth of the SiC matrix (about 2.5 µm thick) from the classical precursor CH 3 SiCl 3 -H 2 at the same temperature of about 1223 K (Fig. 1). With these thicknesses, the microcomposites properly simulate the actual composites (V f ≈ 50 %).

Five batches of microcomposites containing uniform interphases with different compositions corresponding to the C(B) materials described in reference [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF], were prepared by using various BCl 3 contents in the precursor gaseous mixtures (Tab. I).

Four batches of microcomposites containing compositional gradient interphases (CGI) were also prepared :

(i)
interphase A in which the boron content increases discontinuously from the fiber interface to the matrix interface, (ii) interphase A' is similar to interphase A but the boron content reaches a higher value near the matrix, (iii) interphase A -1 is similar to interphase A but the compositional gradient is reverse, (iv) interphase B in which the boron content changes alternately from 0 to 20 %.

1* a Si-C-O fiber (ceramic grade, NL 200) from Nippon Carbon, Japan.

These four interphases are schematically described in figure 2. They are constituted by a succession of layers obtained by changing the precursor gas composition along the experiment.

Characterization

The physico-chemical characterization of each uniform C(B) coating has been reported in reference [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF]. The CGI-interphases (e.g. A and B) were characterized by Auger electron spectroscopy (AES) depth profiling.

For the mechanical characterization, about twenty microcomposites per batch with a L = 10 mm gauge length were tensile tested at room temperature according to a single fiber tensile test procedure which has been described elsewhere [START_REF] Lamon | Determination of Interfacial Properties in Ceramic Matrix Composites using Microcomposites Specimens[END_REF][START_REF] Lamon | Microcomposite test procedure for evaluating the interface properties of ceramic matrix composites[END_REF].

The various batches of microcomposites were submitted to thermal ageing in air under a constant load. The procedure consisted in setting microcomposites with a 10 mm gauge length within a specifically designed heating system (Fig. 3). Each specimen was vertically maintained in the heating area between two SiC CVD filaments (Ø = 100 µm) 2 * with an alumina-based adhesive 3 ** . Given load (from 15 to 40 g depending on the microcomposite diameters and the desired stress) was carefully hooked to the bottom end of each SiC CVD filament in the cold area. The stress was chosen, for each set of microcomposites, very close to the proportional limit identified from the stress-strain curves previously established at room temperature. When the temperature reached the setpoint of 873 K or 973 K (for which pure pyrocarbon is rapidly gasified), the lifetime (i.e. the time before failure) of each microcomposite was automatically measured by means of a device connected with timers which detect the load fall.

2* SIGMA, Germany.

3** AREMCO ref 603, USA.

RESULTS

Interphases with uniform compositions

Mechanical behaviour

Average tensile mechanical characteristics at ambient temperature for the five batches of microcomposites containing interphases with uniform compositions are presented in Table II. Figure 4 displays a typical stress-strain curve for each kind of interphase. The introduction of boron in the PyC-interphase lowers the mechanical characteristics of the microcomposites at room temperature : the average failure strength decreases by about one third of its initial value when the boron content reaches 15 at. %, then this decrease seems to stabilize for boron content increasing up to 33 at. % (interphases III, IV and V) since a brittle behaviour is never really observed. These results are in agreement with those previously reported by Lowden et al. [START_REF] Lowden | Improved fiber coatings for Nicalon/SiC composites[END_REF] and Kmetz et al. [START_REF] Kmetz | Synthesis, Characterization and Tensile Strength of CVI C/SiC, SiC/SiC, SiC/B 4 C, and C/B 4 C Composites[END_REF]. Microcomposites without interphase (matrix directly deposited on the fiber)

have been prepared and exhibited as expected a brittle character. Furthermore, from tensile tests on fibers only coated with C(B) interphase (V), it has been shown that the mechanical characteristics do not exhibit a significant decrease in comparison to those of fibers only coated with pure PyC-interphase. So, the decrease in the failure strength of the microcomposites when the boron content increases cannot be due to a degradation of the fibers during the boron containing interphase processing.

Behaviour under oxidizing conditions

Owing to the statistical dispersion of the results, the behaviour of the microcomposites during an ageing treatment in air under load are represented for each batch by the percentage of unbroken microcomposites versus time to failure (as shown in Fig. 5). The best interphase (i.e. which has the best oxidation resistance when the SiC matrix in the microcomposite is cracked) corresponds to the lowest decrease of unbroken microcomposites percentage versus time. This test procedure does not give an absolute lifetime assessment of each kind of microcomposite, but permits a simple comparison between the various batches.

At 973 K and under 600 MPa (Fig. 5), increasing the boron content within the interphase clearly improves the oxidation resistance. All the microcomposites with a pure PyC-interphase are broken during the first day of exposure, conversely, only 20 % of the microcomposites with an interphase containing 33 % of boron are broken after 3 days of exposure.

Interphases with variable composition

AES depth profiling

As expected, AES depth profiles displayed in figure 6 confirm the occurrence of the four successive layers in both interphases A and B.

Mechanical behaviour

Average tensile mechanical characteristics at ambient temperature for the batches A, A', A -1 and B are presented in Table III. Figure 7 displays a typical stress-strain curve for each kind of interphase. Here, the CGI A confers the best mechanical characteristics. The behaviour is very close to that obtained with a pure PyC-interphase.

The microcomposites with the CGI A' exhibit good mechanical characteristics but are slightly weaker than those with the interphase A. The data for the microcomposite with the interphase A -1 show that the reverse of the compositional gradient results in a catastrophic effect. For the microcomposite with the interphase B, the mechanical characteristics are rather moderate in spite of a high proportional limit stress.

Figure 8 shows that at 973 K and under 600 MPa the behaviour of materials with interphases A and A' is respectively similar to those of materials with interphases IV and V (Fig. 5). Therefore, in these conditions, the oxidation resistance of these CGIs is as high as if they were only made of their highest boron content part. For the microcomposites with the interphase A -1 , one can again observe the disastrous effect of reversing the compositional gradient. For the batch B, the sequence selected for the interphase seems to be inefficient since the behaviour is hardly improved in comparison to pure pyrocarbon.

Thermal ageing at a lower temperature (873 K) shows on the one hand that microcomposite lifetimes are globally maintained despite a higher applied stress (800 MPa) and on the other hand, that the CGIs A and A' keep their improved behaviour with respect to pure pyrocarbon (Fig. 9). However, the behaviour of the microcomposites with the interphase A' is here slightly lowered when compared to those with the interphase A probably owing to weaker mechanical characteristics that make the microcomposite more sensitive to the applied stress.

DISCUSSION

Mechanical behaviour

By considering only C(B) interphases (II to V), the mechanical test data could be explained by the large decrease of the C(B) material anisotropy measured in reference [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF] when boron content increases. But, interphase I (pure pyrocarbon) involves the best mechanical characteristics despite a rather weak anisotropy [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF]. From a comparison between the microcomposites with pure pyrocarbon and C(B) interphases, it appears that the most anisotropic interphase does not result in the best mechanical fuse function.

This feature could be explained by the segregation of a second phase when boron content exceeds the solubility limit of boron in graphite (2-3 % according to Lowell [START_REF] Lowell | Solid solution of boron in graphite[END_REF]) : boron excess is no more inserted in the pyrocarbon network by substitution. This second phase could contribute to lower locally the material compliance. Therefore, C(B) materials with such boron contents exhibit a worse capacity for limiting the propagation of matrix cracks towards the fiber than pure pyrocarbon.

For C(B) interphases with varying composition across the thickness, only a compositional gradient in which the boron content increases from the fiber interface to the matrix interface leads to a good mechanical fuse function. Such a material can gradually deflect matrix cracks before they reach the fiber; it represents an optimum with respect to a reverse gradient such as in A -1 or a sequence such as in B.

Microcomposites with gradient A' interphase being slightly less performant than those with type A interphase, it seems that the boron content near the matrix cannot be increased beyond 20-30 % without lowering the mechanical characteristics.

Oxidation resistance

Several authors have shown that (i) low boron additions in graphite inhibit the oxidation of carbon and (ii) the formation of a molten B 2 O 3 glass acts as a physical barrier against oxygen diffusion for higher boron contents [START_REF] Woodley | The reaction of boronated graphite with water vapor[END_REF][START_REF] Allardice | The effect of substitutional boron on the kinetics of the carbon-oxygen reaction[END_REF][START_REF] Fujii | Oxidation behavior of boronated graphite in helium, containing water vapor[END_REF][START_REF] Rodriguez | Fundamental studies of the influence of boron on the graphite-oxygen reaction using in situ electron microscopy techniques[END_REF][START_REF] Ehburger | Inhibition of the oxidation of carboncarbon composite by boron oxide[END_REF]. In a previous study of the physico-chemical properties of various C(B) materials [START_REF] Jacques | LPCVD and characterization of boron-containing pyrocarbon materials[END_REF], it has been reported that only a small amount of boron is needed (less than 8 at. %) to protect pyrocarbon against oxidation in dry air at 973-1073 K. Moreover, Lowden et al. [START_REF] Lowden | Improved fiber coatings for Nicalon/SiC composites[END_REF] reported that low uniform boron contents in C(B) interphases (about 3 to 5 at. %) were enough to yield SiC/SiC composites exhibiting no change in failure strength after annealing at 1273 K in air for 24 h. However, it is necessary according to the present data to reach 33 at. % B to obtain microcomposites without failures during such an exposure time at the lower temperature of 973 K. This discrepancy is probably due to the difference between the test procedures respectively used. On the one hand, the oxidation of Lowden et al. For compositional gradient interphases, if the highest boron content part is located near the matrix the whole interphase is protected. But when the pyrocarbon is near the matrix as in the reverse gradient A -1 interphase, it is more rapidly submitted to matrix

  specimens was not carried out under load, therefore open matrix cracks were not present and oxygen did not have an easy access to the interphase. On the other hand, at 1273 K (ageing temperature used byLowden et al.) in air, the matrix SiC can form SiO 2 which can combine locally with B 2 O 3 and thus reinforce the action of the protecting glass[START_REF] Kobayashi | Formation and oxidation resistance of the coating formed on carbon material composed of B4C-SiC powders[END_REF]. Figures 10.a and 10.b show a microcomposite with a C(B) interphase after tensile test performed at room temperature and thermal ageing in air at 973 K under constant load, respectively. In the first case, a classical matrix crack is observed. In the second case, a condensed material, probably a B 2 O 3 -based glass, has sealed the matrix crack thus preventing the air access to the interphase. At 873 K, the improved oxidation resistance of the C(B) materials can be preserved owing to the low melting point of the protecting B 2 O 3 -based glass.

  cracks and consequently to air attack. The somewhat disappointing results for interphase B could be explained by the greater pure pyrocarbon volume (2 layers/4 = 50 vol. %) compared to interphase A and also by the fact that the second pyrocarbon layer lies near the matrix. It could be improved by changing the sequence (i.e., by reducing the thickness of pure pyrocarbon layers and increasing the total number of the layers, selecting other C(B) layers . . .).

Fig. 1 :

 1 Fig. 1: Schematics of a typical microcomposite specimen prepared by CVD

Fig. 2 :

 2 Fig. 2: Schematics of interphases with varying composition across the thickness.

Fig. 3 :

 3 Fig. 3: Apparatus for measurements of lifetime in air at high temperature under load of SiC/SiC type microcomposites (schematic).

Fig. 4 :

 4 Fig. 4: Typical tensile stress-strain curves at room temperature for SiC/SiC microcomposites with different kinds of uniform C(B) interphases (Curves are offset horizontally for clarity).

Fig. 5 :Fig. 6 :

 56 Fig. 5: Variations with time of the percentage of unbroken microcomposites subjected to 600 MPa load at 973 K in air for the microcomposite batches with uniform C(B) interphases.

Fig. 7 :

 7 Fig. 7: Typical tensile stress-strain curves at room temperature for SiC/SiC microcomposites with C(B) interphases with varying composition across the thickness (Curves are offset horizontally for clarity).

Fig. 8 :

 8 Fig. 8: Variations with time of the percentage of unbroken microcomposites subjected to 600 MPa load at 973 K in air for the various microcomposite batches with interphases with varying composition across the thickness.

Fig. 9 :Fig. 10 :

 910 Fig. 9: Variations with time of the percentage of unbroken microcomposites subjected to 800 MPa load at 873 K in air for microcomposite batches with interphases with interphases I, A and A'.

Table II :

 II Average tensile mechanical characteristics of the SiC/SiC microcomposites. I: pyrocarbone interphase; II to V: C(B) interphase with increasing boron content. ε PL and σ PL are the proportional limit strain and stress, ε F and σ F are the strain and stress to failure. Standard deviations are indicated between ( ).

Table III :

 III Average tensile mechanical characteristics of the SiC/SiC microcomposites with C(B) interphase with varying composition across the thickness. ε PL and σ PL are the proportional limit strain and stress, ε F and σ F are the strain and stress to failure. Standard deviations are indicated between ( ).

ACKNOWLEDGEMENTS

This work has been supported by CNRS and SEP through a grant to S. J. The authors are grateful to C. Robin-Brosse and S. Goujard from SEP, for fruitful discussion.