Philippe Gambette

Andreas D M Gunawan

Anthony Labarre

Stéphane Vialette

Louxin Zhang

Locating a Tree in a Phylogenetic Network in Quadratic Time

A fundamental problem in the study of phylogenetic networks is to determine whether or not a given phylogenetic network contains a given phylogenetic tree. We develop a quadratic-time algorithm for this problem for binary nearly-stable phylogenetic networks. We also show that the number of reticulations in a reticulation visible or nearly stable phylogenetic network is bounded from above by a function linear in the number of taxa.

Introduction

Genetic material can be transferred between organisms by hybridization, recombination and horizontal gene transfer besides traditional reproduction. Recent studies in comparative genomics suggest that these "lateral" processes are a driving force in evolution which shapes the genome of a species [START_REF] Chan | Topology of viral evolution[END_REF][START_REF] Mcbreen | Reconstructing reticulate evolutionary histories of plants[END_REF][START_REF] Treangen | Horizontal transfer, not duplication, drives the expansion of protein families in prokaryotes[END_REF]. Accordingly, phylogenetic networks have commonly been used to model reticulate evolutionary histories of species [START_REF] Chan | Topology of viral evolution[END_REF][START_REF] Dagan | Modular networks and cumulative impact of lateral transfer in prokaryote genome evolution[END_REF][START_REF] Marcussen | Inferring species networks from gene trees in high-polyploid north american and hawaiian violets (viola, violaceae)[END_REF]. A plethora of methods for reconstructing reticulate evolutionary histories of species and related algorithmic issues have extensively been studied over the past two decades [START_REF] Gusfield | ReCombinatorics: The Algorithmics of Ancestral Recombination Graphs and Explicit Phylogenetic Networks[END_REF][START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF][START_REF] Moret | Phylogenetic networks: Modeling, reconstructibility, and accuracy[END_REF][START_REF] Nakhleh | Computational approaches to species phylogeny inference and gene tree reconciliation[END_REF][START_REF] Parida | Ancestral recombinations graph: a reconstructability perspective using random-graphs framework[END_REF][START_REF] Wang | Perfect phylogenetic networks with recombination[END_REF].

A phylogenetic network is an acyclic digraph with a set X of labeled leaves (that is, vertices of outdegree zero) and a root (having indegree zero). The leaves are in one-to-one correspondence with a collection of taxa under study, whereas the unique root represents their least common ancestor. Vertices with indegree one represent speciation events. Vertices of indegree at least two represent an evolutionary process by which genetic material was horizontally transferred from one species to another.

A fundamental question in the study of phylogenetic networks is to determine whether a tree is displayed by a phylogenetic network over the same set of taxa (in a sense we define precisely below). This problem is called the tree containment problem [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF]. Answering this question is indeed useful to validate and justify a phylogenetic network model by testing whether it displays existing phylogenies over a set of taxa under study.

The problem is NP-complete in general [START_REF] Kanj | Seeing the trees and their branches in the network is hard[END_REF], even on the more restricted class of tree-sibling time-consistent regular networks [START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF]. Although great effort has been devoted to the study of that problem, it has been shown to be polynomial-time solvable only for a couple of interesting classes of phylogenetic networks, namely, normal networks and tree-child networks [START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF]. Determining the complexity of the tree containment problem for a class of phylogenetic networks that properly contains tree-child networks, particularly those with the so-called reticulationvisibility property, is an open problem [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF][START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF].

In this paper, we study the tree containment problem for nearly stable phylogenetic networks (defined in the next section), which generalize normal and tree-child networks. Recombination histories of viruses, hybridization histories of plants, and histories of horizontal gene transfers reported in literature often satisfy the property that defines those networks [START_REF] Jenkins | Genealogy-based methods for inference of historical recombination and gene flow and their application in saccharomyces cerevisiae[END_REF][START_REF] Marcussen | Inferring species networks from gene trees in high-polyploid north american and hawaiian violets (viola, violaceae)[END_REF]. Our key results include: (i) the number of reticulations in a reticulation-visible or nearly stable phylogenetic network is linearly bounded from above in terms of the number of taxa; and (ii) the tree containment problem for nearly stable phylogenetic networks can be solved in quadratic time. Omitted proofs and details will appear in the extended version.

Concepts and Notions

A (phylogenetic) network on a set X of taxa is a directed acyclic graph with a single root (a vertex with indegree 0) which satisfies the following properties: (i) its leaves (vertices with outdegree 0) are in one-to-one correspondence with the taxa in X; (ii) there are no vertices with both indegree one and outdegree one; and (iii) there is a path from the root to any other vertex. We identify each leaf with the taxon corresponding to it and refer to the directed edges (tail, head) as branches.

In a network, reticulation vertices (or simply reticulations) are vertices with indegree at least two and outdegree one; tree vertices are vertices with indegree one and outdegree at least two. A branch is a tree branch if it ends at a tree vertex; it is called a reticulation branch otherwise.

A network is binary if its root, leaves and the other vertices have degree 2, 1 and 3, respectively. A phylogenetic tree is simply a binary network without reticulations.

For a binary network N , we shall use r N to denote the root of N . Let x and y be vertices in N . We say that x is a parent of y and y is a child of x if (x, y) is a branch. More generally, we say that x is an ancestor of y and equivalently y is a descendant of x if there is a directed path from x to y. A vertex x in N is a stable ancestor of a vertex v if it belongs to all directed paths from r N to v. We say that x is stable if there exists a leaf ℓ such that x is a stable ancestor of ℓ.

Proposition 1.

Let N be a binary network. The following facts hold.

(1) A vertex is stable if it has a stable tree child.

(2) A reticulation is stable if and only if its unique child is a stable tree vertex.

(3) If a tree vertex is stable, then its children cannot both be reticulations.

A network is a tree-child network if every vertex has a child that is a tree vertex [START_REF] Cardona | Comparison of tree-child phylogenetic networks[END_REF]. It can be proved that a network is a tree-child network if and only if every vertex is stable. It is reticulation-visible if all its reticulations are stable [START_REF] Huson | Phylogenetic Networks: Concepts, Algorithms and Applications[END_REF]. It is nearly stable if for every vertex, either that vertex is stable or its parents are.

Contracting a branch (u, v) means replacing it with a single vertex w in such a way that all neighbors of u and v become neighbors of w. Given a binary phylogenetic tree T and a binary network N , we say that N displays T if there is a spanning subtree T ′ of N that is a subdivision of T , i.e. T ′ has the same vertex set as N and T can be obtained from T ′ by contracting all branches in T ′ incident with the vertices with outdegree 1 and indegree 1, all branches incident with the "dummy leaves" (leaves in T ′ that correspond to tree vertices in N ), and all branches incident with a vertex of indegree 0 and outdegree 1. Figure 1 shows an example of a phylogenetic network N and a tree that is displayed in N . In this work, we study the tree containment problem (TCP), which is that of determining whether a phylogenetic tree is displayed by a network or not.

How Many Reticulations in a Network?

An arbitrary network with n leaves can have a very large number of reticulations. To analyze the time complexity of an algorithm designed for solving a network problem, we need to bound the size of the network by a function of n.

Removing a reticulation branch from each reticulation in a binary network N yields a spanning subtree T ′ . All leaves in N are still leaves in T ′ , but T ′ may additionally contain some "dummy leaves" that correspond to tree vertices whose outgoing branches have both been removed. The following lemma says that it is always possible to remove proper reticulation branches so as to obtain a tree without dummy leaves.

Lemma 1.

Let N be a binary reticulation-visible phylogenetic network. We can determine which reticulation branch to remove at each reticulation so that the tree obtained after removing the selected branches contains no dummy leaves.

