Swan Dubois

Laurent Feuilloley

Franck Petit

Mikaël Rabie

When Should You Wait Before Updating? Toward a Robustness Refinement

Keywords: 2012 ACM Subject Classification Theory of Computation → Design and analysis of algorithms; Mathematics of computing → Discrete mathematics Robustness, dynamic network, temporal graphs, edge removal, connectivity, footprint, packing/covering problems, maximal independent set, maximal matching, minimum dominating set, perfect matching, NP-hardness

Consider a dynamic network and a given distributed problem. At any point in time, there might exist several solutions that are equally good with respect to the problem specification, but that are different from an algorithmic perspective, because some could be easier to update than others when the network changes. In other words, one would prefer to have a solution that is more robust to topological changes in the network; and in this direction the best scenario would be that the solution remains correct despite the dynamic of the network.

In [6], the authors introduced a very strong robustness criterion: they required that for any removal of edges that maintain the network connected, the solution remains valid. They focus on the maximal independent set problem, and their approach consists in characterizing the graphs in which there exists a robust solution (the existential problem), or even stronger, where any solution is robust (the universal problem). As the robustness criteria is very demanding, few graphs have a robust solution, and even fewer are such that all of their solutions are robust. In this paper, we ask the following question: Can we have robustness for a larger class of networks, if we bound the number k of edge removals allowed?

To answer this question, we consider three classic problems: maximal independent set, minimal dominating set and maximal matching. For the universal problem, the answers for the three cases are surprisingly different. For minimal dominating set, the class does not depend on the number of edges removed. For maximal matching, removing only one edge defines a robust class related to perfect matchings, but for all other bounds k, the class is the same as for an arbitrary number of edge removals. Finally, for maximal independent set, there is a strict hierarchy of classes: the class for the bound k is strictly larger than the class for bound k + 1.

For the robustness notion of [6], no characterization of the class for the existential problem is known, only a polynomial-time recognition algorithm. We show that the situation is even worse for bounded k: even for k = 1, it is NP-hard to decide whether a graph has a robust maximal independent set.

Introduction

In the field of computer networks, the phrase "dynamic networks" refers to many different realities, ranging from static wired networks in which links can be unstable, up to wireless ad hoc networks in which entities directly communicate with each other by radio. In the latter case, entities may join, leave, or even move inside the network at any time in completely unpredictable ways. A common feature of all these networks is that communication links keep changing over time. Because of this aspect, algorithmic engineering is far more difficult than in fixed static networks. Indeed, solutions must be able to adapt to incessant topological changes. This becomes particularly challenging when it comes to maintaining a single leader [START_REF] Casteigts | Deterministic algorithms in dynamic networks: Problems, analysis, and algorithmic tools[END_REF] or a (supposed to be) "static" covering data structure, for instance, a spanning tree, a node coloring, a Maximal Independant Set (MIS), a Minimal Dominating Set (MDS), or a Maximal Matching (MM). Most of the time, to overcome such topological changes, algorithms compute and recompute their solution to try to be as close as possible to a correct solution in all circumstances.

Of course, when the network dynamics is high, meaning that topological changes are extremely frequent, it sometimes becomes impossible to obtain an acceptable solution. In practice, the correctness requirements of the algorithm are most often relaxed in order to approach the desired behavior, while amortizing the recomputation cost. Actually, this sometimes leads to reconsider the very nature of the problems, for example: looking for a "moving leader", a leader or a spanning tree per connected component, a temporal dominated set, an evolving MIS, a best-effort broadcast, etc.-we refer to [START_REF] Casteigts | Deterministic algorithms in dynamic networks: Problems, analysis, and algorithmic tools[END_REF][START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] for more examples.

In this paper, we address the problem of network dynamics under an approach similar to the one introduced in [START_REF] Braud Santoni | A generic framework for impossibility results in time-varying graphs[END_REF]6]: To what extent of network dynamics can a computation be performed without relaxing its specification? Before going any further into our motivation, let us review related work on which our study relies.

Numerous models for dynamic networks have been proposed during the last decades-refer to [START_REF] Casteigts | Deterministic algorithms in dynamic networks: Problems, analysis, and algorithmic tools[END_REF] for a comprehensive list of models-some of them aiming at unifying previous modeling approaches, mainly [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF][START_REF] Xuan | Computing shortest, fastest, and foremost journeys in dynamic networks[END_REF]. As is often the case, in this work, the network is modeled as a graph, where the set of vertices (also called nodes) is fixed, while the communication links are represented by a set of edges appearing and disappearing unexpectedly over the time. Without extra assumptions, this modeling includes all possibilities that can occur over the time, for example, the network topology may include no edges at some instant, or it may also happen that some edge present at some time disappears definitively after that. According to different assumptions on the appearance and disappearance (frequency, synchrony, duration, etc.), the dynamics of temporal networks can be classified in many classes [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF].

One of these classes, Class T C R , is particularly important. In this class, a temporal path between any two vertices appears infinitely often. This class is arguably the most natural and versatile generalization of the notion of connectivity from static networks to dynamic networks: every vertex is able to send (not necessarily directly) a message to any other vertex at any time.

For a dynamic network of the class T C R on a vertex set V , one can partition V × V into three sets: the edges that are present infinitely often over the time -called recurrent edges-, the edges that are present only a finite number of times -called eventually absent edges-, and the edges that are never present. The union of the first two sets defines a graph called the footprint of the network [START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF], while its restriction to the edges that are infinitely often present is called the eventual footprint [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF]. In [START_REF] Braud-Santoni | The next 700 impossibility results in time-varying graphs[END_REF], the authors prove that Class T C R is actually the set of dynamic networks whose eventual footprint is connected.

In conclusion, from a distributed computing point of view, it is more than reasonable to consider only dynamic networks such that some of their edges are recurrent and their union does form a connected spanning subgraph of their footprint.

Unfortunately, it is impossible for a node to distinguish between a recurrent and an eventually absent edge. Therefore, the best the nodes can do is to compute a solution relative to the footprint, hoping that this solution still makes sense in the eventual footprint, whatever it is. In [6], the authors introduce the concept of robustness to capture this intuition, defined as follows:

Definition 1 (Robustness). A property P is robust over a graph G if and only if P is satisfied in every connected spanning subgraph of G (including G itself).

Another way to phrase this definition is to say that a property P is robust if it is still satisfied when we remove any number of edges, as long as the graph stays connected.

In [6], the authors focus on the problem of maximal independent set (MIS). That is, they study the cases where a set of vertices can keep being an MIS even if we remove edges. They structure their results around two questions:

Universal question: For which networks are all the solutions robust against any edge removals that do not disconnect the graph? Existential question: For which networks does there exist a solution that is robust against any edge removals that do not disconnect the graph?

The authors in [6] establish a characterization of the networks that answer the first questions for the MIS problem. Still for the same problem, they provide a polynomial-time algorithm to decide whether a network answers the second question.

Note that the study of robustness was also very recently addressed for the case of metric properties in [START_REF] Casteigts | Robustness of distances and diameter in a fragile network[END_REF]. In that paper, the authors show that deciding whether the distance between two given vertices is robust can be done in linear time. However, they also show that deciding whether the diameter is robust or not is coNP-complete.

Our approach

Our goal is to go beyond [6], and to get both a more fine-grained and a broader understanding of the notion of robustness.

Let us start with the fine-grain dimension. In [6], a solution had to be robust against any number of edge removals as long as the graph remains connected. In this paper, we want to understand what are the structures that are robust against k edge removals while keeping the connectivity constraint, for any specific k, adding granularity to the notion. We call this concept k-robustness (see formal definition below) and we focus on the universal and the existential question of [6] for this fined-grain version of the robustness. Now for the broader dimension, let us discuss the problems studied. In [6], the problem studied is MIS, which is a good choice in the sense that it leads to an interesting landscape. Indeed, robustness being a very demanding property, one has to find problems to which it can apply without leading to trivial answers. In this direction, one wants to look at local problems, because a modification will only have consequences in some neighborhood and not on the whole graph, which leaves the hope that it actually does not affect the correctness at all. Among the classic local problems, as studied in the LOCAL model (see [START_REF] Peleg | Distributed computing: a locality-sensitive approach[END_REF] for the original definition and [START_REF] Hirvonen | Distributed algorithms[END_REF] for a recent book), there are mainly coloring problems and packing/covering problems. The coloring problems (with a fixed number of colors) are not meaningful in our context: an edge removal can only help. But the packing/covering problems are all interesting, thus we widen the scope to cover three classic problems in this paper: maximal independent set (MIS) as before, but also maximal matching (MM) and minimal dominating set (MDS).

To help the reader grasp some intuition on our approach, let us illustrate the 1-robustness for the maximal matching, i.e. a set of edges that do not share vertices and that is maximal in the sense that no edge can be added. To be 1-robust, a matching must still be maximal after the removal of one arbitrary edge that does not disconnect the graph. Let us go over various configurations illustrated in Figure 1 (the matched edges are bold ones). For the two graphs in Figure 1a, that are cycles of 6 vertices, we can observe that two instances of maximal matching can have different behaviors. Indeed, in the top one, if we remove one matched edge, we are left with a matching that is not maximal in the new graph: the two edges adjacent to the removed one could be added. By contrast, in the bottom graph, any edge removal leaves a graph that is still a maximal matching. Now, in the graph of Figure 1b, a complete balanced bipartite graph, all the maximal matchings are identical up to isomorphism. After one arbitrary edge removal, we are left with a graph where no new edge can be matched. Therefore in this graph, any matching is robust to one edge removal. Note that this is not true for any number of edge removals, illustrating the fact that k-robustness and robustness are not equivalent. Finally, in Figure 1c, all the maximal matchings consists of only one edge, and they are not robust to an edge removal. Indeed, after the matched edge is removed, one can choose any of the two remaining ones.

To summarize, Figure 1 illustrates the effect of 1-robustness in three different cases: one where some matchings are 1-robust, one where all matchings are 1-robust, and one where no matching is 1-robust.

