Fabrice Dubertret

GLOBAL CATEGORIZATION OF THE WORLD'S INDIGENOUS LAND AND RESOURCES RIGHTS

This working paper describes the process of establishing a global categorization of indigenous land and resources rights. From the analysis of a great variability of legislations regarding indigenous territories, common considered topics are identified, such as land security or the degree of indigenous control over development programs impacting their territories. Using them as analysis axes of the different laws, different classes of land and resources rights are identified, allowing a standardization of the description of the diversity of territorial rights benefiting indigenous peoples around the world.

INTRODUCTION

The situation of indigenous peoples has been on the global agenda for several decades. Although no consensus has been reached about a global definition of either the two concepts, it is commonly admitted that the notion of indigenous peoples differs from the larger class of minorities by a particular relationship to their traditional land and resources. Indigenous territories encompass the land and resources traditionally used by these people, and are deeply involved in their identity building. At the core of indigenous societies, land and resources have economic, political, cultural, and spiritual functions 1 . Thus, the maintenance of a certain degree of control over these territories is vital to their physical and cultural survival 2 . The recognition of secure rights over land and resources is essential to the integrity of indigenous societies and their well being.

At the international level, much has been done towards the international recognition of indigenous peoples' inherent rights through norms building and improvement, particularly regarding their territories. Yet, the local endorsement and implementation of these international instruments still depends on States will, and a wide variety of land and resources rights are recognized to indigenous peoples throughout the different regions and states of the world. Building a global overview of the territorial situation of indigenous peoples thus involves developing a categorization able to record and classify this diversity of their officially recognized land and resources rights. As the IUCN system for protected areas 3 , these categories shall standardize description of the particular bundle of land and resources rights locally recognized to indigenous peoples.

Through the fine study of international norms and State legislations regarding indigenous territories, the present document aims at building a hierarchized categorization allowing a global overview and comparison of existing rights. First will be presented a review of these laws and a global analysis framework for these rights. Then, a categorization model will be stemmed from the application of this framework to local legislations over indigenous land and resources.

I. DIVERSITY OF INDIGENOUS LAND AND RESOURCES RIGHTS THROUGH THE WORLD

I.1. INTERNATIONAL LAW AND VARIED LOCAL TRANSLATIONS

At international level, the two main normative instruments regarding indigenous peoples rights are the International Labor Organization Convention 169 of 1989 (C169) and the more recent United Nations Declaration on the Rights of Indigenous Peoples adopted in 2007. Both texts recognize the particular relationship linking indigenous peoples to their land and resources, its collective dimension, and affirm a right to property, possession, use and control over their traditional territories. Nevertheless, some differences exist between the two texts, especially concerning development projects affecting indigenous land and land rights security.

When the Declaration forbids any relocation of indigenous peoples from their land or the implementation of development projects affecting their territories without their free, prior and informed consent (art. 10 and 32, respectively), C169 only asks for their consultation without direction on how to deal with the results of these prospects, and displacement of indigenous peoples may occur when considered necessary as an exceptional measure (art. 15). Indigenous land and resources rights are thus weaker in C169 than in the Declaration, and States are given a certain degree of freedom in defining the "exceptional measures" justifying the relocation of indigenous peoples, or the process of consultation and its consequences.

Nevertheless, ILO convention 169 is actually the only legally binding international instrument regarding indigenous peoples rights. However, the UN Declaration, resulting from 20 years of direct negotiations between indigenous peoples and States representatives, is closer to indigenous aspirations, albeit accommodated to governments acceptability. Still, neither of these texts are coercive, the former needing state ratification and the later being only declarative. If they give a good insight of expected minima concerning the rights of indigenous peoples, their level of implementation in local and regional legislations is very diverse.

To date, only 22 countries have ratified C169 4 , and the fuzziness of some of its articles leaves flexibility in interpretation by governments. Even if bond by the same obligations, Norway considered for a long time the usufruct of land held in trust by the government a sufficient territorial right for Sapmis, when Columbia gives territorial autonomy to its resguardos indigenas which are inalienable and imprescriptible collective property of indigenous peoples. In other cases, international norms may substantially influence the conception of state laws independently from explicit endorsement of these norms : am ia's Lan Law f 2001 was directly inspired by ILO convention 169 recommendation while the country didn't ratify the text 5 . Thus, state legislations prevail international norms, and a global analysis of indigenous land and resource rights has to be made at local level.

I.2. GLOBAL FRAMEWORK FOR LEGISLATION ANALYSIS

Despite their very diverse modalities, legislations regarding indigenous land, resources and territorial rights deal with key topics, that are also approached in international norms and indigenous grievances :

 Natures of recognized rights Indigenous territorial rights can be either recognized as full property, or as temporary or permanent use right over land held in trust by a third party, in most cases the State. Such usufructs can be exclusive to indigenous peoples or shared with non-indigenous groups. Property rights generally induce exclusivity for the group of people or individuals to which it is recognized. In both cases indigenous peoples may have the right to control the access to their territories. These property and usufruct rights are generally restricted to surface land and resources, States keeping ownership of sub-surface resources in most cases.

 Level of land security

Land security is a central issue for indigenous peoples as they often face land dispossession or eviction, even when benefiting from officially recognized territorial rights. Considering the central importance of traditional land and resources within indigenous societies, such a loss may have considerable impact on their cultural survival and well being. Loss of indigenous land may happen through unilateral extinction of land rights by the State which can keep priority in land management, or through irreversible land transfer to nonindigenous people when allowed. History has shown that alienability of indigenous land threatens land security, especially when titles are individualized : US General Allotment Act (1887) and New Zealand Native and Acts (1865) reforms led in both case to a loss of two thirds of initial indigenous territories in a few decades 6 . Clauses of imprescriptibility, inalienability and un-morgageability protect indigenous land and resources rights in a number of countries, as New Caledonia, Australia, or 12 countries in Latin America. Some other proceed to a liberalization of indigenous land and resources rights, as Peru whose 1993 constitutional reform deleted the inalienable status of indigenous lands.

 Control over resource extraction and development projects

Indigenous land and resources rights are recognized within States frontiers. Thus, development projects can impact their territories, especially when it comes to resource extraction within indigenous lands, as subsurface generally stays state property. In such cases, depending on legislations, the project can either need indigenous Free Prior and Informed Consent (FPIC) before implementation, need simple information and consultation of impacted peoples without explicit need of consent, or be unilaterally decided and implemented by the State. Even when consent is needed, indigenous peoples can rarely oppose State development projects and this process is more of a right of negotiation over the implementation of the projects, its consequences and the share of benefits  Self determination and territorial autonomy Some governments decentralize their political, administrative, economic and/or administrative powers, giving degrees of sovereignty to indigenous peoples within their territories. The notion of autonomy here encompasses powers allowing a better territorial security and a certain level of indigenous self-decision in the political, cultural and/or economic spheres.