Proof. Let T be a tree obtained from N by removing exactly one reticulation branch incident to each reticulation. In order for T not to contain any dummy leaves, we need to guarantee that the reticulation branches to be removed are incident with different tree vertices. In other words, the branches to be removed form a matching that covers every reticulation in N . Since N has the reticulationvisibility property, the parents of each reticulation are both tree vertices (Proposition 1). Such a set of reticulation branches exists and can be found by applying Hall's Theorem to a bipartite graph with tree vertices and reticulations as vertex sets and reticulation branches as edges. Since each reticulation is the head of two reticulation branches and each tree vertex is the tail of at most two reticulation branches, there exists a matching that covers all the reticulations (see a result of N. Alon on page 429 in [START_REF] Bondy | Graph Theory[END_REF]).

⊓ ⊔

A cross branch removed A non-cross branch removed

A cross branch removed

A B C D y x y x y t 1 r 1 t 2
x z Fig. 2. Illustration of the different cases in the proof of Theorem 1. A. Definition of cross and non-cross branches removed from a path. B. The branch (x, y) is a non-cross branch removed from a path. Assume that a cross branch (z ′ , z) has been removed from a reticulation z inside the segment from x and y, where z ′ is not shown, and two cross branches have also been removed from two tree vertices t1 and t2 between z and y. C. Some cross branches must have been removed from their tails located between the heads of two non-cross branches that are removed from a path (in this case, between y and y ′ ). D. If two cross branches have been removed from two reticulations in a path, then the upper reticulation (rj here) is not stable.

Theorem 1.

Let N be a binary reticulation-visible phylogenetic network with n leaves. Then N has at most 4(n -1) reticulations.

Proof. Assume N contains m reticulations. By Lemma 1, we can obtain a tree T without dummy leaves by removing m reticulation branches from N . Since N is binary, an internal vertex in T has either one or two children; equivalently, T is a subdivision of a rooted binary tree T ′ over the same leaves as N . Therefore, T ′ has n -1 internal vertices (including its root) of outdegree 2 and there are 2n -2 paths P i (1 ≤ i ≤ 2n -2) satisfying (i) the ends of each P i are either the root of T , a leaf, or internal vertices of outdegree 2, and (ii) each internal vertex of P i has both indegree and outdegree 1 if P i consists of two or more branches.

For each path P i of length ≥ 2, an internal vertex of P i is either a tree vertex of N , whose outgoing branch not in P i has been removed, or a reticulation, whose incoming branch not in P i has been removed. For convenience of discussion, we divide the removed reticulation branches into cross and non-cross branches (with respect to T ) (Figure 2A). A removed branch is called a cross branch if its tail and head are located on two different paths P i and P j , i ̸ = j, otherwise it's called a non-cross branch. We first have the following facts.

Facts

(1) If (x, y) is a non-cross branch removed from P i , then at least one cross branch has been removed from its tree vertex tail in the segment P i [x, y] from x to y of P i , and there is no reticulation in P i [x, y] other than y.

(2) Let (x, y) and (x ′ , y ′ ) be two non-cross branches removed from P i , where y is an ancestor of y ′ . Then there exists at least one cross branch being removed from its tree vertex tail located between y and y ′ (Figure 2C). ( 3) There are at least as many cross reticulation branches removed as noncross reticulation branches.

Proof. (1) Since N contains no parallel branches, P i [x, y] has at least three vertices, so it suffices to prove that y is the only reticulation in

P i [x, y].
Assume on the contrary that a branch (z ′ , z) has been removed from a reticulation z in P i [x, y] (Figure 2B). Then there is a path including (x, y) from r N to a leaf below y that avoids z, so z is not stable on any leaf below y (and hence below z) in T (and hence in N ). Moreover, since T is a subtree of N , z cannot be stable in N on any leaf that is not below z in T . N and T have the same leaf set, hence z is not stable in N , contradicting the reticulation-visibility property.

(2) Note that y and y ′ are reticulations in N . By Fact (1) above, y must be above x ′ , and there is a cross brach removed from its tree vertex tail located between x ′ and y ′ .

(3) By Facts (1) and (2), we can establish an injective map from the set of non-cross reticulation branches to that of cross ones. Hence, the statement in this part is also true.

⊓ ⊔

Assume at least 2n -1 cross branches (t i , r i ) have been removed from the 2n -2 paths P i . At least two heads r j and r k are on the same path P i (Figure 2D). Using an argument similar to that used in the proof of Fact (2), one of r j and r k which is upstream in P i is not stable, a contradiction. Therefore, at most 2n -2 cross branches have been removed to produce T . By Fact (3), there are also at most 2n -2 non-cross branches removed during the process. Since we removed one incoming branch for each reticulation, we conclude that there are at most Assume on the contrary that d is unstable. Then both its children must be stable by the nearly-stable property of N . Hence, by Proposition 1(2) and the fact that d is unstable, both its children are stable reticulations. Since a is unstable, a is not a child of d. This implies that c is unstable, a contradiction.

Finally, let e be the parent of c. f be the other parent of a and g be the other parent of b (see Figure 3). Note that g ̸ = f . Otherwise, f is unstable, contradicting that there are no two consecutive unstable vertices. To transform N into a binary reticulation-visible network, we remove unstable vertex a by first removing the branch (c, a), and then contracting the paths f -a-b and e-c-d into branches (f, b) and (e, d). Both b and d are clearly still stable in the resulting network. By rewiring around every unstable reticulation in N , we produce a binary reticulation-visible network N ′ . The inequality follows from the fact that no stable reticulation is removed, and no new reticulation is created during the rewiring.

⊓ ⊔ Proof. Directly follows from the fact that an unstable reticulation must have a stable reticulation as its child, and any stable reticulation can be the child of at most two unstable reticulations. Proof. (i) Theorem 1 and Lemmas 2 and 3 imply S ret (N )+U ret (N ) ≤ 3S ret (N ) ≤ 3S ret (N ′ ) ≤ 3(4n -4) = 12(n -1).

(ii) We can think of the network as a flow network, with r N as source and the n leaves as sinks. Hence, the number of tree vertices equals n -1 plus the number of reticulations, that is, at most 13(n -1) (by (i)). Since the outdegree of the root is two, and the outdegrees of each tree and reticulation vertex are 2 and 1, respectively, N has 2(13n -13) + 12(n -1) = 38(n -1) branches at most. ⊓ ⊔

A Quadratic-Time Algorithm for the TCP

In this section, we shall present a quadratic-time algorithm for solving the TCP. If a given network N and a given reference tree T contain a common subphylogeny, then we can simplify the task of determining whether N displays T by replacing the common subphylogeny by a new leaf. Therefore, without loss of generality, we assume that N does not contain a subphylogeny with two or more leaves. We call this property the subphylogeny-free property.

Lemma 4.

Let N be a nearly stable phylogenetic network satisfying the subphylogenyfree property. Let P = (r, . . . , w, u, v, ℓ) be a longest root-to-leaf path of four or more vertices in N , where r = r N and ℓ the leaf end. Then the subnetwork consisting of the descendants of w exhibits one of the structures given in Figure 4.

Proof. Note that v cannot be a tree vertex: since P is a longest root-to-leaf path, the other child of v would otherwise be a leaf, thereby contradicting our assumption that N satisfies the subphylogeny-free property. Therefore, v is a reticulation. There are two possible cases for u.

1. The u is a reticulation: Then u is unstable, and w must be a stable tree vertex (see Proposition 1(2) for both claims), which is stable on ℓ or some other leaf. Let g be the other child of w. By Proposition 1(3), g is either a tree vertex or a leaf. If g is a leaf, we obtain the subnetwork in Figure 4A.