Our results

Our first contribution is to introduce the fine-grained version of robustness in Section 2. After that, every technical section of this paper is devoted to provide some answer to the fine-grained version of one of the two questions highlighted above (existential vs. universal) for one of the problems we study. Our focus is actually in understanding how do the different settings compare, in terms of both problems and number of removable edges.

Let us start with the universal question. Here, we prove that the three problems have three different behaviors.

For minimal dominating set, the class of the graphs for which any solution is k-robust is exactly the same for every k (a class that already appeared in [6] under the name of sputnik graphs) as proved in Section 3.

For maximal matching, the case of k = 1, which we used previously as an example, is special and draws an interesting connection with perfect matchings, but then the class is identical for every k ≥ 2. These results are presented in Section 4.

Finally, for maximal independent set, we show in Section 5 that there is a strict hierarchy: the class for k edge removals is strictly smaller than the one for k -1. For this case, we do not pinpoint the exact characterization, but give some additional structural results on the classes.

The existential question is much more challenging. Section 6 presents some preliminary results on the study of this question. For maximal independent set, we show that for any k, deciding whether a graph has a maximal independent set that is robust to k edge removals is NP-hard. This is the first NP-hardness result for this type of question.

Model, definitions, and basic properties

In the paper, except when stated otherwise, the graph is named G, the vertex set V and the edge set E.

Robustness and graph problems

The key notion of this paper is the one of k-robustness.

Definition 2. Given a graph problem and a graph, a solution is k-robust if after the removal of at most k edges, either the graph is disconnected, or the solution is still valid.

Note that k-robustness is about removing at most k edges, not exactly k edges. We will abuse notation and write ∞-robust when mentioning the notion of robustness from [6], with an unbounded number of removals. Hence k is a parameter in N ∪ ∞.

Notation 1. We define U k

P and E k P the following way: Let U k P be the class of graphs such that any solution to the problem P is k-robust. Let E k P be the class of graphs such that there exists a solution to the problem P that is k-robust Note that to easily incorporate the parameter k, we decided to not follow the exact same notations as in [6].

Graph problems.

We consider three graph problems:

1. Minimal dominating set (MDS): Select a minimal set of vertices such that every vertex of the graph is either in the set or has a neighbor in the set.

Maximal matching (MM):

Select a maximal set of edges such that no two selected edges share endpoint.

3.

Maximal independent set (MIS): Select a maximal set of vertices such that no two selected vertices share an edge.

A perfect matching is a matching where every vertex is matched. We will also use the notion of k-dominating set, which is a set of selected vertices such that every vertex is either selected or is adjacent to two selected vertices. Note that k-dominating set sometimes refer to another notion related to the distance to the selected vertices, but this is not our definition.

The case of robust maximal matching.

For maximal matching, the definition of robustness may vary. The definition we take is the following. A maximal matching M of a graph G is k-robust if after removing any set of at most k edges such that the graph G is still connected, what remains of M is a maximal matching of what remains of G.

Graph notions

We list a few graph theory definitions that we will need.

Definition 3. The neighborhood of a node v, denoted N (v), is the set of nodes that are adjacent to v. The closed neighborhood of a node v, denoted N [v], is the neighborhood of v, plus v itself. Definition 4. A graph is t-(edge)-connected if, after the removal of any set of (t -1) edges, the graph is still connected. A t-(edge)-connected component is a subgraph that is t-(edge)-connected.
In the following we are only interested in edge connectivity thus we will simply write t-connectivity to refer to t-edge-connectivity. In our proofs, we will use the following easy observation multiple times : in a 2-connected graph every vertex belongs to a cycle. Definition 5. In a connected graph, a bridge is an edge whose removal disconnects the graph. Definition 6. Given two graphs G and H, the join of these two graphs, join(G, H), is the graph made by taking the union of G and H, and adding all the possible edges (u, v), with u ∈ G and v ∈ H. See Figure 2a. Definition 7. A sputnik graph ( [6]) is a graph where every node that is part of a cycle has an antenna, that is a neighbor with degree 1. See Figure 2b.

Basic properties

The following properties follow from the definitions.

3

Minimal dominating set Theorem 8. For all k in N ∪ ∞, U k M DS is the set of sputnik graphs.

Proof. We know from [6] that the theorem holds for k = ∞. Hence, thanks to Property 1, it is sufficient to prove that the theorem is true for k = 1. For the sake of contradiction, consider a graph G in U 1 M DS that is not a sputnik graph. Then there is a node u that belongs to a cycle, and that has no antenna. Let S be the closed neighborhood of u, S = N [u]. We say that a node of S, different from u, is an inside node if it is only connected to nodes in S. We now consider two cases depending on whether there is an inside node or not. See Figure 3.

1.

Suppose there exists an inside node v. Note that v has at least one neighbor different from u because otherwise it would be an antenna. Let the set W be the closed neighborhood of v, except u. The set D = V \ W is a dominating set of the graph, because all the nodes either belong to D or are neighbors of u (which belongs to D). Now, we transform D into a minimal dominating set greedily: we remove nodes from D in an arbitrary order, until no more nodes can be removed without making D non-dominating. We claim that this minimal dominating set is not 1-robust. Indeed, if we remove the edge (u, v), v is not covered any more (none of its current neighbors belongs to D), and the graph is still connected (because v has a neighbor different from u). 2. Suppose there is no inside vertex. Let a be a neighbor of u in the cycle. Let W be the set S \ a. Again we claim that V \ W is a dominating set. Indeed, because there is no inside node, every node in S different from u is covered by node outside W , and u is covered by a, which belongs to V \ W . As before we can make this set an MDS by removing nodes greedily, and again we claim it is not 1-robust. Indeed, if we remove the edge (u, a), we do not disconnect the graph (because of the cycle containing u), and u is left uncovered.

Maximal matching

We now turn our attention to the problem of maximal matching, and get the following theorem.

Theorem 9. The class U 1 M M is composed of the set of trees, of balanced complete bipartite graphs, and of cliques with an even number of nodes. For any k ≥ 2, the class U k M M is composed of the cycle on four nodes and of the set of trees.

The core of this part is the study of the case where only one edge is removed. At the end of the section we consider the more general technically less interesting case of multiple edges removal.

One edge removal

In this subsection we characterize the class of graphs where every maximal matching is 1-robust.

Lemma 10. U 1 M M is composed of the set of trees, of balanced complete bipartite graphs, and of cliques with an even number of nodes.

The rest of this subsection is devoted to the proof of Lemma 10.

A result about perfect matchings

The core of the proof is to show a connection to perfect matchings. Once this is done, we can use the following theorem from [START_REF] David | Randomly matchable graphs[END_REF].

Theorem 11 ([10]). The class of graphs such that any maximal matching is perfect is the union of the balanced complete bipartite graphs and of the cliques of even size.

First inclusion

We start with the easy direction of the theorem, which is to prove that the graphs we mentioned are in U 1 M M . In trees, any property is robust, since no edge can be removed without disconnecting the graph. For the two other types, we will use the following claim.

Claim 12. Perfect matchings are 1-robust maximal matchings.

Consider a perfect matching in a graph, and remove an arbitrary edge (that does not disconnect the graph). If this edge was not in the matching, and then we still have a perfect matching, thus a maximal matching. If this edge was in the matching, then there are only two non-matched nodes in the graph (the ones that were adjacent to the edge), and all their neighbours are matched, thus the matching is still maximal. This proves the claim.

In balanced complete bipartite graphs and cliques of even size, any maximal matching is perfect (Theorem 11), and since perfect matchings are 1-robust maximal matchings, we get the first direction of Lemma 10.

Second inclusion: three useful claims

We now tackle the other direction. The following lemma establishes a local condition that 1-robust matchings must satisfy. See Figure 4 for an illustration. Here we have a maximal matching, and in particular all the neighbors of u are matched, but it is not a 1-robust matching. Indeed, removing (v1, w1) gives the possibility of adding (u, v1) and (w1, z). Also, having a triangle with a matched edge and an unmatched node, like (u, v2, w2) is impossible (Claim 14), since removing (v2, w2) gives the possibility of adding either (u, v2) or (u, w2) to the matching, contradicting the maximality. Hence we need the bridge condition.

Claim 13. In a 1-robust maximal matching M , if a node u is not matched, then all the nodes of N (u) are matched, and their matched edges are bridges of the graph.

The fact that all the nodes in N (u) are matched follows from M being a maximal matching. Now, suppose that there exists (v, w) ∈ M , such that v ∈ N (u) and (v, w) is not a bridge. In other words, the removal of (v, w) does not disconnect the graph. After this removal, both u and v are unmatched, and since (u, v) is an edge of the graph, the matching in the new graph cannot be maximal. This contradicts the 1-robustness of M , and proves the lemma.

The following claim follows directly from Claim 13. We now study the shape of 1-robust maximal matchings in cycles.

Claim 15. In every maximal matching of a graph in U 1 M M , if a node belongs to a cycle, then it is matched.

Our proof of Claim 15 consists in proving that if a maximal matching does not satisfy the condition, then either it is not 1-robust, or we can use it to build another maximal matching that is not 1-robust. In both cases this means the graph was not in U 1 M M . Consider a node u in a cycle. Let a and b be its direct neighbors in the cycle, and let its other neighbors be (c i ) i . There can be several configurations, with a adjacent to b or not, etc. The proof is generic to all these cases, but Figure 5 illustrates different cases. Consider a 1-robust maximal matching M where u is unmatched. Because of Claim 13, we know that there exists nodes a , b , and c i for all i, such that respectively (a, a ), (b, b ) and (c i , c i ) (for all i) are bridges of the graph. Because of the bridge condition, these nodes a , b and c i (for all i) are all different, and are different from a, b, u and the c i 's. Let us also denote d the neighbor of a in the cycle that is not u. Note that d can be a c i or b, but no other named node. (See Figure 5 for an illustration.) Now we create a new matching M from M in the following way. First remove all the edge of the matching that are not adjacent to one of the nodes above. Then, remove (a, a ) and any edge matching d (if it exists). Note that this last edge matching d could be a (c j , c j ) or (b, b ). Add (a, d) to the matching (note that both nodes are unmatched before this operation). In this matching, all the neighbors of u are matched. We complete this matching into a maximal matching M . The edge (a, d) is in M and u is unmatched, which is a contradiction with Claim 13, thus M cannot be 1-robust, and this proves the claim.