These common themes to the different legislations will thus be used to analyze and compare the laws on indigenous land and resources rights (see As can be seen in Table 1, some bundle of rights seems intrinsically linked. Low level of land security doesn't allow a high level of control over resources : as both land and resources rights often come together, prescription of land rights generally leads to an extinction of resources rights, and development project on indigenous land may lead to an extinction of their land right. Territorial autonomy comes with secured land rights and a high level of control over resources. These associated groups of rights help identifying classes for a global categorization of indigenous territorial rights, that can be hierarchized along the level of rights security and indigenous self-determination they provide.

II. GLOBAL CATEGORIZATION OF INDIGENOUS TERRITORIAL RIGHTS

Indigenous land and resources rights across the world can be divided in six global categories, allowing a standardization of description of the bundle of rights recognized to indigenous territories across the world. The framework proposed below describes the different categories identified along their global trends. Some legislation may naturally fall in a category when in other cases the attribution of one or the other will be less obvious. The categories are presented in hierarchical order along the level of rights security and indigenous selfdetermination they provide, in a descending order (I being the highest and VI being the lowest).

Category Ia: Property with territorial autonomy

Category Ia indigenous territorial rights are held on a full property basis of surface land and resources, that can be extended to sub-surface resources in some cases. They benefit of a certain degree of economic, political, cultural, legal or administrative autonomy, allowing indigenous self-determination within its borders. Thus, State decisions affecting those territories shall get indigenous peoples approval before implementation.

Greenland is an autonomous country within the kingdom of Denmark. The island has progressively been given increasing autonomy from Denmark, first with the 1979 home rule leading to the its decentralization, and lately by the 2008 Self-Government Act, giving the Greenlandic government responsibility for policing, judicial system, mineral resources activities, etc. Greenlandic Inuits being the majority of the local population and government (89% of the 55 000 inhabitants), Greenland can be considered as an autonomous indigenous territory.

Category Ib: Usufruct with territorial autonomy

Category Ib indigenous territorial rights are held in trust from a third party, generally the states, which keeps ownership official of land and resources. These territorial units benefit from a certain degree of economic, political, cultural, legal or administrative autonomy, allowing indigenous self-determination within its borders. Thus, States shall obtain indigenous peoples consent before implementation of any project affecting their territories.

Indian reservations within the

Category II: Protected property

Category II indigenous territorial rights are full property regimes over land and resources that may be extended to sub-surface resources in some cases. These territories are intended to stay at indigenous peoples' disposal as they are protected from alienation and extinction. Any activities that may affect them need indigenous approval before implementation.

The 1998 Noumea Accords recognizes the territorial dependence of Kanak identity in New Caledonia. They recognize customary property rights over lands to indigenous groups. These territories are inalienable, untransferable, imperceptible and indivisible. Kanaks can lease their land to companies and benefit from their activities.

Category III: Protected usufruct

Category III indigenous territorial rights are held in trust from a third party, generally the states, which keeps ownership official of land and resources. These territorial units are set aside by states for the benefit of indigenous peoples as they are inalienable and imprescriptible.

cti ities affecting them sha tain in igen s e es' a r a ef re im ementati n.

The Brazilian constitution of 1988 recognizes land rights to indigenous peoples over the land and resources necessary to their physical and cultural reproduction. They consist of an exclusive and permanent usufruct, inalienable and imprescriptible. Resource exploitation within these Indian territories need consultation and agreement of national congress and local populations before implementation.

Category IV: Liberal Property

Category IV indigenous territorial rights are full property rights over land and natural resources that can be transferred to non-indigenous on a voluntary basis. When such transfer occurs, alienated land will no longer benefit from the eventual particular status given to indigenous lands, such as needed consent before development project implementation.

Articles 23 to 28 of Cambodia land law (2001) recognize collective property titles over the traditional land and resources f " d m y " On a voluntary basis, indigenous peoples can leave the group benefiting from such collective ownership and get an adequate share of the land used by the community as an individual ownership. Then, this property will be transferable to non-indigenous.

Category V: Preferential usufruct

Category V indigenous territorial rights are usufruct rights over territories held in trust by third party, generally the State. Indigenous peoples are give exclusive or priority use of land and resources. However, these rights are unilaterally revocable by states, and indigenous peoples may not have the right to confront development project on their territories.

The Australian Native Title Act of 1993, gives aboriginal people the right to practice their law and customs over their traditional lands and waters. Thus, they can live, hunt, gather, fish, and access these land and resources. These rights can be exclusive to a community, restricting access to non members. If not, these land and resources rights will be Category VI.

Category VI: Restricted usufruct

Category VI indigenous territorial rights are usufruct benefiting indigenous peoples on land and resources held in trust by a third party, generally the State. The practice of indigenous traditional activities may be limited by restrictions over the range of allowed use of resources, or by share of these land rights with non indigenous groups, leading to competition. These rights are inferior to State rights and may be unilaterally revoked.

The land rights system of many African countries recognizes customary law and land tenure. These rights are generally held in trust over lands that were transferred to the state during the establishment of modern states that keeps ownership of the territories. In many cases, hunter-gatherers uses of land are not officially recognized, and thus indigenous peoples such as B w ("Pygmies") benefits from customary rights shared with the Bantu villages they are associated to 7 .

CONCLUSION

This draft framework for indigenous land and resource rights is built on the analysis of international norms, local and regional legislations, and the grievance of indigenous peoples regarding the territorial issues they are facing. As a draft, it aims at offering a basis for discussion, completion, modification and progressive refinement with the contribution of local and regional experts. As the analyzed corpus underlined the critical importance of traditional lands and resources in indigenous societies, rights security and the level of self-determination they provide naturally stood out for the categorization and its hierarchization. Yet, submitting this draft framework to the consideration of indigenous peoples and organizations may lead to another articulation of the categories along other priorities and shall thus be discussed. This categorization framework applies to lands and resources rights recognized to indigenous peoples. Nevertheless, not all territorial rights benefiting indigenous peoples are officially recognized as such. As an example, Indonesian government recognizes customary land rights over forests to komunitas adat terpencil (geographically-isolated customary law communities), internationally considered as indigenous peoples while the government argues that this concept is not applicable within the country. Such land and resources rights shall however be considered in this framework as they benefit directly indigenous communities and secures the tenure of their territories.

As the focus is on recognized territorial rights, it is beyond the scope of this study and framework to consider the level of implementation of these laws. Being part of a wider project aiming at building a World Atlas of Indigenous Territories, this classification will be applied to polygons / areas representing the extent of the recognized territories. Thus, lack of implementation of these rights will result in an absence of representation on the map such as a other absences of indigenous land and resources rights recognition. As these situations are frequent and considering the emergence of indigenous territorial claims through countermapping 8 project allowing them to map their territories independently from state institutions, representation of land claims waiting for, or being denied, recognition shall be considered, as they also constitute relevant information. However, if these territories call recognition by one or the other of these laws, they fall out of these categories until formal recognition. 8 This term refers to maps produced as alternatives of State maps, and generally used as political tool. It was first coined by Peluso, Nancy Lee. 1995. Whose Woods Are These? Counter-Mapping Forest Territories in Kalimantan, Indonesia. Antipode 27 (4): 383 406.

1

  Deroche, F., 2008 : un questionnement pour ' d m d . l'Harmattan, Paris, France. 2 Daes, E.-I.A., 2001. Indigenous peoples and their relationship to land; Daes, E.-I.A., 2004. , n a sia ain , nse er a e e i m iente, IUCN World Commissi n n Pr tecte reas, F n aci n i i ersi a , IUCN--The World Conservation Union, 2008. Guidelines for applying protected area management categories. IUCN, Gland, Switzerland.

7

  frican mmissi n n H man an Pe es' Rights, Uni ersit f Pret ria, entre f r H man Rights, International Labour Office, 2009. The overview report of the research project by the International Labour Organization and the African C mm H m d P ' R d v protection of the rights of indigenous peoples in 24 African countries. ILO, Geneva.

Table 1 : Sample of indigenous land and resources rights analysis grid

 1 Table 1 below). (grey cells are for weaker rights regarding rights security, when white stands for stronger ones)

	Country	Law	Nature	Exclusivity	Land security	Control over resources	Territorial Autonomy
	Australia Native Title Act, 1993	Usufruct	Yes or No	Prescriptible	Consultation
	India Constitution 1949, art. 244	Usufruct	No	Prescriptible	None
	Malaysia Aboriginal People Act, 1954	Usufruct	Yes	Prescriptible	Consultation
	Brazil Constitution 1988, art. 231	Usufruct	Yes Access control	Inalienable Imprescriptible	Consent (FPIC)
	Russia Federal Law, 2001	Usufruct	Yes Access Control	Inalienable Imprescriptible	Consent (FPIC)
	USA Indian Reorganization Act, 1934	Usufruct	Yes	Inalienable Imprescriptible	Consent (FPIC)	Tribal sovereignty
	Peru Constitution, 1993 (art. 88, 89)	Property	Yes	Alienable	Consent (FPIC)
	Cambodia Land Law, 2001	Property	Yes	Alienable	Consultation
	Australia	Aboriginal Land Rights (NT) Act, 1976	Property	Yes Access Control	Inalienable Imprescriptible	Consent (FPIC)
	New Caledonia	Accords de Nouméa, 1998	Property	Yes	Inalienable Imprescriptible	Consent (FPIC)
	Nicaragua	Constitution, 1987 Law 445, 2003	Property	Yes Access Control	Inalienable Imprescriptible	Consent (FPIC)	Autonomous regions RAAS, RAAN
	Nunavut	Nunavut Land Claim Agreement, 1993	Property	Yes	Inalienable Imprescriptible	Consent (FPIC)	Inuit majority in local government