If g is a tree vertex, then neither of its children is a tree vertex: since P is a longest path, a tree vertex child of g would have two leaves as children, thereby contradicting the subphylogeny-free property. Note that g's children cannot both be reticulations either, since otherwise w would be unstable. Therefore, one child of g is a leaf and the other is a reticulation with a leaf child (again because P is a longest path), as shown in Figure 4B. 2. The u is a tree vertex: Let e denote the other child of u. Note that e cannot be a tree vertex, otherwise both its children would be leaves (since P is a longest path), which would contradict our assumption that N has the subphylogeny-free property. If e is a leaf, we obtain the subnetwork shown in Figure 4C. If e is a reticulation, then its only child is a leaf (again because P is a longest path), so e is stable on that leaf and u is therefore unstable.

Since N is nearly stable, w must be a stable tree vertex. We consider the other child g of w in the following subcases.

(2.1) If g is a leaf, then we have the subnetwork given in Figure 4D.

(2.2) If g is a tree vertex and also a parent of e and v, then we obtain the subnetwork in Figure 4E. (2.3) If g is a tree vertex and in addition, g is a parent of e, but not a parent of v: then w is stable on ℓ ′ , the unique child of e. Let h be the other child of g; then h cannot be a tree vertex, since both its children would then be leaves, which would contradict our assumption that N has the subphylogeny-free property. If h is a reticulation, its child must be a leaf, since P is a longest path. Thus, we have the subnetwork given in Figure 4F. If h is a leaf, we obtain the subnetwork in Figure 4G. (2.4) If g is a tree vertex and in addition, g is a parent of v, but not a parent of e, then a discussion similar to that of case (2.2) characterises the only two possible subnetworks (Figure 4H and4I) in this case. (2.5) If g is a tree vertex and in addition, g is neither a parent of v nor a parent of e: then again we look at g's children. Both cannot be reticulations, otherwise w is unstable, a contradiction. If neither of them is a reticulation, then there is a subtree below g; if one of them is a reticulation and the other is a tree vertex, then again there is a subtree. The only possible case that remains, shown in Figure 4J, is the case where one child is a reticulation and the other is a leaf.

(2.6) If g is a reticulation: Then w unstable. This is impossible, as w is a stable tree vertex.

⊓ ⊔

The subnetwork below g of the structures shown in Figure 4B, 4G, 4I, 4J and that below u in Figure 4C match the following pattern: y in which a leaf ℓ has a reticulation sibling y and a leaf nephew, ℓ ′ . Such a pattern is called an uncle-nephew structure. Note that if ℓ and ℓ ′ are not siblings in a tree displayed by N , then the reticulation branch (x, y) should not be used. If ℓ and ℓ ′ are siblings, either (x, y) or the other branch entering y can be used. Here, since the other branch enters y from an unspecified vertex, it is simply called a dangling branch. It is not hard to see that for a tree T in which ℓ and ℓ ′ are siblings, if T is displayed in the network resulting from the removal of (x, y), it is also displayed in the one after the dangling branch is removed. Hence, to determine whether N displays a tree T , we can simplify the network by eliminating y using the following process:

Uncle-Nephew Reduction In an uncle-nephew substructure shown above, remove the dangling branch if ℓ and ℓ ′ are siblings in T , or remove (x, y) otherwise. Then contract vertices with indegree and outdegree 1.

In each of the other cases, we can also simplify the network by using information on the input tree. To summarize how to simplify the network, we use the following notation for each vertex w in a network N :

-R(w) denotes the subnetwork consisting of all the descendants of w; -(-, x) denotes the dangling branch entering x from its parent not in R(w) for x in R(w); -N ′ + (x, y) denotes the subnetwork obtained by adding (x, y) into N ′ for a subnetwork N ′ of N and a branch (x, y) of N ; -N ′ -(x, y) denotes the subnetwork obtained by removing (x, y) from N ′ for a subnetwork N ′ of N ; p T (x) denotes the parent of a vertex x in a tree T . Theorem 3. Let N be a binary nearly stable network with no uncle-nephew structure, and T a tree with the same set of labeled leaves. Let w be a tree vertex in N . Define N ′ as follows. Then N ′ is nearly stable and N displays T only if N ′ displays T .

Proof. Since none of the simplifications removes any leaf and all of them only reduce possible paths from r N to a leaf, the resulting network N ′ is nearly stable. Assume R(w) is the subnetwork in Figure 4A and N displays T . Then there exists a subtree T ′ of N that is a subdivision of T and let p T (ℓ) corresponds x in T ′ . Clearly, x is of degree 3 and hence a tree vertex in N . We consider two cases.

CASE A. Leaves ℓ and ℓ ′ are not siblings in T . We first have that x ̸ = u, x ̸ = v for u and v in Figure 4A. We also have x ̸ = w. Otherwise, ℓ ′ must be a child of x in T ′ and ℓ is a sibling of ℓ ′ in T , a contradiction. Therefore, the path from x to ℓ contains two or more vertices and v is the parent of ℓ in this path. If u is the parent of v in the same path, neither (

-, v) nor (w, u) is in T ′ , indicating that N ′ = N -(w, u) also displays T . If p T ′ (v) ̸ = u in the same path, then (u, v)
is not in T ′ and hence u becomes a dummy leaf in T ′ , as there is no leaf other than ℓ below u in R(w). If (w, u) is in T ′ , then (-, u) is not in T ′ and T ′ + (-, u) -(w, u) is a subtree of N ′ in which only the dummy leaf u is relocated. Hence, N ′ also displays T . CASE B. Leaves ℓ and ℓ ′ are siblings in T . Then x is a common ancestor of ℓ and ℓ ′ in N . If x = w, the path from x to ℓ in T ′ must be w, u, v, as this is only path from w to ℓ in N . Hence, (-, u) and (-, v) are not in T ′ . Therefore, T ′ is a subtree of N ′ and N ′ also displays T .

If x ̸ = w, then x is an ancestor of w and hence w is the parent of ℓ ′ in the path from

x to ℓ ′ in T ′ . Note that p T ′ (ℓ) = v. If p T ′ (v) = u, then (-, u) is in T ′ , but both (-, v) and (w, u) are not. T ′′ = T ′ + (w, u) -(-, u) is a subtree of N ′ . Noting that T ′′ is also a subdivision of T , N ′ displays T . If p T ′ (v) ̸ = u, then (-, v) is in the path from x to ℓ in T ′ . This implies that (u, v) is not in T ′ and u is a dead-end in T ′ . If (w, u) is in T ′ , the subtree T ′′ = T ′ + (u, v) -(-, v) of N ′ is a subdivision of T . If (w, u) is not in T ′ , the subtree T ′′ = T ′ + (w, u) -(-, u) -(-, v) of N ′ is a subtree of N ′ . Hence, N ′ displays T ′ .
Similarly, we can prove that N displays T only if N ′ displays T when R(w) is the subnetwork in the panels D, F, and H in Figure 4. Note also that the subnetworks in the panels F and H are essentially identical (if the positions of v and e are switched). Due to the limited space, the details are omitted here. The case when R(w) is the subnetwork in Figure 4E is trivial, as deletion of which two reticulation branches from v and e does not affect outcome.

⊓ ⊔

By Theorem 3, we are able to determine whether a nearly stable phylogenetic network N displays a binary tree T or not by repeatedly executing the following tasks in turn until the resulting network N ′ becomes a tree:

-Compute a longest path P in N ′ = N ; -Simplify N ′ by considering the subnetwork at the end of P according to the cases in Lemma 4; -Contract degenerated reticulations in N ′ and replace the parent of a pair of leaves appearing in both N ′ and T with a new leaf.

and then check if N ′ is identical to T . Finally, we analyze the time complexity. Let N and T have n leaves. By Theorem 2, there are O(n) vertices and O(n) branches in N . Since we eliminate at least a reticulation in each loop step, the algorithm stops after O(n) loop steps. In each loop step, a longest path can be computed in O(n) time ( [START_REF] Sedgewick | Algorithms, 4th Edition[END_REF], page 661), as N is acyclic; both the second and third tasks can be done in constant time. In summary, our algorithm has quadratic time complexity.