Second inclusion: putting pieces together

Claim 16. A graph in the class U 1 M M is either a tree or is 2-connected. Consider a graph that is neither a tree nor a 2-connected graph. There necessarily exists a bridge (u, v) such that u belongs to a cycle. We distinguish two cases. 1. Node v is linked only to u, that is, v is a pendant node. Then we build a maximal matching M by first forcing u to be matched to a node that is not v, and then completing it greedily. Now, if we remove the edge that matches u, we do not disconnect the graph since u was part of a cycle, but neither u nor v is matched, thus the matching is not maximal ((u, v) could be added). Thus the matching M was not 1-robustness. 2. Node v is linked to another node w. Let consider (v i ) i the set of nodes such that v i = v and (u, v i ) is a bridge. By the previous point, we know that there exists some w i = u in N (v i ). Moreover, those (w i ) must be distinct pairwise and from all the other named nodes, otherwise (u, v i ) would not have been a bridge. The node w and the nodes (w i ) i cannot be part of the 2-connected component of u, otherwise (u, v) and (u, v i ) would not be a bridge. We build a maximal matching M by first forcing (u, v) and (v i , w i ) for all i, and then completing it greedily. As observed earlier, in the 2-connected component of u every node must belong to a cycle, thus by Claim 15, we get that every node of this component must be matched. We now build a second matching M . We start from M and remove from the matching (u, v) and every edge that is in v's side of the bridge. Then we force (v, w) in the matching, and complete it greedily. The matching M is maximal and u is unmatched, since all of its neighbors are matched, hence by Claim 15 it is not 1-robust, since it belongs to a 2-connected components thus to a cycle. This concludes the proof of the claim.

To conclude a graph in the class is either a tree, or is 2-connected, and in this last case because of Claim 15, every node must be matched in every maximal matching. Then Lemma 10 follows from Theorem 11.

More than one edge removal

Lemma 17. For any k ≥ 2, U k M M is composed of the cycle on four nodes and of the set of trees.

Now we claim that

v ∪ (A \ u) is not (k + 1)-robust, thus G k does not belong to U k+1
M IS . We choose a vertex b on the B side, and remove all the edges (a, b) for a ∈ A \ u. This is a set of k + 1 edges whose removal does not disconnect the graph, but leaves b without selected neighbors. This v ∪ (A \ u) is not (k + 1)-robust.

A structure theorem for U k M IS

The construction used in the proof of Theorem 18 is very specific and does not really inform about the nature of the graphs in U k M IS . It can be generalized, with antennas on both sides and arbitrarily large (unbalanced) bipartite graphs with arbitrary number of antennas per nodes, but it is still specific. Moreover these construction heavily rely on pendant nodes, that are in some sense abusing the fact that we do not worry about the correctness of the solution if the graph gets disconnected.

In order to better understand these classes, and to give a more flexible way to build such graphs, we prove a theorem about how the class behaves with respect to the join operation (Definition 6).

We denote by G p the class of graphs where every maximal independent set has size at least p. We say that a graph class is stable by an operation if, by applying this operation to any (set of) graph(s) from the class, the resulting graph is also in the class.

Theorem 19. For all k, the class U k M IS ∩ G k+1 is stable by join operation. Also, if either G or H is not in U k+1 M IS , then join(G, H) is not in U k+1 M IS either.
Proof. Let us start with the first statement of the theorem. Consider two graphs G and H in U k M IS ∩ G k+1 . We prove that J = join(G, H) is also in

U k M IS ∩ G k+1 .
Claim 20. Any MIS of J is either completely contained in the vertex set of G, and is an MIS of G, or contained in the vertex set of H, and is an MIS of H.

Consider an independent set in J. If it has a node u in G, then it has no node in H, as by construction, all nodes of H are linked to u. The analogue holds if the independent set has a node in H. Thus any independent set is either completely contained in G or completely contained in H. Now, a set is maximal independent in G (resp. H) alone if and only if it is maximal independent in G (resp. H) inside J. Indeed the only edges that we have added are between nodes of G and nodes of H. This proves the claim. Therefore, the resulting graph is in G k+1 . Now for the k-robustness, consider without loss of generality an MIS of J that is in part G, and suppose it is not k-robust. In this case there must exists a non-selected vertex v, that has no more selected neighbors after the removal of k edges (while the graph stays connected). This node cannot be in the part G, otherwise the same independent set in the graph G would not be k-robust. And it cannot be in the part H, since every node of H is linked to all the vertices of the MIS, and this set has size at least k + 1 since G ∈ G k+1 . Now, let us move on to the second statement of the theorem. Let's assume that G has an MIS S and k + 1 edges such that their removal makes that S is not longer maximal (i.e. there exists some u that can be added to the set). Then, S is also an MIS of join(G, H), and the removal of the same edges will allow to add u to the set, as the only new neighbors of u are from H that does not contain any node of the chosen MIS

6

The existence of a robust MIS is NP-hard

Remember that we have defined two types of graph classes related to robustness. For a given problem, and a parameter k, the universal class is the class where every solution is k-robust. This is the version we have explored so far. For this version, recognizing the graphs of the class is easy since these have simple explicit characterization. The second type of class is the existential type, where we want that there exists a solution that is k-robust. And here the landscape is much more complex. Indeed, in [6] in the simpler case of robustness without parameter, there is no explicit characterization of the existential class, only a rather involved algorithm. In this section we show that, when we add the parameter k the situation becomes even more challenging: the algorithm of [6] runs in polynomial time, and here we show that the recognition of E 1 M IS is NP-hard.

Theorem 21. For every odd integer k, it is NP-hard to decide whether a graph belongs to E k M IS .

The rest of this section is devoted to the proof of this theorem. It is based on the NP-completeness of the following problem.

Perfect stable

Input: A graph G = (V, E). Question: Does there exists a subset of vertices S ⊂ V that is independent 2-dominating? Remember that a set is independent 2-dominating if no two neighbors can be selected, and every non-selected vertex should have at least two selected neighbors. Just to get some intuition about why we are interested in this problem, note that with independent 2-dominating after removing an edge between a selected and a non-selected vertex, the non-selected vertex is still dominated. It was proved in [START_REF] Croitoru | Perfect stables in graphs[END_REF] that Perfect stable is NP-hard in general. We will need the following strengthening of this hardness result.

Lemma 22. Deciding whether a 2-connected graph has an independent 2-dominating set is NP-complete.

Note that this lemma does not follow directly from [START_REF] Croitoru | Perfect stables in graphs[END_REF] because the reduction there does use some non-2-connected graphs.

Proof. Let G be an arbitrary connected graph with at least one edge. Consider G to be the same as G but with a universal vertex, that is, G with an additional vertex u that is adjacent to all the vertices of G. This graph is 2-edge connected. Indeed, since G is connected and has at least two vertices, removing any edge (u, v) with v ∈ V (G) cannot disconnect the graph, and removing an edge from G does not disconnect the graph because all nodes are linked through v.

We claim that G has an independent 2-dominating set if and only if G has one. First, suppose that G has such a set S. Note that the set S has at least two selected vertices. Indeed, G has at least one edge, which implies that at least one vertex is not selected (by independence), and such a vertex should be dominated by at least two selected vertices. Now we claim that S is also a solution for G . Indeed, the addition of u to the graph does not impact the independence of S, nor the 2-domination of the nodes of G, and v is covered at least twice, since there are at least two selected vertices in G. Second, if G has independent 2-dominating set S , it cannot contain v. Indeed, because of the independence condition, if v is selected, then no other node can be selected, and then the 2-domination condition is not satisfied. Then S is contained in G and is an independent 2-dominating set of G. Now, let us formalise the connection between robustness and independent 2-domination.

Lemma 23. In a 2-connected graph, the 1-robust maximal independent sets are exactly the independent 2-dominating sets.

Proof. As a consequence of Property 2, in a 2-connected graph, a 1-robust MIS is an MIS that is robust against the removal of any edge (that is, we can forget about the preserved connectivity in the robustness definition). This means that every node not in the MIS is covered twice, otherwise one could break the maximality by removing the edge between the node covered only once and the node that covers it. In other words, the independent set must be 2-dominating. For the other direction it suffices to note that any independent dominating set is a maximal independent set. At that point, plugging Lemma 22 and Lemma 23 we get that deciding whether there exists a 1-robust MIS in a graph is NP-hard, even if we assume 2-connectivity. This last lemma is the final step to prove Theorem 21.

Lemma 24. For any 2-connected graph G and any integer k > 1, we can build in polynomialtime a graph G , such that: G has a 1-robust MIS if and only if G has a 2k -1-robust MIS.

Proof. We build G in the following way. Take k copies of G, denoted G 1 , ..., G k , with the notation that u x is the copy of vertex u in the x-th copy. For every edge (u, v) of G, we add the edge (u x , v y ) for any pair x, y ∈ 1, ..., k.

Let us first establish the following claim. An MIS in the graph G necessarily has the following form: it is the union of the exact same set repeated on each copy. Indeed, let u i be in the MIS. For any j = i, all the neighbors of u j in the copy G j are a neighbor of u i , which implies that they are not in the MIS. Hence, no neighbor of u in any copy can be in the MIS. As those nodes are the only neighbors of u j , it implies that u j is also in the MIS. Now suppose that G has a 1-robust MIS. We can select the clones of this MIS in each copy, and build an MIS for G (the independence and maximality are easy to check). In this MIS of G , every non-selected vertex has at least 2k selected neighbors, therefore this MIS is 2k -1 robust.