Argentina, Bolivia, Brazil, Central African Republic, Chile, Colombia, Costa Rica, Denmark, Dominica, Ecuador, Fiji, Guatemala, Honduras, Mexico, Nepal, Netherlands, Nicaragua, Norway, Paraguay, Peru, Spain, Venezuela


Shiri Chechik
email: shiri.chechik@gmail.com

Quentin Godfroy
email: quentin@godfroy.eu

David Peleg
email: david.peleg@weizmann.ac.il

Multipath Spanners via Fault-Tolerant Spanners

published or not. The documents may come

Introduction

Consider a graph G = (V, E). An s-spanner H of a graph G is a spanning subgraph that preserves distances between all pairs of nodes within a factor of s, namely, such that δ(u, v, H) ≤ s • δ(u, v, G) for every two nodes u, v ∈ V , where δ(u, v, G ) for a graph G is the distance from u to v in G .

Graph spanners were introduced in [START_REF] Peleg | Graph spanners[END_REF][START_REF] Peleg | An optimal synchronizer for the hypercube[END_REF] in the context of distributed networks. It is well-known how to efficiently construct an s-spanner of size O(n 1+ 2 s+1 ) [START_REF] Althöfer | On sparse spanners of weighted graphs[END_REF], for an odd integer s. Spanners have numerous applications, such as synchronizers [START_REF] Peleg | An optimal synchronizer for the hypercube[END_REF], efficient routing [START_REF] Cowen | Compact routing with minimum stretch[END_REF][START_REF] Cowen | Compact roundtrip routing in directed networks[END_REF][START_REF] Peleg | An optimal synchronizer for the hypercube[END_REF][START_REF] Roditty | Roundtrip spanners and roundtrip routing in directed graphs[END_REF][START_REF] Thorup | Compact routing schemes[END_REF], broadcasting [START_REF] Farley | Spanners and message distribution in networks[END_REF], nearshortest path algorithms [START_REF] Elkin | Computing almost shortest paths[END_REF][START_REF] Elkin | A near-optimal distributed fully dynamic algorithm for maintaining sparse spanners[END_REF][START_REF] Elkin | Efficient algorithms for constructing (1 + , β)-spanners in the distributed and streaming models[END_REF], covers [START_REF] Awerbuch | Near-linear cost sequential and distributed constructions of sparse neighborhood covers[END_REF], dominating sets [START_REF] Dubhashi | Fast distributed algorithms for (weakly) connected dominating sets and linear-size skeletons[END_REF], distance oracles [START_REF] Baswana | Faster algorithms for approximate distance oracles and all-pairs small stretch paths[END_REF][START_REF] Thorup | Approximate distance oracles[END_REF], or emulators and distance preservers [START_REF] Bollobás | Sparse distance preservers and additive spanners[END_REF]. For recent reviews on spanners see [START_REF] Pettie | Low Distortion Spanners[END_REF][START_REF] Woodruff | Lower bounds for additive spanners, emulators, and more[END_REF].

This paper considers spanners for the multipath graph length. A p-vertex (resp., p-edge) multipath between two vertices u and v is a subgraph consisting of the union of p pairwise vertex-disjoint (resp., edge-disjoint) paths between u and v (except for the endpoints). The cost of a p-vertex (resp., p-edge) multipath between u and v is the sum of the weights of its edges.

For a weighted graph G and two vertices u and v, let δ p V (u, v, G) (resp., δ p E (u, v, G)) be the minimum cost of a p-vertex (resp., p-edge) multipath in G between u and v if one exists, and ∞ otherwise. We say that a subgraph H is a p-vertex (resp., p-edge) multipath s-spanner of

G if δ p V (u, v, H) ≤ s • δ p V (u, v, G) (resp., δ p E (u, v, H) ≤ s • δ p E (u, v, G))
for every two vertices u and v such that δ p V (u, v, G) = ∞ (resp., δ p E (u, v, G) = ∞). Our interest in the disjoint multipath graph length stems from the need for multipath routing in networks. Using multiple paths between a pair of nodes is an obvious way to aggregate bandwidth. Additionally, a classical approach to quickly overcome link failures consists in pre-computing alternate paths which are disjoint from the primary paths [START_REF] Kushman | R-BGP: Staying connected in a connected world[END_REF][START_REF] Pan | Fast Reroute Extensions to RSVP-TE for LSP Tunnels[END_REF][START_REF] Nasipuri | Performance of multipath routing for on-demand protocols in mobile ad hoc networks[END_REF]. Multipath routing can be used for traffic load balancing and for minimizing delays. It has been extensively studied in ad hoc networks for load balancing, fault-tolerance, higher aggregate bandwidth, diversity coding, minimizing energy consumption (see [START_REF] Mueller | Multipath Routing in Mobile Ad Hoc Networks: Issues and Challenges[END_REF] for a quick overview). Considering only a subset of links is a practical concern in link state routing in ad hoc networks [START_REF] Jacquet | Remote spanners: what to know beyond neighbors[END_REF]. This raises the problem of computing spanners for the multipath graph length, a first step towards constructing compact multipath routing schemes.

Edge-disjoint multipath spanners were first introduced in [START_REF] Gavoille | Multipath Spanners[END_REF], where the authors provided construction examples. More specifically, they showed how to construct a p-edge multipath spanner with O(pn 1+ 2 s+1 ) edges and stretch s • p. It was also shown that the factor p in the stretch can be discarded by an adhoc construction for p = 2 and s = 3. In [START_REF] Gavoille | Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners[END_REF] the authors proved that for every weighted graph one can efficiently construct a p-vertex multipath spanner with O(p 2 n 1+ 2 s+1 ) edges, but with a large stretch for large values of p (about (1 + p/s) s ).

In this paper, we significantly improve the stretch bounds from the two previous papers, using the related concept of fault-tolerant s-spanners, introduced in [START_REF] Chechik | Fault-tolerant spanners for general graphs[END_REF] for general graphs. We show that the constructions of edge-fault tolerant s-spanners from [START_REF] Chechik | Fault-tolerant spanners for general graphs[END_REF] and vertex-fault tolerant s-spanners from [START_REF] Dinitz | Fault-Tolerant Spanners: Better and Simpler[END_REF] can yield p-multipath sspanners, by fixing the right number of faults. Specifically, for edge multipath spanners we reduce the stretch from s • p to s, thus deriving edge multipath spanners with stretch-size tradeoff close to the best known bounds for standard spanners. For vertex multipath spanners we reduce the stretch bound from a function of both s and p to just s in the case of unweighted graphs, and to s • p in the case of weighted graphs, s being the stretch of the underlying fault-tolerant spanner.

More precisely, we show the following theorems.

Preliminaries

For a graph H and two vertices u and v, let δ(u, v, H) denote the distance between u and v in

H. A subgraph H of G is a spanner of stretch s (or, an s-spanner) of G if δ(u, v, H) ≤ s • δ(u, v, G) for every u, v ∈ V .
For a path P and two vertices x and y on it, let P [x, y] denote the subpath of P from x to y.