Conclusion

We have developed a quadratic-time algorithm for the TCP for binary nearly stable phylogenetic networks. Our algorithm not only is applicable to a superclass of tree-child networks, but also has a lower time complexity than the algorithm reported in [START_REF] Van Iersel | Locating a tree in a phylogenetic network[END_REF]. Although phylogenetic network models built in the study of viral and plant evolution are often nearly stable, it is interesting to know whether the TCP is polynomial time solvable or not for networks with other weak properties.

In particular, the problem remains open for binary networks with the visibility property, but the upper bound we have presented on the number of reticulation vertices of such networks, as well as our algorithm for nearly stable phylogenetic networks, provide definitely valuable ideas to solve the problem, exactly or heuristically, on phylogenetic networks with the reticulation visibility property.

Fig. 1 .

 1 Fig. 1. (A) A phylogenetic network. (B) A spanning subtree of N obtained after the reticulation branch between the parents of c and b is removed. (C) A tree displayed in N through the subtree in (B).

Fig. 3 .Lemma 3 .

 33 Fig.3. A An unstable reticulation a, its stable child b and its stable parents (c and f ) in the original network N . To transform N into a reticulation-visible network, we remove the incoming reticulation branch (c, a) (B) and then contract paths e-c-d and f -a-b (C). The rewiring eliminates the unstable reticulation vertex a.

⊓ ⊔ Theorem 2 .

 2 Let N be a binary nearly stable network with n leaves. Let T (N ) denotes the number of tree vertices in N . Then: (i) N has at most 12(n -1) reticulations; (ii) |T (N )| ≤ 13(n -1) and |E(N )| ≤ 38(n -1).

Fig. 4 .

 4 Fig.4. All ten possible subnetworks at the end of a longest path in a nearly stable network. Here, r is the network root and the directed path from r to w is represented by a coiled path. The parent w of u is not shown in C.

( i )

 i When R(w) matches the structure of Figure 4A, define N ′ = N -(w, u) if ℓ and ℓ ′ are not sibling in T and N ′ = N -{(-, u), (-, v)} otherwise. (ii) When R(w) matches the structure of Figure 4D, define N ′ = N -(-, v) when ℓ and ℓ ′′ are siblings, or when ℓ and ℓ ′ are siblings and their parent is a sibling of ℓ ′′ in T , and N ′ = N -(u, v) otherwise. (iii) When R(w) matches the structure of Figure 4E, define N ′ = N -{(u, e), (g, v)}. (iv) When R(w) matches the structure of Figure 4F, define N ′ = N -{(g, e), (-, v)} if ℓ and ℓ ′ are siblings in T and N ′ = N -(u, e) otherwise. (v) When R(w) matches the structure of Figure 4H, define N ′ = N -{(g, v), (-, e)} if ℓ and ℓ ′ are siblings in T and N ′ = N -(u, v) otherwise.

  Let N be a binary nearly stable network, and let U ret (N ) (resp. S ret (N )) denote the number of all unstable (resp. stable) reticulations in N . We can transform N into a binary reticulation-visible network N ′ with the property that N ′ has the same leaf set as N and S ret (N ) ≤ S ret (N ′ ) ≤ S ret (N )+U ret (N ).Proof. Let a be an unstable reticulation in N , whose child is denoted by b. Since N is nearly stable, b is stable. By Proposition 1(2), b is a stable reticulation. Let c denote a parent of a; then c is stable by definition of N , and it is a tree vertex by Proposition 1[START_REF] Cardona | Comparison of tree-child phylogenetic networks[END_REF]. Let d denote the other child of c. Since c is stable, d is a tree vertex (Proposition 1(3)). In addition, d is stable.

	4(n -1) reticulations in N .	⊓ ⊔
	Lemma 2.

Acknowledgments

The project was financially supported by Merlion Programme 2013.


Thierry Pairault

Mulugeta Gebrehiwot Berhe

China's economic presence in Algeria