Finally, suppose that G has a 2k -1 robust MIS. Thanks to the claim above, we know that this MIS is the same set of vertices repeated on each copy. We claim that when restricted to a given copy, this MIS is 1-robust. Indeed, if it were not, then there would be one non-selected vertex with at most one selected neighbor, and this would mean that in G this vertex would have only k selected neighbors, which contradicts the 2k -1 robust (given the connectivity).

Conclusions

In this paper we have developed the theory of robustness in several ways: adding granularity and studying new natural problems to explore its diversity. The next step is to fill in the gaps in our set of results: characterizing exactly the classes U k M IS , and understanding the complexity of answering the existential question for maximal matching and minimum dominating set. We believe that a polynomial-time algorithm can be designed to answer the existential question in the case of maximal matching with k = 1, with an approach similar

Figure 1

 1 Figure 1 Three examples of MMs in various graphs.

( a )

 a The join of two graphs: the black edges are the original edges, the doted edges are the one added by the join operation.(b) A sputnik graph. The white vertices are part a cycles, the grey vertices are their antennas, and the black vertices do not belong to any cycle, nor are antennas.

Figure 2

 2 Figure 2 Illustration of the definitions of Subsection 2.2.

Figure 3

 3 Figure 3The two cases of the proof of Theorem 8: with an inside node, on the left, and without an inside node on the right. The cycle is represented by the dashed line, and the dotted lines represent outgoing edges of non-inside nodes.

1 zFigure 4

 14 Figure[START_REF] Casteigts | Time-varying graphs and dynamic networks[END_REF] Illustration of Claim 13. Here we have a maximal matching, and in particular all the neighbors of u are matched, but it is not a 1-robust matching. Indeed, removing (v1, w1) gives the possibility of adding (u, v1) and (w1, z). Also, having a triangle with a matched edge and an unmatched node, like (u, v2, w2) is impossible (Claim 14), since removing (v2, w2) gives the possibility of adding either (u, v2) or (u, w2) to the matching, contradicting the maximality. Hence we need the bridge condition.

Claim 14 .

 14 In a 1-robust maximal matching M , if there is an unmatched node u, two nodes a, b ∈ N (u) with (a, b) ∈ E, then (a, b) / ∈ M .

Figure 5

 5 Figure 5 Illustration of the proof of Claim 16, in three cases: d is not b nor a ci, d is one of the ci, d is b. The dashed lines represent paths with at least one edge. The dotted lines represent the change we operate: the edges that are crossed out are removed from the matching, the edges that are have a dotted double are added to the matching.

Property 1 .

 1 For any problem P , for any k, U k+1 If a graph is (k + 1)-connected then a solution is k-robust if and only if after the removal of any set of k edges the solution is still correct.

	In particular, U ∞ P ⊆ U k P ⊆ U 1 P and E ∞ P ⊆ E k P ⊆ E 1 P , for all k.
	Property 2.
	P	⊆ U k P and E k+1 P	⊆ E k P .

Acknowledgements.

We thank Nicolas El Maalouly for fruitful discussions about perfect matchings and Dennis Olivetti for pointing out reference [10].

Funding ANR SKYDATA (ANR-22-CE25-0008-02) ANR GrR (ANR-18-CE40-0032) 1

Proof. We first prove the reverse inclusion. As before, trees are in U k M M for any k because any edge removal disconnects the graph. Then for C 4 , note that it belongs to U 1 M M , and that the removal of more than one edge disconnects the graph.

For the other direction, we can restrict to U 2 M M , and by definition it is included in U 1 M M . Thus we can simply study the case of the balanced complete bipartite graphs and of the cliques on an even number of nodes. Consider first a complete bipartite graph B k,k with k > 2 (that is any B k,k larger than C 4 ), and a maximal matching M . Take two arbitrary edges (a 1 , b 1 ) and (a 2 , b 2 ) from the matching and remove them from the graph. The graph is still connected. Now the nodes a 1 and b 2 are unmatched and there is an edge between them, thus the resulting matching is not maximal and M is not 2-robust. Thus the only

For the cliques on an even number of nodes, consider one that has strictly more than two vertices. A maximal matching M contains at least two edges (u 1 , v 1 ) and (u 2 , v 2 ). When we remove these edges from the graph, we still have a connected graph, u 1 and u 2 are unmatched, but (u 1 , u 2 ) still exists, thus the resulting matching is not maximal and M was not 2-robust.

Maximal independent set

Maximal independent set illustrates yet another behavior for the classes (U k M IS ) k : they form an infinite strict hierarchy.

An infinite hierarchy Theorem 18. For every

Proof. Let k ≥ 1. We will define a graph G k , and prove that it belongs to U k M IS but not to U k+1 M IS .

To build G k , consider a bipartite graph with k + 2 nodes on each of the sides A and B, and add a pendant neighbor v to a node u on the side A. See Figure 6. This graph has only three MIS: A, v ∪ B, and v ∪ (A \ u). Indeed: (1) if the MIS contains u, then it cannot contain vertices outside of A, and to be maximal it contains all of A, (2) if it contains a vertex of B, it cannot contain a vertex of A, and by maximality it contains all of B and v, and (3) if it contains v, and no vertex of B, then by maximality it is v ∪ (A \ u). We claim that these three MIS are k-robust, therefore G k is in U k M IS . Suppose an MIS is not k-robust. Then there exists a vertex w that is not part of the MIS, such that after at most k edge removals, it has no neighbor in the MIS anymore. Let us make a quick case analysis depending on who is this vertex w. It cannot be v, since removing the edge (u, v) would disconnect the graph. It cannot be a vertex of A, nor of B, because in all MIS mentioned, all non selected nodes (except v) have at least k + 1 selected neighbors.


Tem poralit y: St udy of t he Effect of Tem poral Dist ance on t he Episodicit y of Ment al Sim ulat ions Following Prim ing in Virt ual Realit y"

Lesur B., La Corte V., Colas Blanco I., Piolino P.

Fut ure Works