A graph H is an r-vertex (resp., edge) fault-tolerant s-spanner of G if for any set F ⊆ V (resp., F ⊆ E) of size at most r, the subgraph H \ F is an s-spanner of G \ F , where H \ F for a subgraph H and set of vertices F is the graph obtained by removing all vertices F from H together with their edges. Similarly H \ F for a subgraph H = (V , E ) and set of edges F is the graph (V , E \ F ).

For a subgraph H, let cost(H) denote the sum of weights of the edges in H. For a path P , let V (P ) be the set of vertices on P and let E(P ) be the set of edges on P . Similarly for a set of paths S, let V (S) = P ∈S V (P ) and E(S) = P ∈S E(P ). Consider two paths P 1 and P 2 between the same two vertices x and y. We say that P 1 and P 2 are internal vertex-disjoint if V (P 1 ) ∩ V (P 2 ) = {x, y}. We say that a path is an s-path if it is of length at most s.

Edge Disjoint Multipath Spanners

In this section we show that every edge fault-tolerant spanner is an edge multipath spanner with the same stretch, by fixing the right number of faults.

We begin by considering the unweighted case, and show later how to proceed with weighted graphs.

A set of paths B is called a set of edge-disjoint-s-bypasses of u and v if the paths in B are edge-disjoint s-paths between u and v.

Consider two vertices x and y and let S = {Q 1 , ..., Q p } be the set of p vertexdisjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) such that e ∈ E(S). The next lemma shows that G does not contain "many" edge-disjoint-s-bypasses, namely, edge disjoint s-paths between u and v, that intersect with the other paths of S. Lemma 1. Consider two vertices x and y and let S = {Q 1 , ..., Q p } be the set of p edge-disjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) ∈ Q i for some 1 ≤ i ≤ p. There are at most 2sp + 2p edge-disjoint-sbypasses between u to v, that intersect with E(S) \ E(Q i ).

Proof: Assume towards contradiction that there are more than 2sp + 2p edgedisjoint-s-bypasses between u and v that intersect with E(S) \ E(Q i ). Let B be the set of all these edge-disjoint-s-bypasses that intersect with E(S) \ E(Q i ). Let J be the set of indices j such that 1 ≤ j ≤ p, j = i and E(Q j ) ∩ E(B) = ∅. For an index j ∈ J, let e j h = (u j h , v j h ) be the edge in E(Q j ) ∩ E(B) closest to x in Q j , and let e j l = (u j l , v j l ) be the edge in

E(Q j ) ∩ E(B) closest to y in Q j . Let M j = [u j h , v j l ]
for j ∈ J and let M = j∈J M j . We show that it is possible to replace the set of edges E(M ) with a set of edges E such that the resulting graph contains p edge disjoint paths from x to y and its cost is less than cost(S) and thus derive a contradiction to the optimality of S.

We now explain how to gradually build the set of edges E . Roughly speaking, the set of edges E is the union of some prefixes and suffixes of the paths M j together with some edge-disjoint-s-bypasses from B.

Let p j = e j h (resp., s j = e j l ) be the prefix (resp., suffix) of M j . Our construction process will gradually add edges to these prefixes and suffixes.

Let tip(p j ) (resp., tip(s j )) be the edge in

E(p j ) ∩ E(B) (resp., E(s j ) ∩ E(B)) closest to y on Q j (resp., to x on Q j ).
We examine the set of tips of the prefixes and suffixes, and the set of edge-disjoint-s-bypasses B in which they appear. Let X be the set of prefixes and suffixes, namely, X = j∈J {p j , s j }. The set B is the set of edge-disjoint-s-bypasses containing one of the edges {tip(p j ), tip(s j ) | j ∈ J}. For an edge e ∈ E(B ), let B(e) be the edge-disjoint-s-bypass such that e ∈ E(B). Note that there is exactly one such edge-disjoint-s-bypass since the edge-disjoint-s-bypasses are disjoint. We say that a path P ∈ X is clean if the sub-path B(tip(e))[tip(P ), u] does not contain other edges from E(X). For an edge-disjoint-s-bypass B ∈ B , let P clean (B) be the path P ∈ X such that tip(P ) ∈ E(B) and P is clean; note that there is exactly one such path.

We say that a prefix p j ∈ X (resp., suffix s j ) is complete if p j • s j = M j . We apply the following process until all paths in X are clean. Choose an unclean incomplete path and add edges to it until it becomes clean. By adding an edge to a prefix p j (resp., suffix s j ) we mean adding the edge on M j adjacent to tip(p j ) (resp., tip(s j )) closest to y (resp., to x).

Note that it could happen that during this process some clean path becomes unclean. Note also that edge-disjoint-s-bypasses are only added to B (but never removed). Namely, B (t 1 ) ⊆ B (t 2 ) for t 1 ≤ t 2 , where B (t) is the set B in the t'th step of this process. To see this, note that the process does not add edges to P clean (B) for any B ∈ B . Thus in any stage of this process, B contains tip(P ) for P = P clean (B). Hence, by definition, B ∈ B . Notice that the path P clean (B) itself may change (since the process might add an edge to another path and this edge could belong to the path from tip(P ) to u).

We claim that B contains at most 2p edge-disjoint-s-bypasses. This follows directly from the fact that each edge-disjoint-s-bypass B ∈ B contains a different path P clean (B) and that there are 2p paths in X.

We now show that it possible to substitute the paths in M with "cheaper" paths and thus derive a contradiction to the optimality of S. For every incomplete prefix p j ∈ X, let p j be the clean subpath B(p j )[tip(p j ), u]. Similarly, let s j be the clean subpath B(s j )[u, tip(s j )]. For every index j ∈ J, if p j is complete then set

Q j = Q j , otherwise set Q j = Q j [x, u j h ] • p j • p j • s j • s j • Q j [v j l , y]. Let D = j∈J E(p j • s j ) and D = j =i E(M j ) \ (E(p j ) ∪ E(s j )). Let S = {Q 1 , ..., Q p }. Note that |E(S )| = |E(S)| + |D | -|D|.
It is not hard to verify that the paths Q j are disjoint and each of them leads from x to y. Moreover, M intersects with at least 2sp + 2p + 1 edge-disjoint-s-bypasses, and the set E(p j ) ∪ E(s j ) intersects with at most 2p edge-disjoint-s-bypasses, thus |D| > 2sp + 1. In addition, |D | ≤ 2sp. We get that |D| > |D | and thus cost(S ) < cost(S), contradiction.

We now show that edge fault-tolerant spanners constructed by the algorithm of [START_REF] Chechik | Fault-tolerant spanners for general graphs[END_REF] are also edge multipath spanners with the same stretch, by fixing the right number of faults. For completeness, we outline the algorithm and its properties that are essential for our needs. The algorithm operates in q iterations. Initially, set H = (V, ∅). In each iteration i, consider the graph G i = (V, E \ E(H)), and construct an s-spanner H i for this graph, (say, using the algorithm of [START_REF] Althöfer | On sparse spanners of weighted graphs[END_REF]), and add the edges of H i to the subgraph H.

We summarize the required properties for our purposes in the following lemma.

Lemma 2. [START_REF] Chechik | Fault-tolerant spanners for general graphs[END_REF] For every graph G = (V, E), odd integer s and integer q, one can efficiently construct in polynomial time a collection of edge disjoint subgraphs {H 1 , ..., H q } with the following properties. Let H be the union of the subgraphs {H 1 , ..., H q }.

