The k-Center problem on a graph is to nd a set K of k vertices minimizing the radius de ned as the maximum distance between any vertex and K. We propose a probabilistic combinatorial optimization model for this problem, with uncertainty on vertices. This model is inspired by a wild re management problem. The graph represents the adjacency of zones of a landscape, where each vertex represents a zone. We consider a nite set of re scenarios with related probabilities. Given a k-center, its radius may change in some scenarios since some evacuation paths become impracticable. The objective is to nd a robust k-center that minimizes the expected value of the radius over all scenarios. We study this new problem with scenarios limited to a single burning vertex. First results deal with explicit solutions on paths and cycles, and hardness on planar graphs.
then can spread on all neighboring nodes at a xed maximum distance called the range of impact. The impacted zone is then the set of vertices where the re spreads. In a real case scenario, the re can spread over very large areas and the impacted zone grows dynamically. However, it might be relevant to focus on a relatively short period after ignition or after the alert, seen as the time required for all people present in the area to reach an assembly point. This motivates us to consider small ranges of impact depending on the e ciency of the early warning system. We then assume that people are safe after reaching the assembly point; this hypothesis is relevant depending on the exact nature and design of the assembly points.
Our problem is a particular case of location-allocation problems. A solution describes not only the location of emergency assembly points, de ned as a subset K V; jKj = k and known as a k-center (location problem), but it also includes a strategy people should follow in case of re to reach one assembly point (evacuation process). The location can be addressed during the preparedness phase and may involve sophisticated solutions. The allocation however is mainly addressed during the response phase, which usually requires e cient and simple processes. Indeed, even though evacuation scenarios can be prepared in advance, they should remain straightforward in order to be followed by untrained people, without supervision and under high stress conditions. Here, we will consider that somebody is assigned to the closest assembly point with the constraint he/she will never go through the re; this constraint will be precise later. For a real case implementation, this could be supported by simple early warning system deployed on site and indicating the direction and distance of the closest accessible shelter(s). The objective is then to minimize the maximum distance from each vertex v to K, called the radius of the kcenter K. It corresponds to the worst case situation for someone present in the risk zone when a re starts. However high uncertainty lies on where a re ignites and thus on the accessibility of some vertices or on the practicability of some paths during the event. We model it as di erent possible scenarios, where a scenario is given by an ignition vertex and a range of impact. Then, the objective becomes the expected value of the radius in the new instance. We will restrict ourselves to a simple re outbreak scenarios. This hypothesis is supported by our choice to focus on a relative short period after ignition. To simplify the problem in this rst study we will consider a xed range of impact. This corresponds to the situation where the considered region is homogeneous in terms of topography, wind and fuel load conditions.
The framework of Probabilistic combinatorial optimization [3{5], also known as a priori optimization, is particularly suitable to model such situations, where one has to deal with destructions or obstructions on a usual set-up that make an original global strategy potentially unfeasible. In this approach, a problem is decomposed in two phases. The whole instance is considered during the rst phase (seen as the preparedness phase), while in a second time (response phase) only a part of the infrastructure remains available after an uncertain event has occurred. A modi cation strategy is identi ed beforehand to "automatically" transform a solution on the whole instance (called an a priori solution) to a feasible solution on a partial available instance (an a posteriori solution). To represent uncertainty, probabilities are assigned to the di erent possible partial instances. More precisely it is usually based on a probability distribution on the di erent components of the initial instance representing how likely they could be a ected. The objective is then to compute an a priori solution on the whole instance optimizing the expected value of the e ective solution induced on the partial instance using the modi cation scheme. Given our allocation strategy that assigns a person at risk to the closest safety point, the modi cation scheme describes the new set of emergency points after the event and the new possible routes so as to recompute the new allocation and the corresponding objective value. In this paper, since we assume the emergency gathering points or shelters are safe and since it is not possible to de ne new locations during the response phase, we consider that the k-center is not modi ed. Indeed, any original k-center always remains feasible in the new graph. The modi cation scheme only corresponds to the new possible routes; roughly speaking these routes are paths that do not cross the impacted zone. Speci c rules are considered for people in this impacted zone as detailed in the next section.
In the usual non-probabilistic case, also called deterministic case, our problem is known as the Minimum kCenter problem and to our knowledge this is the rst time the Probabilistic k-center is de ned and discussed [6]. However, restricted versions of routing and networking-design probabilistic minimization problems (in complete graphs) have been studied (see, e.g., [7{11] ). In [12{15], the analysis of the probabilistic minimum traveling salesman problem, originally presented in [3, 4], has been revisited in order to propose new e cient resolution. Several other combinatorial problems have been also handled in the probabilistic combinatorial optimization approach, with or without recourse, including minimum vertex cover and maximum independent set [16, 17], longest path [18], Steiner tree problems [19, 20], minimum spanning tree [9, 21], minimum dominating set [22] and some other general combinatorial graph problems [23].
In this paper we apply the probabilistic combinatorial optimization setting for the k-center problem and we use the following notations. Let G = (V; E) be an undirected and connected graph with V = f0; : : : ; ng. For v 2 V , N (v) is the set of its neighbors. A path of length m is a sequence v0; : : : ; vm of pairwise distinct vertices where 8i 2 f0; : : : ; m 1g; vivi+1 2 E. For x; y 2 V , we denote by (x; y) the distance between x and y (that is the length of the shortest path between them). Similarly for a set K V , (x; K) = min (x; y). Given a y2K k-center K V; jKj = k, its radius in G is denoted by rK = max (v; K). Finally, given a real-valued function v2V f with domain A, we denote arg min f (x) the set fx 2 A : f (x) = min f (y)g of the minimum(s) of f in A.
x2A y2A
The paper is organized as follows. In Section 2, we introduce and de ne the problem, namely Probabilistic k-Center. In Section 3, we give and prove an explicit optimal solution on path and cycle instances. Section 4 deals with hardness of approximation on planar graphs of degrees 2 or 3. Finally, we conclude in Section 5. 2
Probabilistic k-Center is characterized by a couple (S; M), where S is the set of scenarios in each instance, and M is a modi cation strategy. In this paper we study scenarios where the re is limited to a simple node. Then S = fsi : i 2 V g with si the scenario where vertex i burns. With the considered modi cation strategy M0, the location of the centers are conserved and the vertices are a ected to the nearest center in the available instance. This strategy involves the following: when a re ignites, all the people in the forest try to escape to the closest shelter to get evacuated by the rescue. If there is a shelter in the ignition area, we assume that people in this area nd refuge in that shelter. Otherwise the people in the ignition zone always ee in the opposite direction of the re. Once at su cient distance, they can choose their path rationally in order to get to the closest shelter.
An instance of our problem is then a couple (G;P) with G a graph and P a probability system associated with the vertices. It gives, for each vertex, the probability of re on it. By default, we will consider a uniform distribution under the assumption that we have one re outbreak at a time on a simple node. So, each scenario has probability p = jV1 j . So in this work, Probabilistic k-Center will refer to this set-up. For scenario sj and for any x; y 2 V , we denote by j (x; y) the distance between x and y in G n fjg. Note that j (x; x) = 0 and j (x; y) = +1 if there is no path between x and y. Then, for scenario sj and K V , the induced evacuation distance of a node x is given by:
Dj (x; K) = ( j (x; K)
if (x 6= j) or if (x = j and j 2 K)
xm2Na(xj)f1 + ym2iKn j (x; y)g if x = j and j 62 K
(
x2V
We illustrate these de nitions for k = 3 on a path of nine vertices and the 3-center K = f0; 5; 8g, whose nodes are drawn as pentagons. Figure 1, gives, for each node x, the value of (x; K). So, the radius of this solution is 2. In Figure 2, we illustrate a re occurring on node 1. We give under each node x 2 V the value of D1(x; K), and underline it when it has changed. For example, node 2 is a ected since the original evacuation path to shelter 0 is no more operational. Note that, in the worst case, people on node 1 escape to node 2 and then to shelter 5. The disrupted radius r1K of scenario 1 is 4.
An optimal solution for our version of the Probabilistic k-Center problem is then a k-center K 2 arg minK2KfE(K)g.
We introduce the following decomposition of the objective function:
E(K) = Es(K) + Es(K) s.t. : Es(K) = p P rjK ; Es(K) = p j2K
P j2GnK rjK
In other words, Es(K) is the contribution of scenarios for which res occur in K (called the skeleton), and Es(K) is the contribution of scenarios for which res occur on the other vertices (called the body). We can treat these components as two di erent problems. In particular, Es(K) corresponds to a version of our problem where the nodes of K are forti ed [24], which means they are immune to re. Note that, if a solution is optimal for both components, then it is optimal for the whole problem.
Moreover, we propose another evaluation function, denoted E, corresponding to the expected evacuation b distance in the local area of the ignition node j de ned as the close neighborhood (N (j) [ fjg) of j. The locally induced radius is then denoted rbjK = x2Nm(ja)x[fjg Dj (x; K) :
Eb(K) = p X rbjK j2V Eb(K) E(K)
3
Denote Pn+1 a path on n + 1 vertices, Cn a cycle on n vertices, and H a graph that is either a path or cycle with n edges. Given the feasibility condition seen in Remark 1, for K = (v1; : : : ; vk) 2 K(Pn+1), we necessarily have v1 = 0 and vk = n. Thus, K induces k 1 segments i of length i, i = 1; : : : ; k 1. On a cycle Cn and for K 2 K(Cn), K would induces k segments. In the following we deal with path and cycles simultaneously, unless speci ed otherwise. We de ne = k if H is a cycle, and = k 1 if H is a path. We denote EH (K) the value of the solution K in H. Denoting = ( 1; : : : ; ), we can consider equivalently EH (K), EsH (K) and EsH (K) as functions of (K). We say that = ( 1; : : : ; ) is not decreasing if 1 : : : . We de ne = ( i1 ; : : : ; i ), where i : f1; : : : ; g ! f1; : : : ; g is a permutation such that i1 : : : i , a non decreasing solution induced by . The possible s corresponding to a feasible k-center are all vectors, ( 1; : : : ; ) 2 N such that Pi=1 i = n. We denote by (H) their set. The aim of this section is to give an explicit optimal solution for Probabilistic kCenter on paths and cycles. In both cases, the balanced solution (see De nition 1), optimal in the deterministic case, reveals also to be optimal in the probabilistic case. However, the proof is non-trivial. For paths, we will show, in a rst step, that this solution minimizes the contribution of the skeleton and in a second step, that it minimizes also the contribution of the body. We then derive the case on cycle by a reduction to the case on paths. 3.1
The results in this subsection hold for both cycles and paths with n edges. We de ne 0 = +1 = ; in the case
of paths. We recall that the objective function of the Probabilistic k-Center problem requires the disrupted
verifying
(
rjK = maxfmx2axifDj(x; K)g; x2mHanx ifDj(x; K)gg we obtain: Observe that, 8x 2 H n i, the evacuation path is not modi ed. On q 62 i, the evacuation path of any node is shorter than the evacuation path of the middle node(s) of q. Then, 8x 2 q; Dj(x; K) b 2q c and max fDj(x; K)g = max fb 2q cg. Now we look at maxfDj(x; K)g. The evacuation paths on segment x2Hn i q2f1;:::; g: q62 i x2 i
i is always shorter than one of the evacuation paths from j or - if j 2 K - from one of his neighbor. We distinguish then two cases:
If j 2 K, max fDj(x; K)g = maxfDj(j 1; K); Dj(j + 1; K); g since Dj(j; K) = 0. Based on Equation (
If j 62 K, maxfDj(x; K)g = Dj(j; K). Using Equation (
We denote by B the related vector of distances. Thus, we have iB 2 f n ; n g and 1B : : : B for i = 1; : : : ; . In what follows, we show that the Probabilistic k-Center problem has an optimal balanced solution on paths and cycles. For k n2 , we have the following result (the proof is given in Appendix):
n , KB is an optimum solution for Probabilistic k-Center on paths and cycles.
2
So, in what follows, we assume k < n2 . In this case, we show in Appendix the Lemma 1 : Lemma 1. EsH ( B) = EbsH ( B) , EsH ( B) = EbsH ( B) and EH ( B) = EbH ( B).
In subsection 3.2, we show that KB minimizes EsPn+1 (K). In order to prove that KB minimizes also EsPn+1 (K), in subsection 3.3, we establish a more general result, by showing that KB minimizes EsH (K). So, we can obtain Theorem 1 for paths and in subsection 3.4, we consider cycles. 3.2
In this subsection, we focus on the skeleton part on paths. We rst show that some balanced solution minimizes
EbsPn+1 (K) and then, that it minimizes as well EsPn+1 (K). Based on Equations (
EbsPn+1 ( )
Proof. Consider = ( 1; : : : ) with i 0; i = 1; : : : ; . If 1 = maxf i; i = 1; : : : g, we de ne r = 0, else
let r be the maximum index in f1; : : : ; g such that 1 : : : r and 8j r; j r. If r = , we have
= and nothing needs to be shown. Else, r < 1 (the value r = 1 is not possible), we consider
s 2 arg minf j; j = r + 1; : : : ; g: by de nition, we have r+1 r if r > 0, s > r + 1 and r s < r+1. We
then consider 0 the vector obtained from by moving the sth coordinate at the position r + 1:
0 =
i
0 =
i
i; i = 1; : : : ; r
i 1; i = r + 2; : : : ; s
0r+1
0
i
=
=
s;
i; i > s
We claim that EbsPn+1 ( 0) EbsPn+1 ( ). Indeed, suppose rst s < and consider the expression of EbsPn+1 ( 0)
and EbsPn+1 ( ), as sums of + 1 terms (see Equation (
EbsPn+1 ( 0) = p (max( r; r+1) + max( s 1; s) + max( s; s+1)
[max( r; s) + max( s; r+1) + max( s 1; s+1)]) = p ( r+1 + s 1 + s+1 s r+1 max( s 1; s+1))) = p ( s 1 + s+1 s max( s 1; s+1)) 0 where the last inequality holds since s min( s 1; s+1). Suppose now s = , then a similar approach without the terms involving s + 1 leads to: EbsPn+1 ( ) EbsPn+1 ( 0) = p (max( r; r+1) + max( 1; ) [max( r; ) + max( ; r+1)]) = p ( r+1 + 1 r+1) 0 (since 1 ) Note that these arguments hold also if r = 0. The proposition is deduced by induction, repeatedly replacing the current vector by 0.
(Pn+1)g. 3.3
We are now ready to show the main result of this part: Proposition 2. B 2 arg minfEsPn+1 ( ); 2 (Pn+1)g.
Proof. First we claim that B 2 arg minfEbsPn+1 ( ); 2 (Pn+1)g. Indeed in order to minimize EbsPn+1 ( ) for
2 (Pn+1), Lemma 2 ensures we can restrict ourselves to non decreasing solutions. But for any non decreasing
in (Pn+1), we have EbsPn+1 ( ) = p(n+ ) p( +1) (Equation (
1 >>: iP=1 i = n; 2 N
This admits B as unique solution. Therefore, by Lemma 1 and Equation (
Lemma 3. Given an initial solution 2 (H), with a + b = m; a a , we de ne a solution 0 such that 0a + 0b = m; j 0a 0bj 1, 0a Then we have EbsH ( 0) EbsH ( ). b and j a bj 2 for some 1 b 0b and 0i = i; 8i = 1; : : : ; ; i 6= a; b.
Proof. Let us denote ( a) =
P Then EbsH ( ) = p
P i=1;:::;
j2 anK ( i). Denote also A a logical proposition, and by 1A the boolean function such that maxfj jg the contribution of a to the value of Ebs( ). 1, we have ( a) = maxfj
1) 1( a even)( 2a ). The previous result a, we can express ( a) + ( b) as a function of a: b 2a c( a + d 2a e +b m 2 a c(m
1) 1( a even)( 2a )
a + d m 2 a e 1) 1((m
a) even)( m 2 a )
If we study the di erent combinations of parities of a and m, we get:
De ning the function f ( a) = 32 2a
and the same holds for ( 0a; 0b). 43 m2 m is xed and f ( a) increases for a > m2 . Since 0a a, f ( 0a) f ( a).
Since ( a) + ( b) and ( 0a) + ( 0b) are integers and 0a a, we deduce from Equation (
Lemma 4. EbsH ( )
EbsH ( B) Proof. Note rst that 8 2 (H); EbsH ( ) = EbsH ( ), and assume is a non decreasing solution. We look at the pair of intervals ( 1; ) with the largest length di erence. If j 1 j 1, then is a balanced solution and the lemma is veri ed. Otherwise, we create a new solution 0 by replacing the extreme intervals by a new pair of intervals of size 01 = b n P2i=21 i c and 0 = d n P2i=21 i e. As 1 + = 01 + 0 , by Lemma 3, we deduce EbsH ( ) EbsH ( 0). We denote 00 = 0 the non decreasing solution induced by 0. Then, EbsH ( 0) = EbsH ( 00). Consequently, note that 8j = 1; : : : ; ; 1 0j0 We can make two observations: rst 010 1 and 00 , thus 00 010 1. It means that the maximum length di erence between intervals in the newly created solution doesn't increase compared to the original solution. The second observation is that 01 > 1 and 0 < . This ensures that after at least n2 iterations, the maximum length di erence strictly decreases. Therefore we can iterate this process with the new extreme intervals ( 010 and 00) until we get a solution whose extreme intervals lengths di er by at most 1, in which case all intervals di er by at most 1. This is then a balanced solution, hereby the proof is completed.
B 2 arg minfEsH ( ); 2 (H)g.
EsH ( ) EbsH ( ) EbsH ( B) = EsH ( B).
We then conclude:
Theorem 1. KB 2 arg minfEPn+1 (K); K 2 K(Pn+1)g
(H), we get:
(PProroopf.osAitsionB32), atrhgemninBfE2sPanr+g1 (mi)n; fE2Pn+(1 P(n)+;1)g2(P(rPopn+os1i)tgio(nse2e )E,qaunadtionB(
Proposition 4. KB 2 arg minfECn (K); K 2 K(Cn)g Proof. (Sketch) Given an instance Cn of our problem with k centers, we match an instance Pn+1 of Probabilistic k-Center with k + 1 centers with the extremity nodes (1; n + 1) part of any feasible solution KP of Pn+1. Thus, to any solution KP 2 K(Pn+1) we can match a solution KC 2 K(Cn) of size k. Since it is the lengths of the segments induced by KC that distinguish a solution from another on Cn, KC matches KP if they both induce a series of k segments of same lengths. We assume then, without loss of generality for Cn, that 1 is the length of the shortest segment. The values of the solutions KC and KP verify the following relations:
EPn+1 (KP ) (
The case of planar graphs and in particular with low degree, is very natural for our application. It motivates us investigating the complexity status of our problem in restricted classed of planar graphs to better discriminate polynomial cases and hard cases.
Minimum Dominating Set is shown NP-hard on planar graphs of maximum degree 3 in [25]. More precisely the authors refer to a private communication by David S. Johnson and give the reduction but not the complete proof. The following lemma allows to prove it and will be required later.
The reduction is from Minimum Vertex Cover in planar graphs of maximum degree 3 [?]. This does not imply immediately the hardness of our problem. Indeed, we de ned the Probabilistic k-Center as the case with xed uniform probabilities jV1 j , while k-Center can only be seen as the speci c case where the probabilities are all zeros. In this section, we will show an inapproximability result for Probabilistic k-Center on planar graphs of maximum degree 3 .
Given a planar graph G = (V; E), one builds a graph G0 = (V 0; E0) by replacing each edge uv by a C4 auvbuvcuvduv, linking auv and cuv to u and v, respectively.
Lemma 5. For any t jV j, G has a vertex cover of size t if and only if G0 has a dominating set of size t + jEj, i.e., a (t + jEj)-center of radius at most 1. Moreover, for each edge uv 2 E this (t + jEj)-center has exactly one vertex in fauv; cuvg and none in fbuv; duvg. The transformation is polynomial.
Proof. Consider U V a vertex cover of G of size t. We de ne the set UE as follows. For every edge uv 2 E, if v 2= U , we add cuv to UE . If both u and v are in U , then we add either auv or cuv to UE . Then, U [ UE is a dominating set of size t + jEj in G0.
Assume conversely that G0 has a dominating set K0 V 0 of cardinality t + jEj. For every edge uv 2 E, we necessarily have K0 \ fauv; buv; cuv; duvg =6 ; to cover vertices buv and duv. In the meanwhile, it is never interesting to take buv or duv, since it would always be possible to modify a solution using buv and/or duv into a solution using none them and of the same size. Thus we can always transform K0 into a dominating set satisfying 8uv 2 E; jK0 \ fauv; cuvgj = 1; K0 \ fbuv; duvg = ;. It remains to prove that K0 \ V is a vertex cover of G. Consider an edge uv 2 E and the unique vertex x 2 K0 \ fauv; cuvg. Since K0 is a dominating set, if x = auv, then v 2 K0 \ V and if x = cuv, then u 2 K0 \ V . This completes the proof.
Consider a planar graph G and assume it does not have pending vertices (vertices of degree 1), then using the previous construction, G0 has no pending vertex. Assume G has a minimal vertex cover of size t, we de ne kt = t + jEj and consider a dominating set K0 of size kt in G0, with exactly one vertex in fauv; cuvg and none in fbuv; duvg for any edge uv 2 E. Seeing K0 as a kt-center, we now evaluate the related probabilistic radius for any scenario in the graph G0.
Lemma 6. Using the above notations we have: rK0 = u 1 , 2 u 2 V and not protected else Proof. Since G0 is triangle-free with no pending vertex, and K0 is a dominating set, then we have: 8u 2 V 0; ruK0 2. Consider rst u 2 V and denote by v1; : : : ; vd all neighbors of u in G. Suppose u is not protected (u 2= K0). By de nition of K0, fv1; : : : ; vdg K0 and thus fauv1 ; : : : ; auvd g K0, so whatever the escaping direction, people located on u will reach a center at distance 1. Since K0 is a dominating set in G0, it remains a dominating set in G0 n fug, which proves ruK0 = 1.
Suppose now u 2 V \ K0. Since the considered vertex cover is minimal, there is j 2 f1; : : : ; dg such that vj 2= K0 and thus K0 \ fauvj ; buvj ; cuvj ; duvj g = fcuvj g. Then, the evacuation distances of auvj is 2, and thus rK0 = 2. u
Suppose now u 2 fbvw; dvwg for vw 2 E. Then u 2= K0 and only one neighbor of u is in K0, inducing an evacuation distance of 2 for u.
Suppose nally u 2 favw; cvwg for vw 2 E. If u 2= K0 exactly one of its three neighbors is in K0 and its evacuation distance is also 2. If nally u 2 K0, the evacuation distance of bvw and dvw becomes 2. So, in all cases but the rst one ruK0 = 2 and the proof is complete.
Our proof will require another transformation and the property mentioned in the next lemma. Consider a planar graph, G = (V; E) of degree at most 3. For a given q 2 N; q 2, we transform G into Geq = (Veq; Eeq) as follows. We choose randomly an orientation of edges in E and we replace every edge uv 2 E oriented from u to v by the path Peuqv = fu; x1uv; x2uv; : : : ; x2uqv; vg. Note that jVeqj = jV j + 2qjEj and Eeq = (2q + 1)jEj. Lemma 7. For any t jV j, G = (V; E) has a minimum vertex cover of size t if and only if Geq = (Veq; Eeq) has a minimum vertex cover of size t + qjEj.
Proof. Assume rst U V is a minimum vertex cover of size t in G: 8uv 2 E; fu; vg \ U 6= ;. Then we build Ueq Veq in Geq as follows. We initialize Ueq with all vertices of U . Then, for every edge uv 2 E, if u 2 U , we add vertices x2uiv; 1 i q to Ue . If u 2= U (then v 2 U ), we add vertices x2uiv+1; 0 i q 1. In both cases we have added exactly q vertices and all edges of Peuqv are covered. Thus, jUeqj = t + qjEj. Ueq is minimum because we need the t vertices of the set U to cover at least jEj edges ux1uv, and we need at least qjEj di erent vertices to cover fx1uv; x2uv; : : : ; x2uqv : 8uv 2 Eg.
Assume now that Geq has a minimum vertex cover Ueq of size t + qjEj. For every uv 2 E, Peuqv is covered by at least q + 1 vertices. If u; v 62 Ueq, we can transform Ueq into Uf0q such that u or v is in Uf0q. Then j(Veq n V ) \ Uf0qj = qjEj and thus jV \ Uf0qj = t. It remains to prove that U = V \ Uf0q is a minimum vertex cover. U is a vertex cover because if u 2 Uf0q, then Peuqv is covered in Geq, thus uv is covered in G. If U is not minimum, then suppose U is a minimum vertex cover of size t < t. Then by the transformation given in paragraph 1 we can get a vertex cover for Geq of size t + qjEj < jUeqj which contradicts our initial hypothesis. Thus U is minimum.
The last Lemma we will need for our hardness proof is certainly a known remark but we show it since we did not nd any reference for it.
Lemma 8. Minimum Vertex Cover is NP-hard in planar graphs with vertices of degree 2 or 3. Proof. The decision version of Minimum Vertex Cover is known to be NP-complete on planar graphs of maximum degree 3 [25]. Consider a planar graph G of maximum degree 3 and with a pending vertex v. Consider the graph G0 obtained from G by adding a triangle and linking one of its vertices with v (v is then of degree 2 in G0). G0 is planar with maximum degree 3 and one pending vertex less than G. Moreover, G has a vertex cover of size t if and only if G0 has a minimum vertex cover of size t + 2, which concludes the proof.
We now are ready to prove the main result of this section. Recall that we consider in this paper Probabilistic k-Center under a uniform probability distribution. Note that if k was a xed constant, the number of k-centers would be polynomial and the problem itself could be polynomially solved on any graph. So, we assume that k is part of the instance.
Theorem 2. There is no polynomial time approximation for Probabilistic k-Center guaranteeing a ratio less than 1290 for planar graphs of degrees 2 or 3, unless P=NP.
Proof. The proof is by contradiction. Let satisfy 1 < < 2109 . Consider " > 0 such that < 2109++22"" < 2109 . Take q 2 N, such that 5q " and q 2.
We suppose we have a polynomial approximation algorithm A for Probabilistic k-Center, admitting as argument a planar graph H of degrees 2 or 3 and the number k of centers, and guaranteeing the approximation ratio . We then will show how to use this algorithm to solve the Minimum Vertex Cover problem on planar graphs with vertex degrees 2 or 3. Lemma 8 will give the contradiction, unless P=NP.
Consider a planar graph G = (V; E) with vertex degrees in f2; 3g, instance of Minimum Vertex Cover. Consider the graph Geq = (Veq; Eeq) and then Ge0q = (Veq0; Eeq0). We have in particular: Denoting by (H) and (H)j the minimum size of a vertex cover and a dominating set in a graph H, respectively, we deduce from Lemmas 5 and 7:
We apply the hypothetical approximation algorithm A on Ge0q for di erent values of k, starting with k = 1 and augmenting it.
Suppose rst we use k < (Ge0q) centers and the algorithm computes a center Ke 00. Then, the non-probabilistic radius is at least 2 since Ke 00 cannot be a dominating set in Ge0q and consequently: 8u 2 Veq0; ruKe 00 2 =) E(Ke 00) 2
Suppose now we use k = (Ge0q) = (Geq) + jEeqj centers. Using Lemma 5 on graph Geq, there is a k-center Ke 0
of graph Ge0q satisfying the conditions of Lemma 6 and then, this Lemma ensures:
jVeq0jE(Ke 0) = 2jVeq0j
(jVeqj
(Geq))
We deduce, using Relations 11 and 12:
jVeqj
jEeqj
jVeq0j
(Geq)
(Ge0q)
= jV j + 2qjEj
= (2q + 1)jEj
= jVeqj + 4jEeqj
= jV j + (10q + 4)jEj
=
=
=
(G) + qjEj
(Geq) + jEeqj
(G) + (3q + 1)jEj
(
jEj, thus: E(Ke 0) < 2jV j + (19q + 8)jEj = 2 jV j + (10q + 4)jEj
qjEj jV j + (10q + 4)jEj E(Ke 0) < 2
qjEj (10q + 5)jEj = 2
q 10q + 5 19 + 2" 10 + " will satisfy E(Ke 0 ) of value: where the last inequality holds since 5q
". As a consequence, since an optimal probabilistic solution Ke 0 E(Ke 0), the approximation algorithm A will determine an approximated center K0 in Gfq0
E(Ke 0) <
19+2" 20+2"10+" 19+2" 1190++2"" = 2
Note that, given a center Ke 0, computing its probabilistic radius can be done in polynomial time since, for any vertex v 2 Veq0, computing rvKe 0 can be performed using any minimum path algorithm. So, we apply successively the approximation algorithm A on the graph Ge0q for increasing values of k, starting with k = 1, until the computed center Ke 0 satis es E(Ke 0) < 2. Equations 12, 13 and14 ensure that, the algorithm stops after k = (Ge0q) = (Geq) + jEeqj iterations and then, (G) = jKe 0j (3q + 1)jEj. Since constructing Ge0q and evaluating E(Ke 0) can be done in polynomial time, and since algorithm A will be run less than jV j times, the whole process is polynomial. This is a contradiction if P6=NP, and the proof is complete.
To our knowledge, this paper introduces the rst probabilistic version of Minimum k-Center. As illustrated in this work, de ning the problem already leads to interesting discussions. So far, we have considered only single node disruption scenarios under a uniform distribution of probabilities and for a modi cation strategy that preserves the location of the centers but a ects only the allocation. Even though relatively restrictive, this version is natural for our application and is already non-obvious. Then, we propose an explicit solution on paths and cycles. The main idea is to express the objective function as the sum of two parts (contribution of the skeleton and the body) and then prove independently that the solution minimizes simultaneously both terms. This approach might be used in a more general setting. Finally we prove that this restrictive version is already NP-hard to approximate it within a factor 1290 on planar graphs of bounded degree 3.
This motivates investigating the complexity status of this version on more restrictive classes of graphs, in particular on subgrids (subgraphs of grids), that correspond to some real case applications. Minimum k-Center is polynomial on trees [25]; it motivates studying the complexity of Probabilistic k-Center on trees, which, to our knowledge, remains open. The next question will be to design approximation algorithms for the hard cases and a third objective will be to consider larger ranges of impact and any probabilities. Indeed, our analysis on paths and cycles cannot be immediately extended to non uniform probability systems.
n2 , KB is an optimum solution for Probabilistic k-Center on paths and cycles.
Proof. In H, at least one vertex out of two consecutive vertices is in KB. Therefore iB 2; 8i 2 1; : : : ; ,
and by Equations (
Lemma 1 EsH ( B) = EbsH ( B) , EsH ( B) = EbsH ( B) and EH ( B) = EbH ( B).
Proof. In H we have:
qB 2 f n ; n g; q 2 f1; : : : ; g. As k < n2 , then q2fm1;a::x:; gb 2qB c =
n 1 qB 1; 8q = 1; : : : ; . The same holds for a balanced solution B in with qB 2 f nk ; nk g.
Then given Equation (