The "constructive episodic simulation" hypothesis (Shacter & Addis, 2007a[START_REF] Schacter | Constructive memory: the ghosts of past and future[END_REF] proposes that episodic memory and episodic future thinking rely on similar mechanisms, and some studies indicate a common brain network [START_REF] Szpunar | Neural substrates of envisioning the future[END_REF]. Recent research suggests that they are both manifestations of the same constructive simulation process (Addis et al., 2018). In line with this symmetrical function of memory and self-projection, the TEDIFT model (La [START_REF] Corte | On the Role of Personal semantic memory and temporal distance in episodic future thinking: the TEDIFT model[END_REF] indicates that personal semantic information increases with temporal distance, becoming more prominent as self-projection moves further into the future or past. The aim of the present study is to investigate differences in episodicity between past and future mental simulations as a function of temporal distance using immersive virtual reality.

A virtual reality tool was developed to initiate mental projections into the past or future. In the first study, participants are primed for their episodic simulations with a virtual immersion in a past or future temporality. Four environments were created, titled "Near Past" (2020), "Distant Past" (1980), "Near

Future" (2024), and "Distant Future" (2060), providing an itinerary through a city inspired by Paris. The study employs an within participant design, comparing episodicity scores (TEMPau, [START_REF] Piolino | La mémoire autobiographique: théorie et pratique[END_REF]Piolino et al., , 2003aPiolino et al., , 2003b[START_REF] Piolino | Autobiographical memory, autonoetic consciousness, and self-perspective in aging[END_REF][START_REF] Piolino | Episodic autobiographical memories over the course of time: Cognitive, neuropsychological and neuroimaging findings[END_REF] in distant versus closer temporal conditions, regardless of the past or future nature of the immersion. In a second study, a "neutral" condition is presented to ensure a valid comparison between primed and unprimed conditions. The episodicity of autobiographical simulations will be compared within participants, following immersion in a specific temporality or in a neutral environment.

We hypothesize that the episodicity score will be lower in the more distant conditions than in the closer conditions, regardless of the past or future nature of the immersion. It is also hypothesized that the episodicity in each temporality condition will be stronger than in the neutral condition. This study has potential implications for understanding the neural mechanisms underlying episodic memory and episodic future thinking, as well as their functional role in self-projection.

The four universes share a similar visual style and structure, with almost identical buildings, while the differences in time periods are conveyed through details and specific scenes. Throughout the journey, public advertising signs display various events that have occurred in the past or could potentially occur in the future. The device incorporates sound, visual, contextual elements, and animations, as well as radio broadcasts, projections, and even holograms in the distant future.

  at oir e M ém oir e, Cer veau et Cogn it ion . Un iver sit é Par is-cit é

  Exper ien ce 1 (w it h in par t icipan t s) Exper ien ce 2 (w it h in / bet w een par t icipan t s) n ear f u t u r e dist an t f u t u r e


Christoph Gerhard

Jörg Hermann

LIBS Analysis of Optical Surfaces and Thin Films

Elemental analyses of thin films and optical surfaces with complex compositions are challenging as the standard analytical techniques based on measurement calibration are difficult to apply. In this chapter, we show that calibration-free laser-induced breakdown spectroscopy presents a powerful solution, enabling rapid quantitative analyses of multi-elemental thin films or tiny surface volumes of optical materials with high analytical performances. Examples are given for classically polished optical glass and a nickel-chromium-molybdenum alloy film of 150 nm thickness. Thus, broadband spectra, recorded under experimental conditions that enable simple and accurate modeling of plasma emission, are processed via a calibration-free approach based on the calculation of the spectral radiance of a plasma in local thermodynamic equilibrium to deduce the elemental composition. The validation via energy-dispersive X-ray spectroscopy, inductively coupled plasma atomic emission spectroscopy, and Rutherford backscattering spectrometry illustrates that calibration-free LIBS is not only a promising tool, but already a reliable analytical technique.

Introduction

Glass is one of the oldest synthetic materials produced and used by mankind for millennia. The first instruction for the production of glass is a more than 2,600 years old cuneiform inscription that was found in the library of the ancient Assyrian king Ashurbanipal. It roughly says: "Take 60 parts of sand, 180 parts of ash from sea plants, and 5 parts of chalk and you obtain glass." Even though this basic recipe is still valid for simple glass vessels or panes, modern technical and optical glasses feature a much more complex composition. For instance, special crown or flint glasses used for the manufacturing of optical components and systems partially feature more than 20 different elements that act as glass network formers, modifiers and stabilizers. Moreover, optically active surfaces are usually coated with different functional coatings such as mirrors, anti-reflection layers or polarizing thin films. Most of such coatings consist of dielectric compounds as for example magnesium fluoride, zinc sulfide or titanium dioxide and may contain further metallic components. Besides optical coatings, thin films are widely used in modern surface technology, for example as functional layers in tribology or passivation. Here, a huge variety of different compositions is in hand. The quantitative analysis of thin films and optical surfaces is thus a challenging task. Here, quite different approaches and methods can be used [jem02,tre13]. The most common technique for glass analysis is X-ray Fluorescence (XRF) where the sample surface is excited by polychromatic X-ray irradiation. The resulting fluorescence signal emitted by recombination of electrons is then detected and evaluated. This approach allows the analysis of major, minor and trace elements. It is thus widely used in archeology [tan09,liu12,hod19] and forensic investigations [koo91,tre13]. However, elements with atomic numbers smaller than 5, as for example hydrogen, cannot be detected. Another standard method for glass analysis is Inductively Coupled Plasma Atomic Emission Spectroscopy (ICP-AES). Here, the sample material is dissolved in acid, vaporized and then transported within an argon flux into an inductively coupled plasma for electronic excitation at a temperature of about 10,000 K. The sample atoms are thus ionized and excited, and consequently emit characteristic radiation. The spectrum obtained in that way is finally analyzed. Even though this approach enables precise and quantitative analysis of solids as for example glasses [koz92], it is difficult to apply to thin films or to in-depth measurements of near-surface layers since for both applications, material with well-defined thickness needs to be dissolved by the used acid. However, ICP-AES is suitable for the detection of impurities within glasses or polishing re-deposition layers [nea05,nea09] where the limit of detection amounts to a few ppm, depending on the particular element [ger21]. As an alternative to sample vaporization via acid digestion, direct vaporization is possible via laser ablation. This process, laser ablation inductively coupled plasma optical emission spectrometry (LA-ICP-OES), has turned out to be a promising alternative elemental analysis technique for forensic applications [sch12]. The ions generated by inductively coupled plasmas can also be evaluated via inductively Coupled Plasma Mass Spectrometry (ICP-MS) where the determination of the sample composition is carried out on the basis of the ion mass and not the emitted radiation. Since this approach is well suited for the detection and quantification of traces of lowest concentration, it is applied for forensic investigations of glasses [duc02]. A further powerful analytical method based on the detection of ions is Secondary Ion Mass Spectroscopy (SIMS) [ben75]. Here, secondary ions are extracted from the sample surface by an incident beam of primary ions of heavy elements such as cesium. The evaluation of secondary ions is then performed by detecting either the mass-over-charge ratio m/q or the time of flight. In the latter case, the method is referred to as Time-of-Flight Secondary Ion Mass Spectroscopy (ToF-SIMS). SIMS is a versatile and powerful analytical technique that -if properly calibrated -is also capable of detecting and quantifying lowest impurities in both natural and synthetic glasses [mar14,reg16] as well as thin films [hat97]. A noteworthy important advantage of SIMS is the possibility of direct detection of hydrogen in glasses [yur89,ger12]. A further advantage -probably the most important one -is the fact that due to the measurement principle, depth-resolved measurements with high resolution can be performed. Another common surface analysis technique based on the application of incident ions is Rutherford Backscattering Spectrometry (RBS). Here, the sample surface is irradiated by ions of low mass as for example hydrogen or helium, but high kinetic energy. Some of these ions are backscattered by the sample. The energy of such backscattered ions depends on several parameters, including the mass of the sample atom where scattering occurred. Hence, the sample composition can be determined by detecting the energy of backscattered ions. Since this energy also follows from the stopping power within the sample material, RBS enables depth-resolved measurements [per87] where the depth resolution is 2 to 10 nm, depending on the atomic mass of the elements within the sample, and the information depth amounts to some microns. It is thus a nondestructive technique for the depthresolved analysis of the composition of coatings and thin films [jey12]. A further method for glass and thin film analysis is X-ray Photoelectron Spectroscopy (XPS), a wellestablished and widespread standard technique. This method is based on the external photoelectric effect. The sample surface is irradiated by X-rays where the Al-Kα line is frequently used. As a result of such irradiation, electrons are extracted from the outermost layer of the surface; the information depth of XPS amounts to about 10 nm. The sample composition is then obtained from the analysis of the number and binding energy of the detected electrons. Moreover, the detected signal does not only enable the measurement of the elemental composition, but also characterizes the binding states or bond types within the sample material. For instance, this allows the analysis of the oxidation states of glass oxides [jie90] or the structure of glasses and glass modifications [ony93,hol01,ban17]. This method is also very suitable for compositional measurements of coatings [ran18] and interfaces [hau93]. Even though XPS -and the related Auger electron spectroscopy (AES) -suffer from matrix effects [jab88,tan03] due to scattering of electrons within the sample material, it is one of the most accurate and powerful analytical tool for surface analysis. Another widespread method, Energy Dispersive X-ray Spectroscopy (EDX, EDS), could be referred to as "inverse XPS": an electron beam irradiates the sample surface and the resulting X-ray emission spectrum is analyzed. The advantage of this approach is the high spatial resolution since EDXapparatuses are usually integrated in scanning electron microscopes (SEM). Thus, precise elemental mapping can be realized [dal10]. Even though this technique is suitable for the quantification of major elements in glasses, its low sensitivity prevents the quantitative determination of traces and minor elements [fal06]. Moreover, surface charging may lead to severe overestimation of oxygen due to electron-beam induced oxidation on the one hand [ric96], and outgassing of oxygen from deeper regions caused by electron bombardment on the other hand [lin63]. Finally, the elemental composition of thin films and glasses can be determined via Laser-Induced Breakdown Spectroscopy (LIBS) -one of the oldest laser applications [bau13]. LIBS has turned out to be a suitable tool for thin film analysis [can05,owe10,in13,her19] and the determination of the chemical composition of glasses [ger14]. In both cases, accurate analysis of traces and impurities that may severely affect the functionality of coatings or glass surfaces is of specific interest. For instance, even lowest residues from operating materials used in optics manufacturing notably alter the index of refraction of polished glass surfaces [ger17b,ger21]. It was demonstrated that appropriate calibration, for example by using a multiple-step calibration procedure as reported by Negre and co-workers [neg15], might increase the measurement accuracy for such minor elements. However, merely calibration-free approaches enable accurate analyses of optics surfaces and thin films as presented hereafter.

Sensitivity-improved calibration-free LIBS

Generally, the accuracy of any quantitative analytical method strongly depends on precise calibration using appropriate standards with well-known and well-defined chemical composition. Moreover, the chemical composition of the standards used for calibration should be as close to the chemical composition of the samples to be measured as possible. This issue can be overcome by using calibration-free LIBS (CF-LIBS), as first suggested by . Since then, this basic approach was successively refined [fu19] and CF-LIBS was used for thin film analysis by various authors [wid10,dav17]. Here, the analysis was based on the modeling of the emission spectrum of the laser-induced plasma [ciu99]. However, it turned out that the simple approaches used, where for example the plasma is assumed to be homogenous and uniform in terms of temperature and electron energy distribution and the effect of self-absorption is not considered, suffer from low accuracy [bul02]. These techniques are furthermore merely applicable to samples of simple composition, containing only a few elements. Higher accuracy can be obtained when correcting for self-absorption [axe14] and improved analysis is obtained when realizing experimental conditions generating a plume that can be well described by the simple model of a uniform plasma in local thermodynamic equilibrium (LTE) as described in [her14] and [her17]. For such a plasma, the relevant data electron density ne, plasma temperature T, concentration of an element Cx, and plasma dimension L can be derived from measuring the spectral radiance of the uniform plasma as described in detail in [ger14]. Here, the computed spectrum is iteratively approximated to the actually measured spectrum. This method is described in more detail in Chapter 5 of the present book. It has turned out to be a promising technique for quantitative elemental analysis of complex bulk materials, and especially optical glasses, where its analytical performance is comparable to the accuracy obtained with standard techniques [ger14]. The sensitivity can even be increased by further expansion of the measurement routine as presented in [che18]. This approach, sensitivity-improved calibration-free LIBS (SENSI-CF-LIBS), consists of a twostep procedure where two spectra with different time delays between the incident laser pulse and the detector gate are recorded as shown schematically in Figure 1. Major and minor elements are then quantified by the evaluation of the spectrum taken at the early time. Here, full LTE conditions are existent and Boltzmann equilibrium distributions of all plasma species are ensured by the large electron density. The analysis of a spectrum taken in partial LTE conditions at a later time further allows for the quantification of trace elements. This becomes possible since the continuum emission intensity is considerably lower in partial LTE. Low-intensity emission lines are thus observable with an improved signal-to-noise ratio. Such Sensitivity-Improved Calibration-Free LIBS allows for the quantification of trace elements and impurities in the range of merely some ppm. As described above, this is achieved by fitting the computed spectral radiance to the actually measured spectrum as illustrated in Figure 2 for spectral lines used for minor and trace element analyses in seafood [che18]. The possibility of calibration-free quantification of trace elements without any extensive sample cleaning or preparation offers a number of new fields of applications and analytical tasks for LIBS. An emerging field is the investigation of glasses where the impact of manufacturing steps on the chemical composition of optics surfaces is of specific interest. Here, the approach of sensitivity-enhanced calibration-free LIBS is a promising technique for gaining further insight and knowledge about the interaction of glasses with ambient media.

Analysis of optical materials and surfaces

Depth-resolved analysis of impurities

Optical components as for example lenses or prisms are usually manufactured by classical grinding, lapping and polishing [ger17]. The glass surface is thus in direct contact with different tools and operating materials in the course of the entire process. This leads to a certain contamination of the glass surface with traces from the manufacturing process, including for example wear debris from tools [lam02] or residues from polishing agents [nea05,sur15,ger17a]. Since such contaminants feature a gradual depth distribution [ger17b], a certain depth resolution is required for the investigation of manufacturing-induced impurities. Depth-resolved analysis of surfaces can be realized by different methods or techniques presented in the Introduction. Applying XRF, a certain depth resolution can principally be achieved by confocal Xray technology as recently reported [sun15]. However, obtaining depth-selective X-ray spectra is a challenging task [kan12] and the resolution is quite limited to the range of some tens of microns [nak09]. A very high depth resolution of generally a few nanometers [cha08] can be achieved by SIMS. This is due to its functional principle, the removal of thin layers from the sample surface by ion beam sputtering for signal generation [ben75]. Depending on the dose of ion irradiation, even depth resolutions in the range of some angstroms can be achieved [mah17]. It should however be noted that the incident ion beam might falsify the measurement results since the measured concentration depends on the etch rate of ions [kaa18]. The effect of surface sputtering is also used in some XPS-apparatuses where usually argon ion guns are applied for the removal of thin layers. The alternating layer removal and actual XPS measurement of the freshly generated surface allows for in-depth measurements where the resolution depends on sputter time. For instance, the sputter rate on fused silica is about 2 nm/minute for standard settings. However, as also valid for SIMS, ion implantation that occurs during sputtering potentially gives rise to a change in chemical composition [yam11] and may thus falsify the measurement results for deeper regions. This also applies to uncertainties caused by selective and thus non-stoichiometric sputtering [ekt00]. A certain depth resolution can thus also be realized without any sputtering, but by varying the angle of incidence of the exciting X-ray beam. This approach can also be applied for EDS analyses where, however, the penetration depth is generally significantly higher than for XPS. An -as a manner of speaking -indirect approach is the HF etching of thin glass layers with defined thickness and the subsequent analysis of the etched-off material, for example using ICP-AES [nea05,nea09]. This approach requires high carefulness in order to avoid a contamination of the gained sample material. The depth resolution depends on etching time but is generally lower than for SIMS and argon gun-assisted XPS. However, for a number of applications, such high resolution as achievable by ion sputtering techniques is not required.

Since during LIBS the ablation and thus information depth is in the range of some hundreds of nanometers to some microns, SENSI-CF-LIBS can be applied for the investigation of the depth distribution of near-surface contaminations. The limiting point in terms of depth resolution is the fluence required for ensuring the ignition of a plasma in LTE (see Chapter 5) and the accompanying ablation depth. For glasses, this fluence is about 100 J/cm², where the ablation or crater depth per pulse depends on the sample material. As shown in Figure 3, quite different values may be obtained for glasses due to differences in absorption coefficients, thermal conductivity and heat capacity [ger14]. Based on the determination of the crater depth per pulse, depth-resolved SENSI-CF-LIBS allows for the investigation of near-surface phenomena on glass interfaces. Comparable and extensive studies have been performed on fused silica by several authors where other analytical methods -mainly ICP-AES and SIMS -were applied as summarized in [pfi17]. Other glasses, and especially optical glasses, are notably less considered in literature. However, due to the high variety in chemical composition, insights in manufacturing process-glass surface interactions gained for the single-component quartz glass or fused silica cannot simply be applied to other glasses of much more complex composition. Calibration-free LIBS thus turns out to be a powerful approach for filling this lag in knowledge. As an example, the fractions of several trace elements, measured for classically manufactured polished heavy flint glass via SENSI-CF-LIBS, are presented in Figure 4 as functions of depth. This glass is of specific interest since it is used for quite different applications. Due to its dispersion characteristics and its high refraction power is serves as material for corrected optical systems such as achromatic lenses [ger17] or thin ophthalmic lenses. Featuring considerable nonlinear behavior and peak Raman gain it is also of high interest for the production of photonic crystal fibers for the generation of supercontinua [hus03,kal07]. The analysis presented in Figure 5 reveals quite different effects [ger21]: First, the concentrations of silver and titanium are very low and remain constant over the measured depth range [Figure 5(a)]. These elements are well-known trace contaminants in heavy flint glasses [sto71]. Second, the calcium concentration is quite high at the glass surface but decreases exponentially with increasing depth [Figure 5(b)]. After some microns, it approaches a final, constant value of about 50 ppm, which corresponds to the content of calcium within the investigated heavy flint glass [ger14]. Third, comparable to calcium, the magnesium and lanthanum signal is high at the surface and decreases continuously. At a depth of some microns, i.e. within the glass bulk material, merely smallest traces of magnesium and no lanthanum are detected since these elements are usually not existent in heavy flint glasses. The observed elevated content of calcium, magnesium and lanthanum at the surface and its exponential decrease over depth can be explained by contamination due to diffusion in the course of the manufacturing process. Here, the elements are provided by the used water and polishing agent, cerium oxide [kat00]. The different diffusion or penetration depths of 1.1 ± 0.2 μm, 1.0 ± 0.2 μm, and 1.8 ± 0.4 μm for lanthanum, calcium, and magnesium, respectively, can be explained by the unequal atom radii and thus mobility of these elements. This example demonstrates that SENSI-CF-LIBS has a high potential for the investigation of nearsurface effects that occur at glass and optics surfaces as for example contamination by trace elements [ger21b]. Apart from manufacturing-induced contamination, long-term degradations and modifications of glass surfaces could be analyzed by this technique. One effect is the accumulation of traces from the ambient air within micro cracks in the course of time. In many cases, such aging of glass surfaces leads to the formation of a grayish and hazy surface layer. This effect is well known, but not sufficiently investigated yet. Here, and for a number of other near-surface phenomena, SENSI-CF-LIBS will most probably serve as valuable analytical measurement method for further knowledge gain in glass chemistry and optics manufacturing technology.

Accuracy of sensitivity-improved calibration-free LIBS on glasses

For any measuring method or technique used for the quantification of minor elements, traces or impurities, precision is of essential importance. The accuracy of sensitivity-enhanced calibration-free LIBS is verified by comparing the elemental fractions deduced for the glass bulk material to values measured via ICP-AES as listed in Table 1 and visualized in Figure 5. It turns out that the elemental fractions deduced from the calibration-free LIBS measurements for the bulk material are in quite good accordance with the reference values measured via ICP-AES. The additional information gained by LIBS through depth-resolved measurements is precious for glass surface analysis as illustrated by the compositional differences between the bulk material and the near surface volume. This ability of LIBS analysis makes it particularity interesting as an analytical tool for quality control in the glass manufacturing industry.

Elemental analysis of thin films

Need of quality control in thin film manufacturing technology

Covering material surfaces with thin films is nowadays a standard in technological applications to functionalize surfaces with desired optical, electrical, mechanical or chemical properties. Among the most widespread applications are thin-film based photovoltaic devices, wear protective or tribological coatings for tools and mechanical devices, and coatings for optical surfaces or components. With the exponential increase of thin film applications over the last decades, specific techniques for their production and characterization have been developed. Beside the determination of crystallographical structure and optoelectronical properties, the measurement of the elemental composition is of great interest. Indeed, the thin film properties typically do not only depend on the major elements, but also on the minor and trace elements.

Compared to analysis of bulk matter, elemental analysis of thin films is challenging. The need of localized analysis of tiny volumes is incompatible with the standard analytical techniques such as inductively coupled plasma mass or atomic emission spectrometry (ICP-MS or ICP-AES), as these techniques require extensive sample preparation via digestion with acids [ole91,gro10]. The techniques commonly used for the elemental analysis of thin films are Rutherford backscattering spectrometry (RBS) and X-ray photoelectron spectrometry (XPS) [sie03,jey12]. Energy-dispersive X-ray spectrometry (EDS) is suitable for the analysis of layers having micrometer thickness. Beside the need to be operated under vacuum conditions, these techniques suffer low sensitivity and elements with mass fractions below 1% are generally not accurately quantified [cli94].

Compared to the traditional techniques of thin films elemental analyses, laser-induced breakdown spectroscopy has the advantages to be operational in atmospheric conditions and to be sensitive for minor and trace element analysis. Moreover, LIBS enables localized measurements, and is therefore compatible with the industrial requirements of an analytical tool for quality control in thin film manufacturing processes. The first thin film analysis via LIBS was reported by Cabalín and Laserna [cab01] for copper-based Manganin alloy coatings of 50 nm thickness, deposited by pulsed laser deposition (PLD) on silicon substrates. The authors demonstrated not only the capability of LIBS to analyze multi-elemental thin films but also the possibility of elemental mapping by scanning the laser beam over the sample surface.

The quantification of the compositional measurement was based on the comparison of the measured line intensities with those obtained for the bulk Manganin sample, assuming equal properties of the laser-produced plasma for both the thin film and the bulk target. According to the reduced laser fluence, that was applied to minimize the probe volume depth, the signal fluctuation was large. Semi-quantitative elemental measurements based on simple emission intensity ratio measurements were performed for other types of thin films [START_REF] Caneve | Laser-induced breakdown spectroscopy as a diagnostic tool for thin films elemental composition[END_REF][START_REF] Lee | Analysis of the absorption layer of CIGS solar cell by laserinduced breakdown spectroscopy[END_REF][START_REF] In | Reproducibility of CIGS thin film analysis by laserinduced breakdown spectroscopy[END_REF][START_REF] Choi | Effects of spot size variation on the laser induced breakdown spectroscopy analysis of Cu(In,Ga)Se2 solar cell[END_REF]. Most of the analyzed layers had micrometer thickness.

To improve the measurement accuracy, Aragón et al. [ara02] proposed to include in such measurements a step for checking the relevance of self-absorption, based on calculations of plasma emission in local thermodynamic equilibrium conditions. Such considerations where then further applied to correct the measured line intensities [wid10,dav17]. Other authors applied calibration-free LIBS to compositional measurements of thin films [acq06,yua10], neglecting however self-absorption in their calculations. Calibration-free LIBS analyses that account for self-absorption were proposed later for more accurate elemental analyses of thin films [pop11,axe14].

Monitoring of thin film synthesis

Apart from the use of laser-induced breakdown spectroscopy for analysis of thin films after their fabrication, LIBS was also used for in situ monitoring during the deposition process. The purpose of such spectroscopic measurements is to investigate the physico-chemical processes within the plasma and to correlate them to the thin film properties. A better understanding of the plasma chemistry is useful for process optimization. In addition, the plasma properties derived from the spectroscopic observations, such as plasma temperature or electron density, can be used for inline process control during thin film deposition. Plasma characterization via spectroscopic observations is commonly used to monitor thin film deposition via other plasma-based methods [koi05,kou06].

In pulsed laser deposition (PLD), a pulsed laser beam is focused onto a target sample to generate an energetic vapor plume under vacuum or in a low-pressure gas atmosphere. The vaporized material propagates towards a substrate placed in front of the target. Time-and space-resolved optical emission spectroscopy was proposed to characterize the ablated vapor plume during its propagation from the target towards the substrate, measuring the propagation velocities of atomic, ionic and molecular plume species and the associated temperatures of electronic and rovibrational motions [geo92,her95,viv98]. The knowledge of the kinetic and internal energies of species arriving on the substrate were than used as input data for molecular dynamics modeling of film growth [kub97].

The so-called reactive pulsed laser deposition was proposed to deposit composite thin films of high purity. Therefore, a pure single element target is irradiated in a low-pressure reactive gas to deposit a film composed by the product of the reaction between the ablated vapor and the gas [cra93].

Monitoring of the vapor-gas chemical reactions is illustrated in Figure 6 for reactive PLD of titanium oxide. According to the high plasma temperature during the early stage of plume expansion, emission of ionic transitions dominates the spectrum recorded close to the irradiated titanium target (a). With increasing distance and time of observation, the plasma temperature decreases and neutral atoms dominate the spectrum observed at a distance of 5.5 mm (b). For a further increase of the observation distance to 9.5 mm (c), molecular emission bands from the TiO ϒ-system dominate the plasma emission spectrum, illustrating that chemical reactions in the gas phase play a significant role in the titanium oxide thin film synthesis. According to the oxygen gas pressure of 70 Pa, the distance of 9.5 mm corresponds to the stopping distance of the plume predicted by the so-called drag force model [geo92,her95]. The observed strong oxidation is thus due to combined effects of plasma cooling and the high rates of vapor-gas collisions. Pulsed laser deposition is usually operated at lower pressure to make sure that the ablated species or those formed by chemical reactions reach the substrate with a kinetic energy appropriate for the thin film growth process [cra93].

In addition to the kinetic energy, the internal energy of plasma species has an influence on the thin film growth process. Beside the characterization of the electronic excitation via the excitation temperatures of atoms and ions, the rovibrational excitation of molecular species impacts the mechanisms of thin film deposition. Assuming Boltzmann equilibrium distributions of the population number densities of vibrational and rotational excitation levels, the rovibrational excitation of molecular species can be characterized by the corresponding temperatures, i.e. the vibrational temperature Tvib and the rotational temperature Trot. The temperatures Tvib and Trot can be deduced from Boltzmann diagrams similar to the determination of the electronic excitation temperature of atoms and ions [har97]. However, the intensity measurement of the individual rotational transitions is often hindered by their interference. Therefore, more accurate measurements of the rovibrational temperatures require the simulation of the molecular emission spectrum as illustrated for the CN violet system in Figure 7. The CN molecular emission was observed during investigations of carbon nitrite thin film synthesis via reactive PLD. The high rovibrational temperature in the vapor-gas contact front of the expanding plume is attributed to the formation of CN by recombination between carbon vapor atoms and nitrogen from the low-pressure ammonia atmosphere. According to the kinetic energy of the carbon atoms in the expanding vapor front, their recombination with nitrogen leads to CN radicals in highly excited rovibrational levels. The equality between rotational and vibrational temperatures shows that the collisional rates are large enough to ensure a collisional equilibrium between both the vibrational and the rotational degrees of freedom.

The equality Tvib = Trot was shown to apply generally in laser-produced plasmas in conditions of reactive PLD [viv98,her01]. Such plasmas are therefore expected to be in a state close to local thermodynamic equilibrium, and modeling of plasma chemistry via the simple statistical laws of LTE was thus proposed [her02].

Probe volume in LIBS analysis of thin films

The irradiation conditions in laser-induced breakdown spectroscopic experiments are mainly characterized by the laser pulse energy, the pulse duration and the focusing diameter on the sample surface. The focusing geometry may also influence the processes of laser ablation and plasma generation, as the effect of plasma screening depends on the numerical aperture of laser beam focusing. The influence of the focusing geometry is thus wavelength-dependent. It may be significant for infrared laser radiation while it is mostly negligible for ultraviolet radiation. In typical LIBS experiments, laser pulses of nanosecond duration and a few mJ pulse energy are focused to a spot diameter of about 100 µm on the sample surface. The incident laser fluence of about 100 Jcm -2 is two orders of magnitude larger than the threshold of laser ablation for most materials. Accordingly, the ablation depth produced by a single laser pulse is of the order of 1 µm for solid materials such as glasses [ger14] and alloys [sem99].

The ablation depth can be decreased by reducing the laser fluence via downscaling the pulse energy or through defocusing. The reduction of the laser fluence lowers however the quality of the analytical signal in LIBS measurements via two effects: (i) according to the lower laser intensity, the plasma temperature and thus the analytical signal intensity are reduced. (ii) the reproducibility of plasma generation diminishes with the laser fluence [cab01].

To avoid the loss of analytical signal quality, LIBS analyses are operated with a characteristic ablation depth larger than thin films of nanometer thickness. The probe volume of LIBS analysis, that is the volume to be transformed into a hot plasma, is typically smaller than the ablated volume as illustrated schematically in Figure 8. Accordingly, the probe depth is smaller than the ablated depth. The ratio between both depths is generally unknown. It depends on the sample material and the laser irradiation conditions. For films having a thickness of the order of 100 nm or thinner, the probe volume is supposed to include atoms from the substrate as illustrated in Figure 8(b). In that situation, calibrated LIBS is difficult to apply as the contribution of the substrate may alter the plasma properties. Compositional measurements of thin films are therefore a challenging application of calibration-free analysis.

Figure 8. (a) Scanning electron microscopic image of a cross section cut through a laser-produced crater in cobalt -cemented tungsten carbide covered with a TiCN coating (Adapted from [dum04]). (b, c) Cross section scheme of laser produced craters in samples covered with thin films of different thicknesses illustrating the impact of film thickness on the composition of the probe volume.

Accurate analysis of thin films via calibration-free LIBS

Analyses in ambient air

Most approaches of calibration-free LIBS analysis are based on the assumption of a spatially uniform plasma, characterized by unique values of temperature and electron density. Although this assumption was shown to apply in appropriate experimental conditions and in particular for LIBS experiments in argon background gas [her17], it is generally not valid for LIBS measurements in ambient air [her14].

Compared to an inert gas such as argon, a molecular gas like air interacts with the laser-ablated vapor plume through inelastic collisions during which the numerous vibrational and rotational levels are excited. This leads to cooling of the vapor in the vicinity of the vapor-gas contact front and thus to temperature gradients in the vapor plume. The simplest approach to account for these gradients is to describe the plasma by dividing it in two zones, representing the hot plasma core and the border of lower temperature (see Figure 9). In that case, the spectral radiance of the plasma in LTE can be computed via the following analytical solution of the radiation transfer equation [her98]

𝐵  = 𝑈 𝑝 (1 -𝑒 -𝜏 𝑝 ) + 𝑈 𝑐 (1 -𝑒 -𝜏 𝑐 )𝑒 -𝜏 𝑝 , ( 1
)
where U is the blackbody spectral radiance and  is the optical thickness. The subscripts c and p stand for the core and the peripheral plasma volumes, respectively. Details on the calculation of the spectral radiance and the implementation in the calibration-free LIBS measurement algorithm can be found in [axe14,her15]

Analyses in argon background gas

The analytical performance of calibration-free LIBS measurements is improved when the samples are irradiated in argon background gas. Beside the gain in signal-to-noise ratio, the spatially uniform character of the laser-produced plasma is of great interest as it enables accurate and robust modeling of the plasma emission spectrum [her17]. The irradiation in argon background gas was therefore chosen to evaluate the capability of analyzing multi-elemental thin films of thickness well below the depth of laser ablation. The first step in the computation scheme of the calibration-free LIBS analysis consists in the calculation of the LTE plasma composition as a function of temperature, electron density and the elemental fractions [her10, ger14] (see Chapter 5). Such calculations can be performed by solving numerically the system of Saha equations with the neutrality equation as closure relation [her02]. The computation is quasi instantaneous, even when a multi-elemental plasma composed of neutral and charged atomic and molecular species is considered. The composition of a plasma in LTE with the elemental composition of a nickel-chromiummolybdenum alloy is displayed in Figure 12 as a function of temperature. Here, the dependence of electron density versus temperature, deduced from measurements for different delays between the laser pulse and the detector gate, was applied as boundary condition [her19]. Thus, the composition computed for each temperature corresponds to the state of the plasma at a given time. The highest temperature values correspond to the earliest delays, where the plasma density is large, and accordingly the pressure is high. During the plume expansion, temperature, density and pressure decrease. The plume reaches a maximum volume at a delay of several microseconds. This corresponds to a minimum pressure, similar to the expansion dynamics of a classical explosion [her18]. The alloy-composing elements are characterized by rich emission spectra. Thus, to minimize measurement errors due to line-interference, the calibration-free analyses should be operated with spectra recorded with a large delay, for which the spectral lines are narrow according to reduced Stark broadening. The electron density should however be large enough so that the validity condition of local thermodynamic equilibrium is satisfied. The validity condition is rather relaxed for most metals and the LTE state is established for measurement delays up to several microseconds [her15]. Based on a detailed evaluation of the calibration-free LIBS measurement errors, the most appropriate measurement delay was found to be situated in the time interval from 1 to 2 µs [her19]. At this time, the temperature is close to 10,000 K and the dominating plasma species are singly-charged ions and neutral atoms (see Figure 12). Spectra recorded in argon for the bulk Inconel target and the thin film deposited via PLD are displayed in Figure 13 together with the spectra computed for a uniform LTE plasma. The displayed spectral windows show transitions of the major elements. Compared to line intensities observed for the bulk target, the spectral lines of molybdenum and niobium have significantly lower intensities in the spectrum recorded for the thin film.

The mass fractions deduced from the calibration-free LIBS analysis are displayed in Figure 14 for both the Inconel bulk target and the thin film. Similar values are observed for all elements except molybdenum, niobium and calcium. The reduced abundance of calcium within the thin film was attributed to a nonuniform distribution of calcium in the target. Indeed, in-depth measurements via calibration-free LIBS evidenced that the mass fraction of calcium is much larger at the surface of the Inconel target than in the bulk (see [her19], Supporting Information). During thin film deposition via PLD, the target is continuously rotated while it is irradiated with thousands of laser pulses. Accordingly, the total ablation depth is much larger than the depth that characterizes the calcium enrichment in the near surface volume. As the LIBS analysis of the Inconel target were performed on the virgin, nonirradiated surface, these measurements were representative of the near-surface volume of large calcium content. Contrarily, the thin film was only partly deposited with calcium-enriched material from the near-surface volume and most of the deposited material originated from the calcium-poor bulk alloy.

The change of the mass fractions of molybdenum and niobium, that were found to be about four times lower in the thin film, was confirmed by RBS analysis as shown in Figure 14(b). Non-stoichiometric mass transfer in pulsed laser deposition was often reported [arn99,kla16]. The possible causes are: (i) non-stoichiometric target vaporization; (ii) segregation in the vapor plume; and (iii) element-dependent sticking probability on the substrate surface. In the here reported case, nonstoichiometric target vaporization may be excluded as it would lead to the enrichment of the target with molybdenum and niobium, and therefore counterbalance non-stoichiometric target vaporization in case of multiple laser irradiation of the same site on the surface. However, multi-pulse laser irradiation generated a columnar structure (see [her19], Supporting Information) that is known to cause a deflection of the plume symmetry axis from the surface normal towards the laser optical axis, typically at 45° from the surface normal [cul06]. In case of strong plume deflection, the heaviest atoms, characterized by the narrowest angular distribution around the plume symmetry axis, will be mostly deposited beside the substrate and the deposited thin film is thus heavyatom deficient.

Conclusion

The results presented in this book chapter demonstrate that calibration-free laser-induced breakdown spectroscopy represents a powerful solution for the challenging problem of elemental analyses of optical surfaces and thin films, combining the capability of quantifying major, minor and trace elements with the ability of performing rapid measurements of tiny volumes. For analysis in ambient air, the simplest calibration-free approach, based on the assumption of uniform equilibrium plasma, is applicable as long as analytical spectral lines of negligible self-absorption are considered. In the opposite case, absorption at the cold plasma border has to be considered, and a two-zones model is shown to enable accurate compositional measurements. The analytical performance is increased for analysis in argon background gas, in particular due to the spatially uniform plasma distribution that enables accurate and robust modeling. In-depth measurements via the application of successive laser pulses on the same irradiation site are shown to be an efficient tool to investigate trace element impurities in the near surface volume. This is of specific interest for the clarification of phenomena on glass surfaces and especially manufacturing-induced contaminants and defects. Calibration-free LIBS measurements are foreseen to enable accurate analysis of thin films having thicknesses down to values of the order of 10 nm, given that the film-composing elements do not occur in the substrate. Challenges of such measurements are the reduction of the probe volume depth without loss of the validity condition of the calibration-free LIBS model. Other issues concern the need of accurate spectroscopic data that are still missing for many elements, and improvements of the CF-LIBS procedures such as a rapid measurement of the apparatus response function through the use of the laser-induced plasma as a radiation standard [tal21].

Figure 1 .

 1 Figure 1. Time scheme for sensitivity-improved calibration-free LIBS based on the measurement of two spectra at different times. Major and minor elements are quantified in conditions of full LTE at an early time, t1, whereas the concentration of trace elements is derived from the plasma in partial LTE at a later time, t2.(Adapted from [che18])

Figure 2 .

 2 Figure 2. Computed and measured spectra for minor and trace element analysis in seafood [sepia (a), sardine (b), and octopus (c)] using sensitivity-improved calibration-free LIBS. (Adapted from [che18])

Figure 4 .

 4 Figure 4. Mass fractions of trace elements measured as functions of depth using sensitivity-improved calibrationfree LIBS in classically manufactured heavy flint glass surfaces: (a) silver and titanium, (b) calcium, (c) magnesium, and (d) lanthanum. (Adapted from [ger21]).

Figure 5 .

 5 Figure 5. Comparison of mass fractions of major and minor elements within heavy flint glasses measured by sensitivity-improved calibration-free LIBS (SENSI-CF-LIBS) and inductively coupled plasma atomic emission spectroscopy (ICP-AES).

Figure 6 .

 6 Figure 6. Plasma emission spectra recorded during pulsed laser ablation of pure titanium in low-pressure oxygen for different distances from the laser-irradiated target. The recording delay was to the maximum of plasma emission intensity for each distance. (Adapted from [her99])

Figure 7 .

 7 Figure 7. Measured spectra and computer simulations of the Δυ = 0 vibrational sequence of the CN violet system for laser ablation of graphite in a low-pressure ammonia atmosphere. The recordings were performed at distances of 2 mm (a) and 6 mm (b) for delays of 500 ns and 300 ns, respectively. (Adapted from [viv99])

Figure 9 .

 9 Figure 9. (a) Scheme of the hemispherical ablation plume composed of hot core and cold periphery. (b) Approximate description of spatial distributions of plasma properties by two zones of different thermodynamic state. (Adapted from [her15])

  and in chapter 5 of this book. Thin film analyses via calibration-free LIBS in air are demonstrated for indium zinc oxide (IZO). The plasma emission spectrum is characterized by a few spectral lines only as shown in Figure10(a). All transitions of indium have high intensity and suffer strong self-absorption. In that case, a means to reduce the amount of self-absorption is given by setting the delay between the laser pulse and the detector gate to a short time. The strong plasma ionization leads then to the reduction of selfabsorption of transition from neutral atoms via two distinguished mechanisms: (i) according to the large stage of ionization, the number density of atoms is reduced; (ii) the optical thickness is further reduced due to Stark broadening of the spectral line profile resulting from the large electron density.

Figure 10 .

 10 Figure 10. (a) LIBS spectrum recorded during IZO thin film ablation in air for a delay of 400 ns between the laser pulse and the observation gate. (b-e) Comparison to the spectral radiance of Zn and In transitions computed according to Equation (1). (Reproduced from Ref. [axe14] with permission from the Royal Society of Chemistry)

Figure 11 .

 11 Figure 11. Atomic fraction of indium compared to the total metal content within the indium zinc oxide thin film versus the longitudinal position on the sample. The fractions measured by LIBS and EDS are represented by empty red and filled black symbols, respectively. The dashed lines represent the indium fractions of the targets used for thin film synthesis by combinatorial PLD. (Reproduced from Ref. [axe14] with permission from the Royal Society of Chemistry)

Figure 12 .

 12 Figure 12. Number densities of species as functions of temperature computed for a plasma in LTE with the elemental composition of a nickel-chromium-molybdenum alloy (Inconel 625). The calculations were performed for the ne = f(T) dependence deduced from the measurements. The calculated kinetic pressure is presented with respect to the secondary y-axis. (Adapted from [her19])

Figure 13 .

 13 Figure 13. Measured and computed spectral radiance of transitions from chromium, molybdenum, niobium, and nickel. The recordings were performed during ablation of (a) the bulk alloy sample and (b) the deposited thin film for t = 1.25 ± 0.25 μs. (Adapted from [her19])

Figure 14 .

 14 Figure 14. (a) Elemental compositions of the bulk alloy target and the thin film deduced from the spectra recorded for t = 1.25 and 2.50 μs. (b) The deduced fraction ratio Cfilm / Cbulk is compared to the ratio measured via RBS for the most-abundant elements. (Adapted from [her19])

Table 1 .

 1 Mass fractions of major, minor and trace elements in heavy flint glass deduced from the calibrationfree LIBS measurement for the surface and the bulk. Comparison to values measured via inductively coupled plasma atomic emission spectroscopy (ICP-AES). (Adapted from[ger21])

	Element	LIBS (surface)	LIBS (bulk)	ICP-AES
			Major (given in %)
	Pb	48.6	48.6	49.45
	Si	18.7	18.7	18.04
	K	4.4	4.4	3.50
	Na	1.5	1.5	1.21
	Ba	0.22	0.22	0.25
		Minor/traces (given in ppm)
	Al	200	100	68
	Ca	290	45	50
	Ti	16	16	13
	Fe	10	10	5
	Ag	6	6	4
	Mg	180	2	5.7
	Sr	3	1	1
	La	220	-	< 2
	Li	40	-	< 5
	Cu	6	-	< 3

Figure 3. Crater depth vs. number of successively applied laser pulses at a fluence of 100 J/cm² on different glasses, heavy flint glass, barium crown glass and fused silica.

Acknowledgements

The research leading to the results presented in this chapter has received funding from the EC's Seventh Framework Programme under grant agreement No 284464 Laserlab-Europe (Project CNRS-LP3001916) and the European Union's Horizon 2020 research and innovation programme under grant agreement No 654148 Laserlab-Europe (Project CNRS-LP3002491).