(1) The number of edges in H is at most O(q • n 1+

Q i ) ≤ s • cost(Q i ). Let T i = {H j | (2sp + 2p + 1) • (i - 1)+ 1 ≤ j ≤ (2sp+2p+1)•i} for 1 ≤ i ≤ p. Note that E(T i ) contains 2sp+2p+1 edge-disjoint paths from u to v for every edge (u, v) / ∈ E(H). Moreover, the sets E(T i ) are disjoint for 1 ≤ i ≤ p.
The path Q i is constructed as follows. For every edge e ∈ E(Q i ) ∩ E(H) add e to Q i . For every edge e = (u, v) ∈ E(Q i ) \ E(H), consider the set B i with the maximum number of edge-disjoint-s-bypasses from u to v in T i . By Lemma 1, there are at most 2sp + 2p edge-disjoint-s-bypasses in B i that intersect with E(S) \ E(Q i ). Since B i contains at least 2sp + 2p + 1 edge-disjoint-s-bypasses, at least one edge-disjoint-s-bypass B(e) ∈ B i does not intersect with

E(S) \ E(Q i ). Add B(e) to Q i instead of e.
We claim that (1) the paths Q i for 1 ≤ i ≤ p are edge-disjoint, and ( 2) cost(S ) ≤ s • cost(S).

To see claim [START_REF] Althöfer | On sparse spanners of weighted graphs[END_REF], consider an edge e = (u, v) such that e ∈ E(Q i ) for some 1 ≤ i ≤ p. We consider two cases. The first case is when e ∈ E(Q i ). Note that e does not appear in any E(Q j ) for i = j, since the paths in S are disjoint. Moreover, e does not appear in any B(e ) for e ∈ E(Q j ) for some j = i. To see this, recall that B(e ) does not intersect with E(S) \ E(Q j ). The second case is when e ∈ B(ẽ) for some ẽ ∈ E(Q i ). The edge-disjoint-s-bypass B(ẽ) does not intersect with E(S) \ E(Q i ). Moreover, the edge-disjoint-s-bypass B(ẽ) does not intersect with any B(e ) for e ∈ E(Q j ) for some j = i. To see this, recall that

E(B(ẽ)) ⊆ E(T i ), E(B(e )) ⊆ E(T j ), and E(T i ) ∩ E(T j ) = ∅. It follows that the paths Q i are edge-disjoint for 1 ≤ i ≤ p.
To see claim [START_REF] Awerbuch | Near-linear cost sequential and distributed constructions of sparse neighborhood covers[END_REF], note that for every edge e ∈ E(Q i ), either e itself or an alternative path of length s is added to

E(Q i ). We get that cost(Q i ) ≤ s • cost(Q i ). Claim (2) follows.
Weighted Graphs. We now show the modifications needed for weighted graphs. Assume the minimal edge weight is 1 and let ω be the maximal edge weight. We now describe the algorithm for constructing p-edge multipath s-spanner.

Initially, set H = (V, ∅). Consider the graphs G i = (V, E i ) such that E i = {e ∈ E | 2 i-1 ≤ ω(e) ≤ 2 i } for every 1 ≤ i ≤ log ω . Construct the collection of subgraphs F i = {H 1 , ..., H 4sp 2 +2p 2 +p } of Lemma 2 for parameters s and q = 4sp 2 + 2p 2 + p on the graph G i . Add E(F i ) to H.
We claim that H is a p-edge multipath s-spanner. The analysis is very similar to the unweighted case. We now outline the slight changes.

Here we call a set of paths B a set of edge-disjoint-s-bypasses of two nodes u and v that are connected by an edge if the paths in B are edge-disjoint paths between u and v of length at most s • ω(u, v) each.

Consider two vertices x and y and let S = {Q 1 , ..., Q p } be the set of p edgedisjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) ∈ Q i for some 1 ≤ i ≤ p. Let i be the index such 2 i-1 ≤ ω(e) ≤ 2 i . In Lemma 1 we prove that the graph (V, E(F i )) contains at most 4sp + 4p edge-disjoint-sbypasses B from u to v. Note that since the weight of the edges in the edgedisjoint-s-bypasses B could be half the weight ω(e), we double the factor of sp 2 in the number of edge-disjoint-s-bypasses. The rest of the proof of Lemma 1 is similar to the unweighted case.

The proof of Theorem 4 is also similar to the unweighted case, where for each edge e = (u, v) ∈ Q j for some 1 ≤ j ≤ p such that e / ∈ E(H), we pick an edge-disjoint-s-bypass from F i that does not intersect E(S) \ E(Q j ), for i such that 2 i-1 ≤ ω(e) ≤ 2 i .

We thus conclude with Theorem 1.

Vertex Disjoint Multipath Spanners

In this section we show that every vertex fault-tolerant s-spanner is a vertex multipath spanner with the same stretch, by fixing the right number of faults.

Note that it is unclear how to generalize the analysis from the previous section to vertex disjoint multipath spanners. To see this, recall that in the previous section we consider a set S = {Q 1 , ..., Q p } of p vertex-disjoint paths from x to y in G of minimal cost. We claim that every edge e ∈ E(Q i ) does not contain too many bypasses that intersect with the other paths of S. To prove this claim, we substitute sub-paths of each Q j with some E-bypasses of the edge e = (u, v). All these E-bypasses are edge disjoint but not vertex-disjoint. Specifically, all these E-bypasses contain the nodes u and v. Therefore, it is unclear how to use these E-bypasses to substitute multiple sub-paths and stay with vertex disjoint paths. We thus present a different analysis for vertex disjoint multipath spanners at the price of slightly increasing the size of the spanner. Moreover, our analysis for vertex disjoint multipath spanners works only for unweighted graphs. We later show a simple construction for weighted vertex multipath spanners with stretch sp (instead of s).

A subgraph H is q-vertex-resilient with stretch s if for every edge e = (x, y) ∈ E, either e ∈ E(H) or H has at least q internal vertex-disjoint s-paths between x and y. For a path P between two nodes x and y and a vertex v ∈ V (P ), let index(v, P ) be the distance (number of hops) between x and v in P . Two paths are said to intersect if they have at least one common vertex.

A set of paths B is called a set of vertex-disjoint-s-bypasses of u and v if the paths in B are internal vertex-disjoint s-paths between u and v. The next lemma shows that every vertex fault-tolerant s-spanner H has "many" vertex-disjoints-bypasses between u and v for every edge e = (u, v) in E \ E(H).

Lemma 3. Every r-fault tolerant s-spanner is r/(s -1) -vertex-resilient with stretch s.

Proof: Consider an r-fault tolerant s-spanner H. Consider an edge e = (u, v) ∈ E\E(H). We need to show that H contains r/(s-1) vertex-disjoint-s-bypasses. Assume towards contradiction that H contains only k vertex-disjoint-s-bypasses between u and v such that k < r/(s -1) . Let B be the set of these k vertexdisjoint-s-bypasses. Note that V (B)\{u, v} contains at most (s-1)•k < r vertices. Fix the set of vertices F = V (B) \ {u, v} to be faulty. Since the subgraph H is an r-fault tolerant s-spanner, by definition H \ F contains an s-path between u and v. Therefore H contains more than k vertex-disjoint-s-bypasses between u and v, contradiction.

Throughout, we consider a graph G(V, E). Consider two vertices x and y and let S = {Q 1 , ..., Q p } be a set of p vertex-disjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) in one of the paths of S. The next lemma shows that G does not contain "many" vertex-disjoint-s-bypasses, namely, internal vertex disjoint s-paths between u and v, that intersect with the other paths of S. Lemma 4. Consider two vertices x and y and let S = {Q 1 , ..., Q p } be a set of p vertex-disjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) ∈ Q i and / ∈ H for some 1 ≤ i ≤ p. There are at most 2sp(p -1) + 2p(p -1) vertex-disjoint-s-bypasses between u and v that intersect with V (S) \ V (Q i ).