Keywords: China, Algeria, FDI, Investment, Trade, Economic Relations, Riveneuve éditions, 2014, p. 63-82 [, Defraigne, J.-C. and Wouters, J., EU-China

archive ouverte pluridisciplinaire HAL, est destinée au dépôt

China's economic presence in Algeria

3

China's economic presence in Algeria S ocialist Algeria has always maintained friendly relations with Maoist China, but paradoxically, it was only during the 1990s and the 2000s, when Algeria abandoned its offi cial ties to socialism, that the two countries began experiencing an unprecedented expansion in their economic, commercial and human relations. Twelve years ago, China's share in Algeria's foreign trade was insignifi cant. In 2013, China became Algeria's number one supplier with 6.82 thousand million dollars worth of imports, thus overtaking France (6.25 thousand million dollars), which had long held fi rst position. The European Union, however, still ranks as top trading partner for both imports and exports (Douanes, 2013:17). Excitement surrounded the Algerian media's announcement of this event, which was portrayed as a competition between the former colonial power and the new global economic giant. France, whose dominant position in Algerian imports had been steadily reinforced ever since the opening of trade in the early 1990s, was now superseded by China. This breakthrough in imports might well be the most obvious expression of China's increasing presence. However, it is rather diffi cult to assess the exact importance of this presence as there is much fantasising about it. From the moment the country became more visible, Western observers began to study China's strategy in Algeria with increasing attention, as it introduced a renewed questioning going beyond the nagging issue of a rentier country's failure to industrialise, diversify and create jobs. This contribution will examine the sudden acceleration of Sino-Algerian economic relations and the resulting changes in the relationship between Algeria and the world. China's presence in Algeria combines many interrelated features, which are not only distinctive, but contain their own logic and temporality: these encompass political, diplomatic, cultural, migratory, human and economic relations. This paper will mainly focus on the last category; it will draw on statistical data recorded by international agencies, as well as data collected by national statistical agencies in Algeria and China. It will thus seek to improve our understanding of what is meant by "China's economic presence in Algeria".

FACTS AND FIGURES ABOUT CHINA'S INVESTMENT IN ALGERIA

To assess the economic role that China plays in Algeria, we must examine the importance of both countries' commercial exchanges, as well as the weight of Chinese direct investment in the Algerian economy. In this paper we will fi rst deal with the investment approach, as "foreign direct investment" (FDI) strongly implies an entrepreneurial commitment to the medium and/or long term in the economy of a country. According to the defi nition proffered by international authorities such as the OECD, FDI "…is an activity in which an investor resident in one country obtains a lasting interest in, and a signifi cant infl uence on the management of, an entity resident in another country. This may involve either creating an entirely new enterprise (a so-called «greenfi eld» investment) or, more typically, changing the ownership of existing enterprises (via mergers and acquisitions)." (OECD, 2003:157, box VI-I).

In 2012, the Chinese FDI fl ow in (Northern and sub-Saharan) African countries amounted to about 2.9 per cent of the total Chinese outward FDI fl ow and 0.18 per cent of the worldwide global outward FDI fl ow 1 . Looking at Algeria alone, these fi gures are less than 0.3 per cent and 0.02 per cent, respectively. The low level of the last two global fi gures should be viewed in terms of a longterm African perspective: China's FDI stock in Algeria accounted for 6.0 per cent of the total Chinese FDI stock in Africa in 2012. Among those African countries which have benefi ted from the Chinese FDI, Algeria ranks fourth, behind South Africa (fi rst), Zambia (second) and Nigeria (third). These four countries cumulate about half of China's FDI stock in Africa. This fact highlights Algeria's economic interest for China and may indicate a Chinese entrepreneurial and fi nancial long-term strategy. Nevertheless, it cannot be assumed that Chinese FDI is actually impacting on the Algerian economy. To gage a possible infl uence, Chinese FDI fl ows must be measured using the yardstick of the Algerian gross fi xed capital formation (GFCF), which is an indicator of net investment in a given country2 . As FDI infl ows can fl uctuate greatly Th., 2013:261-265). A more minute statistical account appears in our study of Sino-Algerian relations (Pairault Th., 2014:33-62)..

4

from one year to another, it is necessary to consider its average value over a given period in order to better ascertain its actual proportion. On average, from 2003 to 2011, Algeria relied little on FDI to fi nance its GFCF (10.2 per cent as compared to the world average, 21.9 per cent), with a Chinese contribution (0.6 per cent) identical to the Chinese average for the world, but half the Chinese average for African countries (1.2 per cent). Hence, Chinese investment indicates China's interest in Algeria, but is of marginal economic relevance for the latter and must be seen as part of a more general Chinese concern in investing abroad: oil supplies (cf. fi gure 1).

The recent period has been marked by a clear commitment to reviving the oil sector by relying heavily on the expertise of foreign companies. In the process, China has received a certain degree of attention, which should, however, be considered in context 3 . Adding up areas prospected by foreign oil companies in association with the national oil company Sonatrach, the two Chinese companies (CNPC and SINOPEC) respectively rank fourth and sixth; it does not appear that they are particularly advantaged nor disadvantaged relatively to others major oil companies selected by Algeria. Areas conceded to U. S. companies account for one third of the total whilst those granted to Chinese ones account for less than a quarter. In other words, there has been a preference for China without it does call into question the pre-eminence of Western companies that handle more than three quarters of the prospected areas. Preference for China is also played down by direct investment fl ows as recorded by Algerian statistical services. Between 2000 and 2008, China accounted for 4 per cent of FDI entering Algeria and invested in the energy and mining sector. Thus, China certainly maintained an active presence, but much less so than Algeria's main partners, such as the United Kingdom, the United States and Spain, which represent more than half (57 per cent) of FDI in this sector (Fachqoul K. and Th. Pairault, 2014:79-81).

China's presence in the oil and gas sector clearly refl ects the Algerian government's will to open up to an old and faithful ally, whose growing economy offered great hopes of an expanding market for what was expected to be exceptional oil production, but which in fact proved to be disappointing. China was also undoubtedly a partner whose technical skills needed to be tested; this is probably why China was not put in charge of the most technically complex projects or the most expensive ones. There is little to say about Algeria's exports, for they consist mainly of crude oil and petroleum products. On average, from 2003 to 2012, they accounted for 98.3 per cent of the value of Algeria's total exports and 99.2 per cent of the value of its exports to China. Seen From this perspective, it is obvious that exports are not Chinese specifi c. The structure of Algerian imports of Chinese merchandise does not differ very signifi cantly from that of all African countries: during the period 2003-2012, on average, about 91 per cent of these imports were machinery and transportation equipment5 (51 per cent) and miscellaneous manufactured goods6 (40 per cent). Once chemicals products7

FACTS AND FIGURES ABOUT SINO-ALGERIAN

(5 per cent) were added, the proportion of all manufactured goods came to a total of 96 per cent.

For Africa as a whole, these fi gures were 88 per cent, (44 per cent and 44 per cent) and 7 per cent respectively, making a total of 95 per cent.

Different patterns may appear if Algeria's imports are examined in terms of the contributions of different categories of countries: this provides a comparison between China and other developing -and developed -countries (cf. fi gure 2). The forty-seven countries with a "very high human development" index according to the UNDP (2013:144) are considered to be "developed countries", while the other countries are categorised as "developing countries" -this last category being divided into "China" and "other developing countries". In 2012, Algerian imports from "developed countries" accounted for two-thirds (65 per cent) of the total imports of goods, whereas it was three-quarters (73 per cent) of the total in 2003. Even if exports from "developed countries" to Algeria are still increasing, the proportional loss in market shares is China's gain (12 per cent), and China's gain alone, as "other developing countries" have not experienced any increase. The three groups of countries play very different roles, because the main goods they supply are not of the same kind. Imports from "other developing countries" are made up of 51 per cent primary commodities 8 (food items: 40.5 per cent; fuel: 10.5 per cent). Imports from China are almost exclusively made up of manufactured goods 9 products including chemical products (96.2 per cent). Imports from "developed countries" show a comparatively more even distribution, as they are made up of 26.2 per cent primary products and 70.2 per cent manufactured goods.

There are three groups of goods that deserve a more detailed analysis, as they are economically and socially sensitive: Clothing 10 (including The entry of smuggled goods is not recordable, but their impact a fortiori can only be diminishing. Importation of telecommunication equipment is an Actually, the real competition may be between the "developed countries" themselves, not between these countries and China. The lists of telecommunication equipment approved by the Algerian Post and Telecommunications Regulatory Authority 13 do not show a marked preference for Chinese brands, but rather for Chinese-made products such as those sold under brand names like Alcatel, Ericsson and Nokia, for example. The Value-Added Export Ratio (i.e. the total domestic value added to the share of gross exports) in this sector reached only 57.4 per cent for China, whereas it stands at 87.9 per cent for the United States, 87.5 per cent for Japan and 70.4 per cent for France 14 .

Algeria granted China a large share of its imports of road vehicles, to the extent that, in 2009, it became the fi rst market abroad for Chinese vehicles, according to the Chinese Ministry of Commerce (MOFCOM, 2011). Despite its present success and impressive progress, China has not yet dethroned the automakers from "developed countries". In 2012, China won about 16 per cent of the market share of imported cars, but the "developed countries" still held almost two-thirds (65 per cent). Here again, France is the biggest loser in market shares, even if it is still able to keep pace with the Chinese, who are in fi rst position.

In the near future, competition between car makers will not be restricted to imported vehicles, so may shift to locally manufactured cars. In this situation, the French automakers may have somewhat of an advantage (see infra).

CHINA'S ECONOMIC PRESENCE

Sino-Algerian economic relations refl ect the overall dynamics of the Chinese economic expansion in Africa. China has entered the African market thanks to its ability to meet the urgent needs of these countries and, to some extent, because of its capacity to contribute to GDP growth. (1994)(1995)(1996)(1997)(1998) that Algeria had to endure when oil prices were low and when the "struggle against terrorism" was dictating expenditure priorities and budget allocations. Once the legislation on foreign investment was liberalised, under the constraint of structural adjustment programs, Chinese contractors became very competitive, won numerous public tenders easily and took away the best part of the loot. Thus, China may have secured 80 per cent of recent infrastructure contracts in Algeria (Castel V. et al., 2011:5). Algerian contractors, mainly small and medium enterprises, cannot compete de facto with the large Chinese public groups (Souiah F., 2011:8). Thus, Chinese contractors have managed to get a step ahead by positioning themselves on the Algerian construction market at a time when Western contractors were fl eeing the insecurity and the poor business climate.

The current Minister of Housing, Abdelmadjid Tebboune, seems to somehow regret past choices and now urges French contractors to respond to tenders. He adds that "the timeliness and quality required in the completion of our housing projects require us to explore new solutions." (Lamriben H., 2014).

The entry of Chinese expertise and investment into Algeria does not automatically fall within the authorities' sphere of decision. It may also occur via Western fi rms, without being checked by the Algerian decision-makers and sometimes even against their will, as in the case of Terramin Australia and Desertec (Talahite F., 2014:20-21). Formally, the disagreement between Terramin and Algerian authorities is said to have focused on technical issues, but in fact, it is the involvement of a Chinese partner that has been the bone of contention.

HUMAN ECONOMIC PRESENCE

The (Michel S., 2007).

The decrease in the number of Chinese workers is expected to continue with the completion of major contracts (Hammou S. and Th. Pairault, 2014:166-168;Pina-Guerassimoff C., 2014:237-241). It was relatively easy for foreigners to settle down in the early 2000s, but later, administrative constraints (visas, work permits) become tighter -even for the Chinese, who fully felt their effects (Dridi D., 2011).

According to Tayeb Louh, then Minister of Labour, "[for major national projects], we resorted to foreign workers with work visas not exceeding three months and temporary work permits issued by the employment bureaux knowing that foreign workers must return to their home country upon the expiration of his work visa.» (Bouklia-Hassane R. and F. Talahite, 2010:127-129). Thus, in the 2000s, tens of thousands of Chinese workers arrived in Algeria, but only a few hundred of them could have permanently settled in the country -at least legally. This infl ux of Chinese migrants in Algeria could therefore only have been an interlude and not a groundswell, as some have supposed. This idea was widely publicised in Algeria and abroad, sometimes to the point of feeding the fear of a Chinese "invasion". However the only outstanding feature of this infl ux was its novelty in a country where there were very few foreigners, including Westerners, as a result of a long period of insecurity in the wake of the 1992 coup d'état. China's presence here thus remains marginal when compared to Lubumbashi (DRC), which is "overwhelmed by […] an exhibition of Chinese symbols" (Tshibambe G., 2013:257) or to South Africa, where the Chinese "community" has been formed by numerous waves of Chinese migrants, the fi rst one dating back to the 18th century (Pina-Guerassimoff C., 2014:238).

In the 2000s, the Algerian government had to face two pressing issues: housing and unemploymentboth causes of endemic social unrest. To tackle them, it adopted two distinct approaches: on the one hand, it relied on foreign companies to speed up housing construction; on the other, it promoted what in France is called "a social response to unemployment" (Bouklia-Hassane R. and F. Talahite, 2008:423-430). This policy nourished criticism against Chinese enterprises, which were accused of increasing unemployment by importing their own workforce. Bound by their tender specifi cations, Chinese companies had no choice but to import their own labour force in order to meet a commitment to maintain such low costs and short deadlines. The presence of large Chinese labour forces on construction sites was not at fi rst contested. Later, however, this was often seen as a refusal to provide employment for Algeriansalthough few Algerians would have agreed to work at wages and under working conditions such as those offered by Chinese enterprises to their own workers. The African Development Bank noted the Chinese enterprises' low propensity for providing work that could absorb youth unemployment, especially that of graduates (Alden C. and F. Aggad-Clerx, 2012:14). This social discontent might explain why the brawls that broke out between Algerians and Chinese during the summer of 2009 in Algiers' suburbs were interpreted as the anger and hostility of the young unemployed towards Chinese workers (Hammou S. and Th. Pairault, 2014:165) The Algerian government did impose a quota of 20 per cent Algerian workers in Chinese construction projects. It is not clear whether this measure applied to all construction sites and, when it did, to what extent it was actually implemented (Dzaka-Kikouta Th. et al., 2014:208;Kpetigo D., 2014:147-148;Provenzano L., 2009). It is diffi cult to fi ght unemployment and at the same time to engage in the construction of housing. This should be kept in mind when interpreting the contract signed with Beijing Liujian Construction Corp (BLCC), a Chinese public company under the direction of Beijing municipality. BLCC was founded in 1958 and was authorised to recruit manual labour, skilled workers and executives to supply various construction sites abroad. BLCC was chosen to build 4,000 dwellings in Saïda. The agreement signed with the employment services provided that BLCC must recruit 3,724 local workers; in return it was allowed to hire 1,197 Chinese workers to ensure proper supervision. The agreement also stipulated that BLCC was required to promote training operations for young recruits in the various specialised sectors of building and construction. When the agreement was signed, work had already been in progress for almost one year. One year after its signature by both parties, BLCC was employing just 300 local workers, i.e. about 8 per cent of the fi gure originally put forward (Ahmed S., 2013(Ahmed S., & 2014)).

Even if it is possible that there might be a refl ux, the presence of Chinese migrants and expatriates in Algeria is probably not a cyclical phenomenon, but rather fi ts into a basic trend in Africa that should gain momentum with ever closer Sino-African economic relations.

AN OUTSTANDING RELATIONSHIP

When compared to other Sino-African relationships, Sino-Algerian relations show certain distinctive features. Two of them are particularly noteworthy: fi rst, the fact that infrastructure investment is selffi nanced and second, the purchase of military hi-tech equipment. Algeria does not seek package deals (i.e. an agreement including loans, aid and services) in The Algerian government challenged this strategy in 2005 when it became aware that higher oil prices made it possible to fi nance infrastructure investments with its foreign exchange reserves and, thus, to proceed by request for tender. The announcement of this procedural change seems to have been sorely received by CITIC which was originally to play the role of a mere construction manager, hiring the CRCC services. In the rehashed version of the project, the Algerian authorities asked the tender winners to act as project manager and thereby to assume responsibility for the project design. The panic seems to have been real: the Chinese consortium tried unsuccessfully to retrieve the studies conducted previously by Western consulting and engineering fi rms. What "rescued" the Chinese consortium was the low priority the Algerian government accorded to the quality of the work and, conversely, the high priority it accorded to the speed of its completion (fast-track EPC project). Consequently, the project design did not necessarily need to be completed before answering the call for tender, but as and when needed. The consortium thus had time to conduct engineering studies. Furthermore, the Algerian government, consistent with its policy of prioritising speed, even at the expense of quality, no longer required, in its fi nal version of the specifi cations, that bidders should have experience of completing a certain number of linear kilometres of motorway in countries demanding class A standards, such as European countries or the USA. The removal of this constraint meant that the Chinese consortium would not be excluded from the competition and, to some extent, that the previous promise would be respected. On the 16th of April 2006, the Chinese consortium won only two of the three sections of the motorway (the West and Centre sections); the third section (the East section) was won by COJAAL, a Japanese consortium (He Y., 2011;El Kadi I., 2009;CACI, 2006). The experience of the CITIC-CRCC consortium in Algeria merits a few remarks. The completion of the motorway's two sections in relatively good time certainly could have given a very favourable impression if it had not been for the poor quality of the work and the suspicions of corruption. We will not discuss the later issue here, as both partners (both the supply and demand sides of corruption) may be in the wrong. Furthermore, corruption on construction projects is a worldwide problem, which is not specifi c to China (Kpetigo D., 2014:146) 21 .

Promoting the employment of nationals is not easy, as it is neither a mere matter of strengthening legislation, nor a problem of stricter enforcement of quotas. It is, indeed, the entire structure of the policy that must be re-examined, because calling on Chinese workers -in conditions that they are used to -is a sine qua non for low cost completion.

Organising technology transfer, for the same purpose, is not an easy operation either. China has already experienced these problems when confronted with Western fi rms. Setting up vocational training centres funded by foreign fi rms may, wrongly, seem like a good idea: this type of solution cannot be reproduced indefi nitely -even assuming the teachers needed are available. Cooperation is probably a more promising path: here, the question is a matter of politics rather than of economic policy. Algeria has obviously made an effort to diversify its suppliers in the sphere of defence and China appears to be one of the main benefi ciaries of this policy (Zanardi C., 2014:93-94

SOMMAIRE

Avant-propos Introduction

Fatiha

1

  Unless otherwise stated, all statistical fi gures displayed in this paper are based on the author's calculations from the United Nations Conference on trade and development (UNCTAD) on-line database (UNCTADStat at unctadstat.unctad.org) and MOFCOM (i.e. the Chinese Ministry of Commerce) annual communiqués, Duiwai zhijie touzi tongji gongbao 对外直接投资统计公报 [Statistical Communiqué of China's Outward Foreign Direct Investment] (Pairault

  footwear), Telecommunication equipment 11 and Road Vehicles 12 . In 2012, clothing import statistics showed the opposite situation to that recorded in 2003, when the "developed countries" had 42 per cent of market shares and China had 30 per cent: in 2012 the fi gures were 29 and 43 per cent respectively. On the other hand, "other developing countries" did not undergo any changes. This underlying trend should not conceal two facts: fi rst, the clothing industry in China is partly the result of the delocalisation of Western enterprises, and, second, the clothing industry's share in the total value of Algerian imports is extremely low (2.1 per cent). Hence, China's share accounts for 0.9 per cent of the total value of Algerian imports. Throughout the 1980s in Algeria, well before the liberalisation of foreign trade and while local consumer goods were in short supply, of poor quality and limited variety, "suitcase traders" started ferrying contraband, fi rst from Europe, then from Asia, to meet the needs generated by rising incomes and the emergence of a middle class. In 2009, Ben Simpfendorfer described the liveliness of the "New Silk Road" stretching from Chinese market towns to Cairo, Damascus, Riyadh and Dubai. Because of the policy of economic openness, the impact of indirect imports going through such commercial hubs may now be more limited (textile imports from Egypt, Syria, Saudi Arabia and the United Arab Emirates amounted to 10.3 per cent of textile imports from China in 2012).

6

  equally sensitive issue, particularly as the Chinese telecom giant Huawei has recently been at the centre of legal proceedings in Algeria(Mira R. and F. Talahite, 2014:138-139). Obviously, the "developed countries" have lost their monopoly in supplying telecom equipment, but still remain the leading suppliers. As the fl ow of imports by country varies considerably from year to year, depending on the signing of contracts and the completion of projects, the average fi gures for the period 2003-2012 provide the best illustration of the respective position of the competitors: imports from China account for 28 per cent, whereas those from "developed countries" stand at 70 per cent on average. If looking at individual countries, France is certainly the biggest loser: it ranked fi rst in 2003, with a quarter of all Algerian imports of telecom equipment; in 2012 not only did its market share fall to less than two per cent, but the value of its sales dropped to one-tenth of its 2003 value. Conversely, the United States, which sold less than China in the early 2000s, gained an identical market share of about one third in 2012.

  fi rst wave of Chinese migrants reached Algiers in the late 1990s. Some arrived as migrant workers, hired in China by Chinese enterprises engaged in the construction market in Algeria. Their contract once completed, some of them stayed in Algeria, where they opened small businesses. At the end of 2011, the total number of Chinese nationals on Algerian soil may have reached about 40 to 45,000 individuals, including migrant workers (the manual workforce recruited for a specifi c job), "expatriates" (managerial staff sent out on temporary assignments by their companies), petty entrepreneurs, shopkeepers and their families. Between 2005 and 2011, Algeria was the African country with the largest number of Chinese migrant workers, peaking at 49,631 in 2009, then falling to 36,562 in 2011, a decrease of 8,646 between 2010 and 2011, mainly due to the migrant workers' massive return home after the completion of the projects (cf. fi gure 4). The construction of the West and Centre sections of the East-West Motorway, which is now completed, may alone have mobilised about twenty-two thousand Chinese workers

10

  exchange for granting Chinese enterprises access to strategic resources -i.e. the infrastructures for resources strategy, often epitomised as the "Angolan model" of bartering(Corkin L., 2013). There is no detailed account of the whole process involved in awarding the East-West motorway contract; nevertheless, what we do know demonstrates the transformation in Algeria's stance on the fi nancing of such infrastructure investment. The Algerian government was fi rst approached in 2003 by CITIC, a major public investment company under the direct supervision of the Chinese government. In 2004, both parties seem to have agreed to assess the costs of the infrastructure at 10.8 million dollars 19 on the basis of studies conducted from the year 2000 on by Western consulting and engineering fi rms, at the request of the Algerian authorities. Under this agreement, the construction of the East-West motorway's three sections was assigned to a Chinese contractor designated by CITIC, who would be in charge of fi nancing the project. Moreover, it was understood that the Chinese consortium -made up of the fi nancier (CITIC) and the contractor (CRCC 20 )would be paid in oil deliveries.

  : UNE RELATION SINGULIÈRE EN AFRIQUEL'Algérie socialiste entretenait déjà des relations amicales avec la Chine maoïste, mais c'est paradoxalement dans les années 1990 et 2000, alors que l'Algérie abandonnait la référence offi cielle au socialisme, que les échanges entre les deux pays connaissent une expansion sans précédent, aux plans économique, commercial, humain..., tellement rapide qu'elle a pu alimenter des fantasmes sur la présence et les visées chinoises en Algérie. C'est cette accélération brutale de l'histoire des relations entre les deux pays qui est interrogée dans cet ouvrage. D'abord pour tenter d'en évaluer l'ampleur et les contours, puis, dans une perspective comparative, pour relativiser le phénomène au regard de ce qui se passe sur le continent africain, en distinguant les aspects contingents de cette présence de ceux qui s'inscrivent dans la longue durée, les traits singuliers de ceux que l'on retrouve ailleurs en Afrique. friendly relations with Maoist China; it is paradoxically during the 1990s and the 2000s, while Algeria abandoned the offi cial reference to socialism, that economic, commercial and human relations between the two countries began experiencing an unprecedented expansion in such a way that it could feed fantasies about the Chinese presence and expectations in Algeria. This book examines the sudden acceleration of the relations between the two countries. It aims fi rst at assessing the extent and outlines of these relations, then at putting this phenomenon into perspective relatively to what is taking place on the African continent; it therefore distinguishes casual aspects of this presence from those which may last more permanently, singular features from those which are more commonly met in Africa.

  following: -0.358, -0.249 and -0.180). There is often speculation that China is making the most of the withdrawal of Western companies from Africa in order to promote projects that they have abandoned because of low returns (inter aliaHugon Ph., 2009:164-165). For instance, according to Mathieu Pellerin, this may have been the case in the oil sector in Niger(Pellerin M., 2012). The facts may prove to be more complicated. A recent audit by Ernst and Young found the China National Petroleum Corporation (CNPC) guilty of bloated costs and undue charges. In 2008, CNPC concluded an agreement with the former president, Mamadou Tandja, to lend money to Niger in order to launch operations at an oil fi eld near Diffa and to build a refi nery at Zinder. The audit revealed that the Chinese fi nancial package was infl ated by hundreds of millions of dollars, interest rates were set very high (market rates over ten years) and, fi nally, there was a kickback scheme involving 300 million dollars. The new Niger government renegotiated the contract, but did not obtain complete satisfaction. In neighbouring Chad, the government has been more cursory, shutting down the Chinese operation and accusing the CNPC of "blatant disregard of environmental legal standards".In Gabon, the Obangue oil fi eld, operated by SINOPEC since 2009, was seized and handed over to Gabon's state company.(Boisbouvier C., 2013a(Boisbouvier C., et 2013b;;[START_REF] Adam | China Finds Resistance to Oil Deals in Africa[END_REF]. Thus, things are not as simple as they seem at fi rst sight.

	On the other hand, in December 2013, the French
	pharmaceutical leader Sanofi , whose Algerian
	market has long accounted for about 25 per cent of
	its turnover in Africa, undertook the construction of a
	plant in Sidi Abdellah which is to become the largest
	Sanofi unit in Africa (Smati S., 2013). Therefore,
	speculation about the supposed withdrawal of
	Western companies and their alleged unwillingness
	to invest should be weighed alongside the capacities,
	as well as the (alleged or proven) behaviour, of
	Chinese fi rms and, last but not least, the industrial
	and political choices of the African partner countries
	-in our case, Algeria.
	In the 2000s, Algeria frequently appealed to
	Chinese contractors to implement the Programme of
	Support for Economic Revival (2001-2004) and the
	follow-up Economic Growth Support Programme
	(2005-2009) which were fi nanced by soaring oil
	Another example may be useful in evaluating
	all the speculation about the withdrawal of
	Western companies. Ever since 2006, FAW (First Automotive Works -one of the main Chinese central enterprises -has been soliciting the Algerian government for an agreement to install an assembly line, but high tariff 16 and land policies 17 make direct imports of fi nished products no more expensive than local assembly. So it comes as no surprise that the presence of Chinese automakers is linked mainly to imports of Chinese vehicles and that their investments are limited to the opening of sales representative offi ces. That is also true of the Shaanxi Automobile Group (a publicly funded enterprise under the supervision of the Shaanxi province government), which had planned to set up an assembly unit in Sétif, scheduled to be operative in 2010, but in the end only opened a sales representative offi ce in 2011. Similarly Higer and JMC, too, only opened offi ces (Pairault Th., 2014:50-52). On the other hand, the French car maker Renault, which was said to be reluctant to invest in Algeria, fi nally accepted, in	On the 8th of October 2011, in Algiers, the Algerian Minister of Health, Djamel Ould Abbès, organised a lavish ceremony to entertain la crème de la crème of Western pharmaceutical industries and announced a "mega-project" for the manufacture of drugs at the technopole located in the new city of Sidi Abdellah, near Algiers (Merabet H., 2011). A few days later, Djamel Ould Abbès reported that foreign direct investment in the pharmaceutical sector amounted to 420 million dollars in 2011 -of which 320 million from European companies and 100 million from Indian, Egyptian, Jordanian, Turkish and Saudi companies (Ould Abbès D., 2011). A few days after that, Algeria and China agreed to set up a joint committee for the technical study of this "mega-project", the purpose of which was to enable Algeria to eventually become «a hub for the Middle East and North Africa» in medicine, according to a statement by the Algerian Minister of Health, Djamel Ould Abbès (Haider K., 2011). Subsequently, the
		press never again mentioned any such prospective
		Sino-Algerian partnership.

Meanwhile, China is looking for suppliers of raw materials (crude oil, mining products…). In Algeria, consumer goods imported from China have become an indispensable part of everyday life and have led to consumer patterns which would not otherwise have developed. These goods are not actually in competition with local production, which is virtually non-existent, since private capital is still essentially invested in merchant activities and fl ourishes especially in the wholesale consumer goods trade. Therefore, Chinese small businessmen do not really threaten the retail industry in Algeria, no more than Syrian, Tunisian, Egyptian, Moroccan, Turkish and other foreign petty traders do

(Hammou S. and Th. Pairault, 2014:163)

. Even if the available capital is invested in the manufacturing sector, lowend necessities imported from China are the key to keeping the cost of labour relatively low. Trade relations between Algeria and China are not really in competition with those involving the traditional partners either

(Pairault Th., 2014:55-56)

. Generally speaking, developed economies and China are not in direct competition in their trade relations with Algeria: according to the merchandise trade correlation index, as calculated by UNCTAD 15 , the Euro area countries should have better opportunities in Algeria than other developed countries and even better ones than China (the indexes are, respectively, 15 "Trade correlation index is a simple correlation coeffi cient between economy A and economy B's trade specialization index. The resulting coeffi cient can take a value from -1 to +1. A positive value indicates that the economies are competitors in global market since both countries are net exporters of the same set of products. Consequently, a negative value suggests that the economies do not specialize in the production/consumption of the same goods, and are therefore natural trading partners". See the statistical data provided online by UNCTADStat at unctadstat.unctad.org. the 16 Custom duties on imported auto parts to be assembled are very high. An exemption of such duties could be why Renault recently (December 2012) accepted to invest in Algeria. 17 Access to industrial land is a major impediment to investment in Algeria. There is no shortage of land but there are poor land policies and ineffi cient institutions together with frenzied rent seeking competition. As a consequence, investors are discouraged by land price, opaque transactions, time-consuming procedures and extra-legal payments. 2012, the proposal to create a new production unit at Oued Tlélat near Oran (Chaal M., 2012). In that particular case, the Algerian government voiced a political choice (rappro¬chement between Algiers and Paris) as well as an obvious industrial preference (veteran carmaker versus newcomers).The revealed comparative advantage (RCA) index, based on gross exports of motor vehicles and transport equipment, shows that France has a clear comparative advantage whereas China has a signifi cant comparative disadvantage in that sector: this index is 1.7 for France, but 0.3 for China (1.6 and 1.9 respectively for Germany and Japan) 18 . Nevertheless, a year later, in December 2013, the Chinese automaker FAW was fi nally able to sign an agreement for a partnership with Arcofi na, a private Algerian group that is already marketing its vehicles (Kerri N., 2013). Sometimes, the announcement of investment projects involving Chinese companies acts as a signal to Western companies and vice-versa 18 The revealed comparative advantage (RCA for short) is measured by OECD (stats.oecd.org). When the RCA exceeds one, the country is said to have a revealed comparative advantage in that sector; when the RCA is below one, the country is said to have a revealed comparative disadvantage in that sector. CHINE, CORÉE, JAPON UMR8173 -190-198 avenue de France -75013 Paris -France http://umr-ccj.ehess.fr 8 revenues. The goal was to make up for the time lost during the 1990s, i.e. during the "black decade" marked by the Structural Adjustment Programme

  , now that one of its shareholders is Dongfeng Motor (DFM) -one of the "Big Three" Chinese public automakers? It is worth pointing out that DFM has entered into joint ventures in China with Citroën, Honda, Kia, Nissan, Peugeot and Renault. This automaker may consider Algeria to be a bridgehead for securing its commercial expansion in Africa(Zhu G., 2014).

The arrival of the State Grid Corporation of China as a shareholder of Desertec was not Algiers' choice for its energy policy; however, the Algerian authorities had no alternative but to accept it. And what about Peugeot's investment plan in Algeria

  ). Military purchases from China have several advantages: they should reduce the Algerian military dependence on Russia and make it possible to buy less expensive but modern equipment. As a result, competition in the sector of high-tech military equipment is no longer limited to Russian and Western companies and opens up possibilities for negotiation with military equipment suppliers for technology transfer Algerian policy-makers try to operate on two fronts. On the one hand, they tend to limit China's presence to areas where there is no competition with their traditional partners, such as the construction sector. On the other hand, they are tempted to take advantage of China's economic and technological performance to boost Algeria's economic growth by engaging in Sino-Algerian joint projects. "China has expressed a strong will to enhance multilevel cooperation with Africa. That is in accordance with Algeria's development strategy" claimed Abdelkader Bensalah, president of the Council of the Nation of Algeria during the Bo'ao Forum in 2013(Li X., 2013).

The gross fi xed capital formation, during a given period, measures the value of net additions to fi xed assets (less disposals) but without deducting the depreciation of fi xed assets. It is not a measure but a statistical "indicator" of (net) investment.

The statistical data given here are extracted from balance sheets published by the Algerian Ministry of Energy and Mines, http://www. mem-algeria.org/francais/index.php?page=bilan-des-realisations-2

All statistical fi gures displayed in this section are based on author's calculations from UNCTAD on-line database.

Classifi cation: STIC 7.

Classifi cation: STIC 6 + 8 less 667 and 68.

Classifi cation: STIC 5.

Classifi cation: STIC 764.

Classifi cation: STIC 78 (including motor vehicles for the transport of persons and goods, motorcycles and cycles…).

This fi gure has to be compared with that resulting from the call for tenders which two years later reached 11.2 million dollars.

The China Railway Construction Corporation (CRCC) is the second largest contractor in China; founded in 1948, it is a public enterprise under the direct supervision of the Chinese government.

The 2014 Arachnys Open Data Compass reveals that "intrusive, bureaucratic and authoritarian states often perform quite well in providing open, business-critical data," with China (20th) and Russia (23th) outranking United States (26th) when it comes to corporate transparency but performing worse than New Zealand, United Kingdom, Australia, France and Germany (to list orderly the top 5). See compass.arachnys.com/static /download/Arachnys-Open-Data-Compass-2014.pdf.

L'