Proof: Assume towards contradiction that there are more than 2sp(p -1) + 2p(p -1) such vertex-disjoint-s-bypasses that intersect V (S) \ V (Q i ). By the Pigeonhole principle, there exists a path Q j for some j = i such that at least 2sp + 2p + 1 of these vertex-disjoint-s-bypasses intersect with Q j . Let B be the set of all these vertex-disjoint-s-bypasses that intersect Q j . For every vertexdisjoint-s-bypass A ∈ B, let top(A) be the earliest vertex of A on Q j , i.e., the vertex in V (A) ∩ V (Q j ) with minimal index(top(A), Q j ), and let bottom(A) be the last vertex of A on Q j , i.e., the vertex in V (A) ∩ V (Q j ) with maximal index(top(A), Q j ). Let B h be the set of p vertex-disjoint-s-bypasses A ∈ B with minimal index(top(A), Q j ) and let B l be the set of p vertex-disjoint-s-bypasses A ∈ B with maximal index(bottom(A), Q j ). Let A h ∈ B h be the vertexdisjoint-s-bypass with maximal index(top(A h ), Q j ) and let q h = top(A h ). Let A l ∈ B l be the vertex-disjoint-s-bypass with minimal index(bottom(A l ), Q j ) and let q l = bottom(A l ). Let M = Q j [q h , q l ] (i.e., the subpath of Q j from q h to q l ). See Figure 1 for illustration. We claim that (1) the subgraph

H (V, S ) for S = (E(S) \ E(M )) ∪ E(B h ) ∪ E(B l ) contains p vertex-disjoint paths from x to y and (2) cost(S ) ≤ cost(S).
To prove claim (1) we use Menger's theorem. We show that there is no set F of p -1 vertices such that x and y are disconnected in S \ F . Consider a set F of at most p -1 vertices. If F fails to intersect a path Q r ∈ S, for some r = j, then clearly x and y are connected in S \ F . So suppose the set F disconnects every path Q r ∈ S, for r = j, hence F contains exactly one vertex from each path Q r ∈ S for every r = j. In particular, F contains only one vertex of Q i . Therefore, one of u or v is not in F . Assume without loss of generality that u / ∈ F . Note that both sets B h and B l contain p vertex-disjoint-s-bypasses.

Since F contains at most p -1 vertices, there must be a vertex-disjoint-s-bypass B h ∈ B h and a vertex-disjoint-s-bypass B l ∈ B l whose internal vertices are not in F . Let x 1 = top(B h ) and y 1 = bottom(B l ). Note that the subpaths

Q j [x, x 1 ] and Q j [y 1 , y] do not contain any vertex from F , as F ∩ V (Q j ) = ∅.
Moreover, the vertex-disjoint-s-bypasses B h and B l contain subpaths B h [x 1 , u] and B l [u, y 1 ] that do not intersect F . Concatenating all these paths together, we get a path

Q j [x, x 1 ]•B h [x 1 , u]•B l [u, y 1 ]•Q j [y 1
, y] from x to y. We thus conclude that H contains p vertex-disjoint paths from x to y, establishing [START_REF] Althöfer | On sparse spanners of weighted graphs[END_REF]. Next, we show claim [START_REF] Awerbuch | Near-linear cost sequential and distributed constructions of sparse neighborhood covers[END_REF]. Recall that B contains at least 2sp + 2p + 1 vertex-disjoints-bypasses where each of which intersects Q j . Moreover, each of the subpaths Q j [x, q h ] and Q j [q l , y] intersect with exactly p vertex-disjoint-s-bypasses from B. We get that the remaining part of Q j , namely, the path M = Q j [q h , q l ], intersects with at least 2sp + 2p + 1 -2p = 2sp + 1 vertex-disjoint-s-bypasses from B. Thus, the length of M is at least 2sp + 1. In contrast, the number of edges in the edge collection E(B h ) ∪ E(B l ) that replaced M in S is at most 2ps. Hence, cost(S ) < cost(S).

Finally parts ( 1) and ( 2) of the claim imply a contradiction to the optimality of S. The lemma follows.

Let f = ((4s + 2)(p -1)s + 1 + 2sp(p -1) + 2p(p -1)).

Lemma 5. Every f -vertex-resilient subgraph H is a p-vertex disjoint multipath spanner.

Proof: Consider two vertices x and y and let S = {Q 1 , ..., Q p } be the set of p vertex-disjoint paths from x to y in G of minimal cost. Consider an edge e = (u, v) ∈ E(Q i ) such that e / ∈ E(H) for some 1 ≤ i ≤ p. By definition of H, H contains f vertex-disjoint-s-bypasses between u to v. By Lemma 4, there are at most 2sp(p -1) + 2p(p -1) vertex-disjoint-s-bypasses between u to v, that intersect V (S) \ V (Q i ). We thus get that there exists a set Bypasses(e) of at least f -2sp(p -1) -2p(p -1) vertex-disjoint-s-bypasses between u to v in H, that do not intersect V (S) \ V (Q i ). We now show how to select for each edge e ∈ Q i for some i a vertex-disjoint-s-bypass B e ∈ Bypasses(e), such that B e is vertex disjoint with any B e for any e ∈ Q j such that e / ∈ H and j = i. Consider an edge e = (u, v) ∈ Q i such that e / ∈ E(H). Let E e be the set of edges e such that e ∈ E(Q j ) \ E(H) and V (B) ∩ V (B ) = ∅ for some j = i, B ∈ Bypasses(e) and B ∈ Bypasses(e ). Towards proving Lemma 5, we first prove the next auxiliary lemma. Lemma 6. For every edge e ∈ E(S) \ E(H), the set E e contains at most (4s + 2)(p -1) edges Proof: Assume, towards contradiction, that |E e | ≥ (4s + 2)(p -1) + 1. By the Pigeonhole principle, there is a path Q j (for j = i) such that |E(Q j ) ∩ E e | > 4s+2. Let e h = (u h , v h ) be the edge in E(Q j )∩E e closest to x in Q j , and let e l = (u l , v l ) be the edge in E(Q j ) ∩ E e closest to y in Q j . Let h 1 , h 2 ∈ Bypasses(e), h 3 ∈ Bypasses(e h ) and h 4 ∈ Bypasses(e l ) such that h 1 and h 3 intersect and h 2 and h 4 intersect (it could be that

h 1 = h 2 ). Let M be the subpath Q j [v h , v l ].
We now claim that (1) the subgraph H (V, S ) for S = E(S) \ E(M ) ∪ E(h 1 ) ∪ E(h 2 ) ∪ E(h 3 ) ∪ E(h 4 ) contains p vertex disjoint paths from x to y and (2) cost(S ) < cost(S).

We show claim (1) by using Menger's theorem to establish that S contains p vertex-disjoint paths from x to y. Consider a set F of at most p -1 vertices. If F fails to intersect a path Q r ∈ S, for some r = j, then clearly x and y are connected in S \ F . So suppose the set F disconnects every path Q r ∈ S, for r = j, hence F contains exactly one vertex from each path Q r ∈ S for every r = j. Note that all vertices in h 3 and h 4 are not in F as h 3 and h 4 are disjoint from all Q r for r = j and we assume that F contains only nodes from Q r for some r = j. Since F contains exactly one vertex in Q i then one of u and v are not in F , assume w.l.o.g. that u / ∈ F . Let r 3 be a vertex in h 3 ∩ h 1 and let r 4 be a vertex in h 4 ∩ h 2 . Note that the subgraph (E(Q j ) \ E(M )) ∪ E(h 3 ) contains a path from x to r 3 that does not intersect F . Similarly, the subgraph (E(Q j ) \ E(M )) ∪ E(h 4 ) contains a path from r 4 to y that does not intersect F . The cycle h 1 ∪ {(u, v)} contains at most one vertex in F and thus there is a path from r 3 to u that does not contain vertices from F . Similarly, h 1 ∪ {(u, v)} contains a path from r 4 to u that does not contain vertices from F . Concatenating all these paths together we get a path from x to y. Claim (1) follows. Next, we show claim (2) and thus derive a contradiction to the optimality of S. the path Q j contains at least 4s+3 edges from E e and since the path M contains all these edges but two (e h and e l ), the length of M is at least 4s + 1. In contrast, the number of edges in the edge collection E(h 1 ) ∪ E(h 2 ) ∪ E(h 3 ) ∪ E(h 4 ) that replaced M in S is at most 4s. We thus get that cost(S ) < cost(S). This implies a contradiction to the optimality of S. The lemma follows.

Consider the edges e ∈ E(S) \ E(H) one by one. For each edge e ∈ E(Q i ) \ E(H), choose a vertex-disjoint-s-bypass B e that does not intersect with any B e for an edge e that was already considered by this process and such that e ∈ E(Q r ) \ E(H) for some r = i. We claim that this process never gets stuck, namely, each time we consider an edge e ∈ E(Q i ) \ E(H), there is at least one vertex-disjoint-s-bypass in Bypasses(e) that does not intersect with the other vertex-disjoint-s-bypasses selected so far. Let Ẽe ⊆ E e be the set of edges that were considered before e by this process. Note that | Ẽe | ≤ (4s + 2)(p -1) by Lemma 6. Moreover, note that each path B e for some e ∈ Ẽe intersects with at most s vertex-disjoint-s-bypasses in Bypasses(e). Since there are more than (4s + 2)(p -1)s vertex-disjoint-s-bypasses in Bypasses(e), at least one of these vertex-disjoint-s-bypasses does not intersect with any of B e for e ∈ Ẽe .

For each path Q r ∈ S for 1 ≤ r ≤ p, construct a path Qr as follows. For every edge e ∈ E(Q r ), if e ∈ E(H) then add e to Qr , otherwise add B e to Qr . It is not hard to verify that V (Q i ) ∩ V (Q j ) = ∅ for any i = j and that each Q r is a path from x to y such that cost( Qr ) ≤ s • cost(Q r ). The lemma follows.

The following theorem was shown by Dinitz and Krauthgamer in [START_REF] Dinitz | Fault-Tolerant Spanners: Better and Simpler[END_REF]. Theorem 5. [START_REF] Dinitz | Fault-Tolerant Spanners: Better and Simpler[END_REF] For every graph G = (V, E), odd integer s and integer r, one can construct in polynomial time with high probability a r-vertex fault-tolerant s-spanner with O r 2-2 s+1 n 1+ 2 s+1 log n edges.

Combining Theorem 5, Lemma 3 and Lemma 5, we get Theorem 2. We note that for weighted graphs, every p-vertex-resilient H with stretch s is a p-vertex multipath (s • p)-spanner. To see this, consider two vertices x and y and let S = {Q 1 , ..., Q p } be the set of p vertex-disjoint paths from x to y in G of minimal cost. We now show how to construct a subgraph H (V, S ) such that (1) H contains p vertex-disjoint paths from x to y and ( 2) cost(S ) ≤ s • cost(S).

Initially, set S = ∅. For every edge e = (u, v) ∈ E(Q r ), if e ∈ E(H) then add e to S , otherwise add to S a set B(e) of V -bypasses such that |B(e)| = p and E(B(e)) ⊆ E(H). Note that such a set B(e) exists since H is p-vertex-resilient with stretch s.

To prove claim (1) we use Menger's theorem. We show that there is no set F of p -1 vertices such that x and y are disconnected in S \ F . Consider a set F of at most p -1 vertices. Note that, for every edge e ∈ (E(Q r ) \ E(H)), there exists a V -bypass B(e) ∈ B(e) that is internal vertex disjoint from F . To see this, recall that B(e) contains p V -bypasses. In addition, there exists at least one path Q r ∈ S such that V (Q r ) ∩ F = ∅ for some 1 ≤ r ≤ p. Construct the path Q r as follows. For every edge e = (u, v) ∈ E(Q r ), if e ∈ E(H) then add e to Q r , otherwise add the alternative path B(e) to Q r . It is not hard to verify that Q r leads from x to y, E(Q r ) ⊆ E(H), and V (Q r ) ∩ F = ∅. Claim (1) follows.

To see claim [START_REF] Awerbuch | Near-linear cost sequential and distributed constructions of sparse neighborhood covers[END_REF], note that for every edge e ∈ E(S), either e itself or an alternative path of length s is added to E(S ). We get that cost(S ) ≤ s•cost(S).

We note that Lemma 3 can be generalized to weighted graphs. This can be done by invoking a construction for s-spanner, in the algorithm for constructing vertex fault-tolerant spanners of Dinitz and Krauthgamer in [START_REF] Dinitz | Fault-Tolerant Spanners: Better and Simpler[END_REF], that satisfies the following property, defined in [START_REF] Gavoille | Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners[END_REF]. Every edge e is either included in the spanner H or H contains an alternative path to e of length at most s • ω(e) and with at most s hops. The details are omitted.

Combining with Theorem 5, we conclude Theorem 3.

Fig. 1 .

 1 Fig. 1. Illustration of the sets B h , B l (p = 2) and the path M

  2

Supported in part by the Israel Science Foundation (grant 894/09), the United States-Israel Binational Science Foundation (grant 2008348), the Israel Ministry of Science and Technology (infrastructures grant), and the Citi Foundation. Supported by the Institut Universitaire de France.


Cyril Voyant
email: voyant@univ-corse.fr

Marie Laure Nivet

Christophe Paoli

Marc Muselli

Gilles Notton

Meteorological time series forecasting based on MLP modelling using heterogeneous transfer functions

établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The time series (TS) formalism is useful in many scientific fields [START_REF] Behrang | The potential of different artificial neural network (ANN) techniques in daily global solar radiation modeling based on meteorological data[END_REF][START_REF] Crone | Stepwise selection of artificial neural networks models for time series prediction[END_REF][START_REF] De Gooijer | 25 years of time series forecasting[END_REF]. In the particular case of the meteorology, the prediction is essential to anticipate weather variation and thus to prevent the population of potential risks, but it can also be used for the energy management (intermittent energy sources switching e.g. global solar radiation or wind speed) [START_REF] Duchon | Time Series Analysis in Meteorology and Climatology: An Introduction[END_REF][START_REF] Hocaoglu | Stochastic approach for daily solar radiation modeling[END_REF][START_REF] Kalogirou | Artificial neural networks in renewable energy systems applications: A review[END_REF][START_REF] Mellit | Artificial intelligence techniques for photovoltaic applications: A review[END_REF]. The measured series are often seasonal and noised; they have repetitive and more or less predictable fluctuations (24 hours and 1 year). The noise increases when the time step between measurements decreases. It is essential to take into account periodicities and to build a predictor with seasonal adjustments [START_REF] Voyant | Multi-horizon solar radiation forecasting for Mediterranean locations using time series models[END_REF]. In this paper, we suggest to study periodic meteorological TS measured during 11 years in Ajaccio (France; at an hourly step) and concerning four kinds of data with different degrees of periodicity: solar irradiation (Wh/m 2 , [START_REF] Hocaoglu | Stochastic approach for daily solar radiation modeling[END_REF]), humidity (%), ground temperature (•C) and wind velocity at 10 meters from the ground (Beaufort scale) [START_REF] Warner | Numerical Weather and Climate Prediction[END_REF]. The variation coefficients (VC; standard_deviation/mean) of these series are respectively: 1.5, 0.2, 0.4 and 0.5. This coefficient represents the variability and the seasonality of the series; the high values are often related to bad prediction results. In the next section, we will present the one hour ahead prediction methodology based on the heterogeneous transfer functions multilayer perceptron (MLP) and on a particular time index taken as input. Then the results of predictions and the comparison between different architectures will be exposed; finally in the last part, we will analyze the results and will draw conclusions.

Methods

In this section, we first introduce the global methodology based on the heterogeneous transfer functions MLP that is to say the fact to mix transfer functions within on network [START_REF] Duch | Transfer functions: hidden possibilities for better neural networks[END_REF]. Next, we present the different meteorological data estimation methodologies used during the cross-comparison. .

MLP with heterogeneous transfer functions

A classical MLP with one hidden layer is, in the time series (x(t)) prediction context, defined by equation 1 where W 1 ,b 1 and W 2 ,b 2 are the weights and biases matrices of the hidden and output layers and f the transfer function of the hidden layer (note that in our case, the transfer function of the output layer is the identity function). The tapped delay line (p delays) is defined from the lag operator (L) by [ ] considering that . With this notation, the output of the MLP becomes [START_REF] Crone | Stepwise selection of artificial neural networks models for time series prediction[END_REF].

(

) 1
Often a hyperbolic tangent function (or similar function) is used for f. In this study we propose to combine two types of transfer function in the hidden layer: bijective and non-bijective. As the first one allows activating a specific hidden node once the argument is upper than the bias; the second one allows to introduce an excitation/inhibition balance in the system: low and high signals will have an inhibition effect. We choose to test respectively the hyperbolic tangent function (noted tanh) and its derivative. Figure 1 represents these two functions types and the scaled form of the non-bijective transfer function (expanded between -1 and 1). Fig. 1: In blue the tanh function and in red its derivative (= 1-tanh²). The green curve represents the scaled form of (tanh)' With this modification, the new network is defined by [START_REF] Duch | Transfer functions: hidden possibilities for better neural networks[END_REF], where W 1' and b 1' define the weights and biases related to the non-bijective nodes.

( ) (2) ( )
The difference between the "classic" and the heterogeneous transfer functions MLP is related to the two following expressions:

( ) (3)
If we pose where is the asymmetry rate, and , we obtain that in the classic case the output is related to while in the heterogeneous transfer functions MLP case it is related to In figure 2 are shown these two types of outputs related to linear combination of inputs (u) and to If is upper than 0.5 then the global output is non-bijective and the inhibition phenomenon becomes leading. Concerning the low values of the output is not between -1 and 1 but between -0.3 and 1.7 (shift of 0.7). 

Meteorological data forecast

The test and validation process of the proposed methodology consists in a cross-comparison with some classical tools usually proposed in literature in order to make Meteorological data forecasting. These different methodologies of prediction are tested through the two last years of measurements, all the others data are related to learning step of the MLP.

Persistence

The first studied prediction methods is the persistence method; the simplest way of producing a forecast. The persistence method assumes that the actual conditions will not change. To improve the results and to take into account the fact that the TS is more or less periodical, we corrected the persistence with a scale term computed from the moving average related to the nine first years [START_REF] De Gooijer | 25 years of time series forecasting[END_REF][START_REF] Voyant | Multi-horizon solar radiation forecasting for Mediterranean locations using time series models[END_REF].

MLP

In the presented study, the MLPs have been computed with the Matlab© software and its Neural Network toolbox. The characteristics chosen related to previous works are the following: one hidden layer, the activation functions are the continuously and differentiable hyperbolic tangent (hidden) and linear (output), the Levenberg-Marquardt (approximation to the Newton's method) learning algorithm with a maximum fail parameter before stopping training equal to 3. The optimization of the number of input nodes is done with the partial autocorrelation factor, which measures the degree of association between two measures, with the effect of a set of controlling intermediate measures removed. Concerning the four types of TS considered, this number varies between 4 and 9 lags. The number of hidden neurons is taken equal to the input nodes number. The results shown in the following parts are related to the best network among six different trainings coupled with a random weight initialization [START_REF] Behrang | The potential of different artificial neural network (ANN) techniques in daily global solar radiation modeling based on meteorological data[END_REF][START_REF] De Gooijer | 25 years of time series forecasting[END_REF][START_REF] Kalogirou | Artificial neural networks in renewable energy systems applications: A review[END_REF]. Concerning the MLP with heterogeneous transfer functions, the characteristics are described in the section 2.1.

MLP with a time index input

The last approach consists in adding a time index input to the two MLP previously proposed, that is to say, the classical one and the MLP with the heterogeneous transfer function. An input is added and is related to the time concerning the hour of prediction. This node takes the values i/24 (for i=1 to 24) for each hour of the day [START_REF] Voyant | Multi-horizon solar radiation forecasting for Mediterranean locations using time series models[END_REF].

Results

-3 -2 -1 0 1 2 3 -1 -0.5 0 0.5 1 1.5 2 u f(u) increasing 
The first series of results (Table 1) is related to the persistence (P), normal MLP (noted N-MLP) and the heterogeneous transfer functions MLP (noted HTF-MLP; 50% of tanh' transfer function in the hidden layer). The error metric used is the nRMSE (RMSE/mean). Concerning the use of the MLP, the results presented in the following tables are related to the runs (among six) minimizing the nRMSE. In bold the lowest nRMSE.

In Table 1, we see that HTF-MLP is not really efficient, it gives the best results only for only one TS (Wind speed) tied with N-MLP. With a MLP, one way to improve the results is often to make the time series stationary and to operate a preprocessing before to choose the inputs nodes. In our case, there are four kinds of data, so we chose to apply a seasonal adjustment by periodic coefficients (computed from moving average during the learning phase). In the following results, when this prepost processing is used, the suffix -s is added (example N-MLP-s). The Table 2 shows the impact of this processing on the nRMSE value. The stationary process doesn't improve systematically the nRMSE, in fact, in the solar radiation case the error is increased by more than 2 percentage point. The second tool that should improve results is the time index taken as input of the networks. In the following parts, we will note -t (example N-MLP-s-t) when this index is used. The Table 3 shows the impact of this exogenous data (multivariate analysis). Considering the different configurations -s, -t, non-bijective or bijective transfer functions of hidden nodes, a lot of combinations are possible. The next table [START_REF] De Gooijer | 25 years of time series forecasting[END_REF] summarizes for each data the predictor with the lowest nRMSE and the related error metric.

1 Fig. 2 :

 12 Fig.2: Output of the classic (blue) and the heterogeneous transfer functions MLP (dotted curve) relating to the u parameter (linear combination of inputs) and the asymmetry rate and In black, the output concerning 

  Table. 1: nRMSE related to the persistence, normal MLP and heterogeneous transfer functions MLP.

		P	N-MLP	HTF-MLP
	Humidity	0.070	0.073	0.073
	Solar irradiation	0.319	0.305	0.308
	Temperature	0.058	0.067	0.067
	Wind speed	0.394	0.359	0.359

Table . 2

 . : nRMSE related to the normal MLP and heterogeneous transfer functions MLP and concerning the time series made stationary. In bold the lowest nRMSE.

		N-MLP-s	HTF-MLP-s
	Humidity	0.070	0.070
	Solar irradiation	0.333	0.334
	Temperature	0.059	0.059
	Wind speed	0.351	0.350

  Table. 3: nRMSE related to the normal MLP and heterogeneous transfer functions MLP and concerning the time index taken as input. In bold the lowest nRMSE.

		N-MLP-t	HTF-MLP-t	N-MLP-s-t	HTF-MLP-s-t
	Humidity	0.069	0.070	0.071	0.070
	Solar radiation	0.292	0.298	0.324	0.331
	Temperature	0.058	0.060	0.059	0.057
	Wind speed	0.358	0.357	0.351	0.353

*the hidden node with the (tanh) ' The time index and the (tanh)' transfer function are the tools giving the best results 75% of the cases). The stationary process does not define really the best approaches. For the two time series with the lowest VC the nRMSE is under 10% whereas for the other series (solar irradiation and wind speed) the nRMSE is close to 30%.

Conclusion

In this study, a MLP coupling two transfer functions, a time index and a stationary process was studied. If the interest of the time index taken as inputs of the network is proved in this study, future studies expanding the nature or the location related to time series will be necessary to show the interest of the MLP with heterogeneous transfer functions. As conclusion of this paper, for each case concerning the time series forecasting of meteorological data, the possibility to use a time index, a stationary process and an inhibition transfer functions should be considered.