# Spider Covers and Their Applications

Authors: Filomena De Santis; Luisa Gargano; Mikael Hammar; Alberto Negro; Ugo Vaccaro
Journal: ISRN Discrete Mathematics
 (2012)

---

## Abstract

We introduce two new combinatorial optimization problems: the Maximum Spider Problem and the Spider Cover Problem; we study their approximability and illustrate their applications. In these problems we are given a directed graphG=(V,E), a distinguished vertex s, and a family D of subsets of vertices. A spider centered at vertex s is a collection of arc-disjoint paths all starting at s but ending into pairwise distinct vertices. We say that a spider covers a subset of vertices X if at least one of the endpoints of the paths constituting the spider other than s belongs to X. In the Maximum Spider Problem the goal is to find a spider centered at s that covers the maximum number of elements of the family D. Conversely, the Spider Cover Problem consists of finding the minimum number of spiders centered at s that covers all subsets in D. We motivate the study of the Maximum Spider and Spider Cover Problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the Maximum Spider Problem and a (log|𝒟|+1)-approximation algorithm for the Spider Cover Problem.


---

## Body

## 1.  Introduction

Given a digraphG=(V,E) and a vertex s∈V, a spider centered at s is a subgraph S of G consisting of arc-disjoint paths sharing the initial vertex s and ending into pairwise distinct vertices. The vertex s is called the center of the spider. The endpoints of the paths composing the spider S—other than the center s—are called the terminals of the spider. In other words, a spider is a subdivision of K1,m, where m is the number of terminals. Given a spider S, we say that S reaches a vertex x∈V if x is a terminal of S; we say that the spider S covers a subset of vertices D⊆V if S reaches at least a vertex in D.In this paper we consider the approximability of the following problems.Maximum Spider Problem (MSP)
We are given a digraphG=(V,E), a distinguished node s, and a family 𝒟⊆2V∖{s} of subsets of vertices. The objective is to find a spider S centered at s such that the number of subsets D∈𝒟 covered by S is maximum among all possible spiders centered at s.We also consider the related minimization problem, where one wants to cover all the elements of𝒟.Spider Cover Problem (SCP)
As before, we are given a digraphG=(V,E), a distinguished vertex s∈V, and a family 𝒟∈2V∖{s} of subsets of vertices. The goal is to find a minimum cardinality collection of spiders centered at s such that each subset D∈𝒟 is covered by at least a spider in the collection.


### 1.1. Motivations

The Maximum Spider and the Spider Cover Problems are far reaching generalizations and unifications of several Maximum Coverage and Set Cover Problems which, in turn, are fundamental algorithmic and combinatorial problems that arise frequently in a variety of settings [3]. To start, recall that in the basic formulation of the Maximum Coverage Problem [3], one is given a ground set X, a collection of sets 𝒮={S1,S2,…,Sm}, where each Sj⊆X, for j=1,…,m, and an integer k. The goal is to find ℓ≤k sets Si1,…,Siℓ such that the cardinality |∪j=1ℓSij| of their union is maximum. To see that the Maximum Coverage Problem is a very particular case of the Maximum Spider Problem, let us consider the digraph G=(V,E) of Figure 1, with node set V={s,x1,…,xk,S1,…,Sm}. The vertex s is connected to each of the nodes x1,…,xk, and each xi is connected to every Sj, for i=1,…,k and j=1,…,m. The family 𝒟⊆2V-{s} is defined as 𝒟={Du:u∈X}, where Du={Si:u∈Si}. One can see that the Maximum Spider Problem in G is equivalent to the Maximum Coverage Problem on the original instance X, 𝒮, and k. To that purpose, let us proceed as follows. Let S be a spider in G that covers a maximum number μ of subsets D∈𝒟. Let Du1,…,Duμ be these subsets. By our definition of spider cover, the (at most k) terminals of S in G correspond to some Si1,…,Siℓ,ℓ≤k, such that for any Dut∈{Du1,…,Duμ} there exists Sij∈{Si1,…,Siℓ} for which Sij∈Dut. This implies that for any ut∈{u1,…,uμ} there exists Sij such that ut∈Sij, consequently ∪j=1ℓSij⊇{u1,…,uμ} and |∪j=1ℓSij|≥μ. Conversely, let Si1,…,Siℓ,ℓ≤k, be a solution to the Maximum Coverage Problem on the original instance X,𝒮, and k. Let ∪j=1ℓSij={u1,…,uμ}. Consider now the spider s in G starting at s and having terminal nodes equal to Si1,…,Siℓ. By definition, spider S covers at least the μ subsets Du1,…,Duμ.Figure 1
Maximum Coverage as a Maximum Spider Problem.Thus, the Maximum Coverage Problem corresponds to the Maximum Spider Problem in a very simple digraphG. By allowing more flexibility in the structure of G, one can describe many more combinatorial optimization problems in this framework. For instance, Chekuri and Kumar in [4] considered the following generalization of Maximum Coverage.Maximum Coverage with Group Budget Constraints (MCG) (see [4])
We are given a ground setX and a collection 𝒮={S1,…,Sm} of subsets of X. We are also given sets 𝒢1,…,𝒢ℓ, each 𝒢i⊆𝒮={S1,…,Sm}, with 𝒢i∩𝒢j=∅ for i≠j, and integer bounds k,k1,…,kℓ. A solution is a subset ℋ⊆{S1,…,Sm}, such that |ℋ|≤k and |ℋ∩𝒢i|≤ki, for i=1,…,ℓ. The goal is to find a solution ℋ such that |⋃H∈ℋ‍H| is maximized.Before showing how MGC easily fits into our scenario, let us mention that the MGC problem itself was introduced and studied in [4] since it represents a useful generalization of several combinatorial optimization problems, like the multiple depot k-traveling repairmen problem with covering constraints [5] and the orienteering problem with time windows [6–8].Given an instance〈X,𝒢1,…,𝒢ℓ,{S1,…,Sm},k,k1,…,kℓ〉 of MCG, consider the digraph G=(V,E) with vertex set
(1.1)V={s,x1,…,xk,y11,…y1k1,…,yℓ1,…,yℓkℓ,S1,…,Sm}.
There is an edge from s to each xi,i=1,…,k. Moreover, there is a complete bipartite graph between {x1,…,xk} and {y11,…y1k1,…,yℓ1,…,yℓkℓ} (with orientation of the edges going from the x's to the y's). Finally, there is a complete bipartite graph between the set 𝒴i={yi1,…,yiki} and the set 𝒢i⊆{S1,…,Sm}, for i=1,…,ℓ and, in case ∑i=1ℓ‍ki<k, there is a complete bipartite graph between {x1,…,xk} and 𝒮∖⋃i=1ℓ‍𝒢i. As before, the family 𝒟 is defined as consisting of subsets of vertices Du={Si:u∈Si}, for each u∈X. Figure 2 below depicts the situation.Figure 2
MGC as a Maximum Spider Problem.Again, it is not hard to see that MGC is equivalent to the Maximum Spider Problem in the graphG. At this point it should be clear that by variating the structure of the graph between the vertex s and the family of subsets {S1,…,Sm}, one can describe many more covering problems.Just as the Maximum Spider Problem encompasses a variety of coverage problems formulated in term of maximization of the objective function, the related Spider Cover minimization problem includes particular cases variants and extensions of the well-known Set Cover Problem. One of such an extension was considered in [4, 9, 10].Set Cover with Group Budget (SCG)
We are given a ground setX and a family 𝒮={S1,…,Sm} of subsets of X. The family 𝒮 is partitioned into subfamilies 𝒢1,…,𝒢ℓ. The goal is to find an ℋ⊆𝒮 such that all elements of X are covered by sets in ℋ, and maxi=1,…,ℓ|ℋ∩𝒢i| is minimized.Elkin and Kortsarz [9] studied the SCG problem as a preliminary tool for their multicasting algorithm in synchronous directed networks. Gargano et al. [10] studied the SCG problem in the context of multicasting in optical networks. Interestingly, Gargano et al. [10] also noticed that SCG naturally arises in airline scheduling problems [11]. We trust that the experienced reader can now appreciate the flexibility of our approach by checking that the SCG is equivalent to the Spider Cover problem in the graph shown in Figure 3. The family 𝒟 to cover is 𝒟={Du:u∈X}, where for each u∈X we have Du={S∈𝒮:u∈S}.Figure 3
SCG as a Spider Cover Problem.In general, we expect that the capability of our approach to easily describe and deal with diverse requirements in covering problems to be quite useful. In any case, it seems to provide a nice and unified view of many different questions.


### 1.2. Our Results in Comparison with Previous Work

To the best of our knowledge, the Maximum Spider and the Spider Cover Problems have not been considered before, apart from the different special cases mentioned in the previous section. Our results are the following.(1)
We show that the greedy approach yields a 2-approximation algorithm for the Maximum Spider Problem. (In this paper approximation ratios for both maximization problems and minimization problems will be greater than 1). It is remarkable that we achieve the same approximation ratio obtained in [4] for the Maximum Coverage with Group Budget Constraints, although our Maximum Spider Problem is much more general. Since the Maximum Spider Problem contains the classical Maximum Coverage Problem as particular case, from results of [12] it follows that it is hard to approximate within a factor of e/(e-1)-o(1), unless NP⊂Dtime(nloglogn). In the paper [4] it is additionally proved that the approximation factor 2 is tight for their problem in the oracle model. Obviously, this tightness of analysis transfers also to our Maximum Spider Problem.(2)
We give a greedy algorithm for the Spider Cover Problem with approximation ratiolog|𝒟|+1. Again, we match the results of [4, 9, 10], who obtained the same result in case the graph G is the simple tree of Figure 3. Since the Maximum Spider Problems include the Set Cover problem as a particular case, from [12] one gets a (1-ϵ)ln|𝒟|) factor for the hardness of its approximation, for any ϵ>0. We also observe that our algorithm for the Spider Cover Problem provides a O(log|𝒟|)-approximation algorithm for the Multicasting-to-Groups Problems considered in [10], extending the main result of the same paper from trees to general networks. The problem considered therein was to find a set of paths from a source node to at least one node in each subset of a set of groups 𝒟 and assignments of wavelengths to paths so that paths sharing a same physical link of the network are assigned different wavelengths. The goal is to minimize the number of wavelengths. It can be seen that the paths constituting the spiders covering the family 𝒟, and an assignment of different wavelengths to paths in different spiders, give an admissible solution to the Multicasting-to-Group problem in general optical networks.


## 1.1. Motivations

The Maximum Spider and the Spider Cover Problems are far reaching generalizations and unifications of several Maximum Coverage and Set Cover Problems which, in turn, are fundamental algorithmic and combinatorial problems that arise frequently in a variety of settings [3]. To start, recall that in the basic formulation of the Maximum Coverage Problem [3], one is given a ground set X, a collection of sets 𝒮={S1,S2,…,Sm}, where each Sj⊆X, for j=1,…,m, and an integer k. The goal is to find ℓ≤k sets Si1,…,Siℓ such that the cardinality |∪j=1ℓSij| of their union is maximum. To see that the Maximum Coverage Problem is a very particular case of the Maximum Spider Problem, let us consider the digraph G=(V,E) of Figure 1, with node set V={s,x1,…,xk,S1,…,Sm}. The vertex s is connected to each of the nodes x1,…,xk, and each xi is connected to every Sj, for i=1,…,k and j=1,…,m. The family 𝒟⊆2V-{s} is defined as 𝒟={Du:u∈X}, where Du={Si:u∈Si}. One can see that the Maximum Spider Problem in G is equivalent to the Maximum Coverage Problem on the original instance X, 𝒮, and k. To that purpose, let us proceed as follows. Let S be a spider in G that covers a maximum number μ of subsets D∈𝒟. Let Du1,…,Duμ be these subsets. By our definition of spider cover, the (at most k) terminals of S in G correspond to some Si1,…,Siℓ,ℓ≤k, such that for any Dut∈{Du1,…,Duμ} there exists Sij∈{Si1,…,Siℓ} for which Sij∈Dut. This implies that for any ut∈{u1,…,uμ} there exists Sij such that ut∈Sij, consequently ∪j=1ℓSij⊇{u1,…,uμ} and |∪j=1ℓSij|≥μ. Conversely, let Si1,…,Siℓ,ℓ≤k, be a solution to the Maximum Coverage Problem on the original instance X,𝒮, and k. Let ∪j=1ℓSij={u1,…,uμ}. Consider now the spider s in G starting at s and having terminal nodes equal to Si1,…,Siℓ. By definition, spider S covers at least the μ subsets Du1,…,Duμ.Figure 1
Maximum Coverage as a Maximum Spider Problem.Thus, the Maximum Coverage Problem corresponds to the Maximum Spider Problem in a very simple digraphG. By allowing more flexibility in the structure of G, one can describe many more combinatorial optimization problems in this framework. For instance, Chekuri and Kumar in [4] considered the following generalization of Maximum Coverage.Maximum Coverage with Group Budget Constraints (MCG) (see [4])
We are given a ground setX and a collection 𝒮={S1,…,Sm} of subsets of X. We are also given sets 𝒢1,…,𝒢ℓ, each 𝒢i⊆𝒮={S1,…,Sm}, with 𝒢i∩𝒢j=∅ for i≠j, and integer bounds k,k1,…,kℓ. A solution is a subset ℋ⊆{S1,…,Sm}, such that |ℋ|≤k and |ℋ∩𝒢i|≤ki, for i=1,…,ℓ. The goal is to find a solution ℋ such that |⋃H∈ℋ‍H| is maximized.Before showing how MGC easily fits into our scenario, let us mention that the MGC problem itself was introduced and studied in [4] since it represents a useful generalization of several combinatorial optimization problems, like the multiple depot k-traveling repairmen problem with covering constraints [5] and the orienteering problem with time windows [6–8].Given an instance〈X,𝒢1,…,𝒢ℓ,{S1,…,Sm},k,k1,…,kℓ〉 of MCG, consider the digraph G=(V,E) with vertex set
(1.1)V={s,x1,…,xk,y11,…y1k1,…,yℓ1,…,yℓkℓ,S1,…,Sm}.
There is an edge from s to each xi,i=1,…,k. Moreover, there is a complete bipartite graph between {x1,…,xk} and {y11,…y1k1,…,yℓ1,…,yℓkℓ} (with orientation of the edges going from the x's to the y's). Finally, there is a complete bipartite graph between the set 𝒴i={yi1,…,yiki} and the set 𝒢i⊆{S1,…,Sm}, for i=1,…,ℓ and, in case ∑i=1ℓ‍ki<k, there is a complete bipartite graph between {x1,…,xk} and 𝒮∖⋃i=1ℓ‍𝒢i. As before, the family 𝒟 is defined as consisting of subsets of vertices Du={Si:u∈Si}, for each u∈X. Figure 2 below depicts the situation.Figure 2
MGC as a Maximum Spider Problem.Again, it is not hard to see that MGC is equivalent to the Maximum Spider Problem in the graphG. At this point it should be clear that by variating the structure of the graph between the vertex s and the family of subsets {S1,…,Sm}, one can describe many more covering problems.Just as the Maximum Spider Problem encompasses a variety of coverage problems formulated in term of maximization of the objective function, the related Spider Cover minimization problem includes particular cases variants and extensions of the well-known Set Cover Problem. One of such an extension was considered in [4, 9, 10].Set Cover with Group Budget (SCG)
We are given a ground setX and a family 𝒮={S1,…,Sm} of subsets of X. The family 𝒮 is partitioned into subfamilies 𝒢1,…,𝒢ℓ. The goal is to find an ℋ⊆𝒮 such that all elements of X are covered by sets in ℋ, and maxi=1,…,ℓ|ℋ∩𝒢i| is minimized.Elkin and Kortsarz [9] studied the SCG problem as a preliminary tool for their multicasting algorithm in synchronous directed networks. Gargano et al. [10] studied the SCG problem in the context of multicasting in optical networks. Interestingly, Gargano et al. [10] also noticed that SCG naturally arises in airline scheduling problems [11]. We trust that the experienced reader can now appreciate the flexibility of our approach by checking that the SCG is equivalent to the Spider Cover problem in the graph shown in Figure 3. The family 𝒟 to cover is 𝒟={Du:u∈X}, where for each u∈X we have Du={S∈𝒮:u∈S}.Figure 3
SCG as a Spider Cover Problem.In general, we expect that the capability of our approach to easily describe and deal with diverse requirements in covering problems to be quite useful. In any case, it seems to provide a nice and unified view of many different questions.


## 1.2. Our Results in Comparison with Previous Work

To the best of our knowledge, the Maximum Spider and the Spider Cover Problems have not been considered before, apart from the different special cases mentioned in the previous section. Our results are the following.(1)
We show that the greedy approach yields a 2-approximation algorithm for the Maximum Spider Problem. (In this paper approximation ratios for both maximization problems and minimization problems will be greater than 1). It is remarkable that we achieve the same approximation ratio obtained in [4] for the Maximum Coverage with Group Budget Constraints, although our Maximum Spider Problem is much more general. Since the Maximum Spider Problem contains the classical Maximum Coverage Problem as particular case, from results of [12] it follows that it is hard to approximate within a factor of e/(e-1)-o(1), unless NP⊂Dtime(nloglogn). In the paper [4] it is additionally proved that the approximation factor 2 is tight for their problem in the oracle model. Obviously, this tightness of analysis transfers also to our Maximum Spider Problem.(2)
We give a greedy algorithm for the Spider Cover Problem with approximation ratiolog|𝒟|+1. Again, we match the results of [4, 9, 10], who obtained the same result in case the graph G is the simple tree of Figure 3. Since the Maximum Spider Problems include the Set Cover problem as a particular case, from [12] one gets a (1-ϵ)ln|𝒟|) factor for the hardness of its approximation, for any ϵ>0. We also observe that our algorithm for the Spider Cover Problem provides a O(log|𝒟|)-approximation algorithm for the Multicasting-to-Groups Problems considered in [10], extending the main result of the same paper from trees to general networks. The problem considered therein was to find a set of paths from a source node to at least one node in each subset of a set of groups 𝒟 and assignments of wavelengths to paths so that paths sharing a same physical link of the network are assigned different wavelengths. The goal is to minimize the number of wavelengths. It can be seen that the paths constituting the spiders covering the family 𝒟, and an assignment of different wavelengths to paths in different spiders, give an admissible solution to the Multicasting-to-Group problem in general optical networks.


## 2. A Greedy Algorithm for the Maximum Spider Problem

In this section we will present a2-approximation greedy algorithm for the Maximum Spider Problem (MSP).Given an instance〈G,s,𝒟〉 of the MSP, where G=(V,E) is a digraph, s is a designated vertex in V, and 𝒟 is a family of subsets of V∖{s}, we say that the subsets of vertices X⊆V are reachable if there exists a spider in G, with center in s, such that each node v∈X is reached by such a spider. In other words, X is reachable if there is a spider in G whose set of terminals includes X. For any set X⊆V—not necessarily reachable—we define C(X) as the number of elements in 𝒟 covered by X, that is,
(2.1)C(X)=|{D∈𝒟:D∩X≠∅}|.
In terms of the function C(·), our original objective is essentially that of finding a reachable set X of maximum value C(X).For anyX,Y⊆V, we define the covering improvementC(Y∣X) of Y over X as
(2.2)C(Y∣X)=C(X∪Y)-C(X)=|{D∈𝒟:D∩Y≠∅,D∩X=∅}|.Definition 2.1.
Given a reachable setX we say that: (1)
a nodex∈Vimproves on X if X∪{x} is reachable;(2)
a nodex∈Vmaximally improves on X if C(X∪{x})=maxyC(X∪{y}), where the maximum is taken on all nodes y that improve on X;(3)
the setX is maximal if no node x∈V∖X improves on X.We can now describe the skeleton of our 2-approximation algorithm. (We point out that the algorithm could also stop as soon as it finds a first node maximally improving onX with the property that C({x}∣X)=0. However, we let max_sp generate a maximal set X to make the analysis cleaner).In the rest of this section we will show how to efficiently implement step 2. Of the above greedy algorithm and how to compute a spider centered ats and with set of terminals X, and we will also show that the number of sets in 𝒟 covered by the terminals in X is at least half of the optimum number.Let us first check that the algorithm is polynomial.Lemma 2.2.
The algorithmmax_sp(G,s,𝒟) is polynomial.Proof.
In order to compute the nodex∈V∖X that maximally improves on X we proceed as follows. First, for each y∈V∖X we check whether X∪{y} is reachable, that is, whether there is a spider centered at s and with set of terminals equal to X∪{y}. This can be done by constructing a flow network (For undefined terminology about flows in networks, see for example [13]) from G, assigning the source node at s, connecting all nodes in X∪{y} to a sink node t, setting all flow capacities equal to 1, and by verifying whether or not in this flow network there exists a flow of value |X|+1. This entire procedure can be performed clearly in polynomial time. Subsequently, among all y's for which X∪{y} is reachable, we compute the one that maximally improves on X by using the identity C(X∪{y})=C(X)+C({y}∣X). Finally, the spider that reaches the set X,—output of the algorithm max_sp—is computed from the executions of the maximum flow algorithm, and it consists of all the flow paths from s to X with assigned flow value equal to 1.In order to show that Algorithmmax_sp(G,s,𝒟) is a 2-approximation algorithm for the Maximum Spider Problem, we first need the following technical result.Lemma 2.3.
Let〈G=(V,E),s,𝒟〉 be an instance of the Maximum Spider Problem, and let ℛ={X∣X⊆V,Xis  reachable} denote the family of reachable subsets of V. For any X,Y∈ℛ with |X|>|Y| there exists x∈X such that the set Y∪{x}∈ℛ.Proof.
Consider two arbitrary setsX,Y∈ℛ, such that |X|>|Y|. Let S(X) denote a spider reaching X, and let S(Y) be a spider reaching Y. We will show that there exists a new spider S(W), with terminals W=Y∪{x}, where x∈X∖Y. Hence, we will get that W∈ℛ.
Starting fromG, let us construct the flow network G'=(V',E') with
(2.3)V'=V∪{t},E'=E∪{(v,t)∣v∈X∪Y},
where s is the source of the flow network, t is the sink, and each arc has capacity 1.
The existence of the spiderS(Y) in G centered in s and reaching all nodes in Y implies the existence of a flow f in G' such that
(2.4)f(u,v)={1if(u,v)is an arc ofS(Y)oru∈Y,v=t,0otherwise.
The value of f is |Y|.
In the same way, the existence of spiderS(X) in G implies the existence of a flow of value |X| in G'. Since |X|>|Y|, we know that the maximum flow in G' is at least |Y|+1. Hence, the flow f given in (2.4) can be augmented. Consider then the residual graph Df obtained starting from the initial flow f; Df must contain an augmenting path P from s to t. Moreover, the path P must use the arc (x,t) for some x∈X∖Y (since Df only contains the arcs (t,y) for any y∈Y). Consider then the augmented flow g implied by f and P. Since it modifies the values of f only on arcs on P, we get that g induces a set of arc disjoint paths in G from s to the nodes in Y∪{x}. This gives the desired spider S(W) covering W=Y∪{x}.We notice that the familyℛ is hereditary, that is, any subset of a reachable set is reachable. This fact and Lemma 2.3 tell us thatLemma 2.4.
The pair(V,ℛ) forms a matroid.However, the set system associated to our optimization problem is not(V,ℛ), but it is (𝒟,𝒢), where 𝒢={𝒟'⊆𝒟:all subsets in𝒟'are covered by a spider inGcentered  ats}; which is hereditary but not a matroid.Nonetheless, the fact that(V,ℛ) is a matroid represents a useful fact for us. Indeed our coverage function is submodular, for example for any X,Y⊆V it holds
(2.5)C(X∪Y)+C(X∪Y)≤C(X)+C(Y).
Hence the Maximum Spider Problem corresponds to the maximization of the submodular function C(·) on the independent sets of the matroid (V,ℛ). By a well-known result of Nemhauser et al. [14] we have that the greedy algorithm max_sp given in Algorithm 1 returns a set X such that
(2.6)C(X*)≤2C(X),
where X* represents an optimal solution to the problem. Hence, we have proved the desired approximation result.Algorithm 1:The algorithm for the Maximum Spider Problem on G, s, and 𝒟.
Algorithm  max_Sp(G,s,𝒟)
(
1
)  Set X←∅
(
2
)  while  X is not maximal
(
3
)  Let x∈V∖X be the node that maximally improves on X
(
4
)  Set X←X∪{x}.
(
5
)  Output  X, C(X), and the spider with set of terminals X.Theorem 2.5.
The Algorithmmax_sp(G,s,𝒟) is a 2-approximation algorithm for the Maximum Spider Problem.


## 3. The Spider Cover Problem

In this section we will build up on the results for the Maximum Spider Problem in order to design aO(log|𝒟|)-approximation algorithm for the Spider Cover Problem. Recall that in this latter problem we are given digraph G, a vertex s, a family 𝒟⊆2V∖{s}, and the goal is to cover all elements in 𝒟 by using the minimum number of spiders centered at s. Our first step will be to introduce a parametrized family of digraphs {Ht}t≥1 and reduce the problem of determining the minimum number of spiders in G necessary to cover all elements of 𝒟 to the problem of determining the minimum value of t for which Ht contains a single spider covering all vertices in a designated subset of vertices of Ht. Subsequently, using iteratively the approximation algorithm max_sp on certain Ht’s, plus some additional constructions, will allow us to construct an approximation algorithm for the Spider Cover Problem.


### 3.1. Constructing the DigraphHt

Let〈G=(V,E),s,𝒟〉 be an instance of the Spider Cover Problem, and let t≥1 be an integer. We first construct t graphs G1=(V1,E1),…,Gt=(Vt,Et) as follows: for any v∈V the vertex set Vi of the ith digraph Gi contains a corresponding vertex vi, for i=1,…,t. Vertex vi will be called the ith copy of v in the final digraph Ht. If the designated vertex s is connected to k vertices v1,…,vk in G, then each Vi contains k copies of s, let si1,…,sik be such  copies, for i=1,…,t.Now for the arcs in theGi’s. For each arc (u,v)∈E, u≠s≠v, we insert a corresponding arc (ui,vi) in Ei. We also insert in Ei the arcs (si1,vi1),…,(sik,vik), where, we recall, (s,v1),…,(s,vk)∈E.For the final construction ofHt we introduce new nodes nt(v), for each v∈∪D∈𝒟D, and a special node z. There are arcs between z and each sij, and for each v∈∪D∈𝒟D there is an arc (vi,nt(v)) from vi to nt(v), for each i=1,…,t.Formally,Ht=(Ut,At) is a directed graph where
(3.1)Ut=(⋃i=1t‍Vi)∪{z}∪{sij:i=1,…,t,j=1,…,k}∪{nt(v):v∈⋃D∈𝒟‍D},At={(z,sij):i=1,…,t,j=1,…,k}∪(⋃i=1t‍Ei)∪{(vi,nt(v)):v∈⋃D∈𝒟‍D,i=1,…,t}.An example of digraphG and associated graph H2 is presented in Figure 4. The relevance of digraph Ht to our questions is explained by the following two evident results.(a) A digraphG; (b) its corresponding graph H2 when 𝒟 consists of D1={a,c} and D2={b,c}, and the designated node is s.
(a)
(b)Lemma 3.1.
Let〈G,s,𝒟〉 be an instance of the Spider Cover Problem. There are t spiders centered at s in G that altogether reach a set of nodes X⊆∪D∈𝒟D if and only if there exists a spider centered at z in the digraph Ht reaching the corresponding set of nodes {nt(x):x∈X}.Notice that thet spiders in G can also be easily constructed from the “big” spider in Ht and vice versa.Given an instance〈G,s,𝒟〉 of the Spider Cover Problem, let nt(𝒟) be the family of subsets of nodes of digraph Ht consisting of all subsets nt(D)={nt(v):v∈D}, for any D∈𝒟.Theorem 3.2.
An instance〈G,s,𝒟〉 of the Spider Cover Problem admits an optimal solution with t* spiders if and only if t* is the minimum integer for which an optimal solution of the Maximum Spider Problem on the instance 〈Ht*,z,nt*(𝒟)〉 consists in a spider covering all elements in the family of subsets nt*(𝒟).


### 3.2. The Spider Cover Algorithm

Our spider cover algorithmsp_cov(G,s,𝒟) is presented in next box Algorithm 2. The algorithm consists of successive iterations, based on the Algorithm max_sp. At each iteration a certain set of spiders is constructed in order to cover as many subsets in 𝒟 as possible. Namely, at each iteration, if Δ⊆𝒟 is the subfamily of subsets not covered yet, the algorithm seeks for the minimum number w for which the algorithm max_sp(Hw,z,nw(Δ)) returns a spider centered in z that covers at least half of the subsets in nw(Δ). The minimum number w can be obtained by applying the algorithm max_sp(Hw,z,nw(Δ)) in a binary search fashion, with w in the range [1,|Δ|]. Thereafter, via Lemma 3.1, one obtains w spiders in G from the “big” spider in Hw.Algorithm 2:The algorithm for the Spider Cover Problem on G, s, and 𝒟.
Algorithm  sp_cov(G,s,𝒟)
SetΔ=𝒟   [Family of groups that need to be covered]
SetS=∅, w¯=0
Repeat
(i) Compute the minimum integerw (with 1≤w≤|Δ|) such that the algorithm
max_sp (Hw,z,nw(Δ)) outputs a spider S¯ in Hw reaching a set X for which
C(X)=|{D∈nw(Δ):D∩X≠∅}|≥|nw(Δ)|/2=|Δ|/2
(ii) From the spiderS¯ in Hw obtain (via Lemma  4) w new spiders in G that cover
at least |Δ|/2 elements of Δ
(iii) LetΔ be the new family of uncovered subsets, put in 𝒮 the new w spiders,
set w¯=w¯+w.
Until  Δ=∅.
Output:  𝒮 and w¯.The total number of used spidersw¯ will be the sum of the number of spiders used at each iteration.We show now that the number of spiders returned by the algorithmsp_cov(G,s,𝒟) is at most log2|𝒟|+1 times the optimal number of spiders necessary for the given instance 〈G,s,𝒟〉 of the Spider Cover Problem.Theorem 3.3.
The number of spiders returned by the algorithmsp_cov(G,s,𝒟) is w¯≤w*(log2|𝒟|+1), where w* is the number of spiders in an optimal solution for the given instance 〈G,s,𝒟〉 of the problem.Proof.
Consider any iteration of the cycle. The algorithm computes the minimum integerw such that max_sp(Hw,z,nw(Δ)) outputs a spider covering at least |Δ|/2 elements of the family nw(Δ). This means that the current size of the family of yet uncovered groups is decreased of at least 1/2 of its value during each iteration. Hence, the algorithm sp_cov(G,s,𝒟) consists of at most log|𝒟|+1 iterations.
Moreover, at each iteration the minimum integerw computed by the algorithm is upperbounded by w*. In fact, it is certain that in Hw* there exists a spider reaching |Δ| elements of nw*(𝒟), for any Δ⊆𝒟, and the algorithm max_sp(Hw*,z,nw*(Δ)) is guaranteed to find a spider that covers at least |Δ|/2 elements of nw*(Δ).
We can then conclude that the total number of spidersw¯ used by sp_cov(G,s,𝒟), which is the sum of all the values obtained at the various iterations, is upperbounded by w*(log2|𝒟|+1).


## 3.1. Constructing the DigraphHt

Let〈G=(V,E),s,𝒟〉 be an instance of the Spider Cover Problem, and let t≥1 be an integer. We first construct t graphs G1=(V1,E1),…,Gt=(Vt,Et) as follows: for any v∈V the vertex set Vi of the ith digraph Gi contains a corresponding vertex vi, for i=1,…,t. Vertex vi will be called the ith copy of v in the final digraph Ht. If the designated vertex s is connected to k vertices v1,…,vk in G, then each Vi contains k copies of s, let si1,…,sik be such  copies, for i=1,…,t.Now for the arcs in theGi’s. For each arc (u,v)∈E, u≠s≠v, we insert a corresponding arc (ui,vi) in Ei. We also insert in Ei the arcs (si1,vi1),…,(sik,vik), where, we recall, (s,v1),…,(s,vk)∈E.For the final construction ofHt we introduce new nodes nt(v), for each v∈∪D∈𝒟D, and a special node z. There are arcs between z and each sij, and for each v∈∪D∈𝒟D there is an arc (vi,nt(v)) from vi to nt(v), for each i=1,…,t.Formally,Ht=(Ut,At) is a directed graph where
(3.1)Ut=(⋃i=1t‍Vi)∪{z}∪{sij:i=1,…,t,j=1,…,k}∪{nt(v):v∈⋃D∈𝒟‍D},At={(z,sij):i=1,…,t,j=1,…,k}∪(⋃i=1t‍Ei)∪{(vi,nt(v)):v∈⋃D∈𝒟‍D,i=1,…,t}.An example of digraphG and associated graph H2 is presented in Figure 4. The relevance of digraph Ht to our questions is explained by the following two evident results.(a) A digraphG; (b) its corresponding graph H2 when 𝒟 consists of D1={a,c} and D2={b,c}, and the designated node is s.
(a)
(b)Lemma 3.1.
Let〈G,s,𝒟〉 be an instance of the Spider Cover Problem. There are t spiders centered at s in G that altogether reach a set of nodes X⊆∪D∈𝒟D if and only if there exists a spider centered at z in the digraph Ht reaching the corresponding set of nodes {nt(x):x∈X}.Notice that thet spiders in G can also be easily constructed from the “big” spider in Ht and vice versa.Given an instance〈G,s,𝒟〉 of the Spider Cover Problem, let nt(𝒟) be the family of subsets of nodes of digraph Ht consisting of all subsets nt(D)={nt(v):v∈D}, for any D∈𝒟.Theorem 3.2.
An instance〈G,s,𝒟〉 of the Spider Cover Problem admits an optimal solution with t* spiders if and only if t* is the minimum integer for which an optimal solution of the Maximum Spider Problem on the instance 〈Ht*,z,nt*(𝒟)〉 consists in a spider covering all elements in the family of subsets nt*(𝒟).


## 3.2. The Spider Cover Algorithm

Our spider cover algorithmsp_cov(G,s,𝒟) is presented in next box Algorithm 2. The algorithm consists of successive iterations, based on the Algorithm max_sp. At each iteration a certain set of spiders is constructed in order to cover as many subsets in 𝒟 as possible. Namely, at each iteration, if Δ⊆𝒟 is the subfamily of subsets not covered yet, the algorithm seeks for the minimum number w for which the algorithm max_sp(Hw,z,nw(Δ)) returns a spider centered in z that covers at least half of the subsets in nw(Δ). The minimum number w can be obtained by applying the algorithm max_sp(Hw,z,nw(Δ)) in a binary search fashion, with w in the range [1,|Δ|]. Thereafter, via Lemma 3.1, one obtains w spiders in G from the “big” spider in Hw.Algorithm 2:The algorithm for the Spider Cover Problem on G, s, and 𝒟.
Algorithm  sp_cov(G,s,𝒟)
SetΔ=𝒟   [Family of groups that need to be covered]
SetS=∅, w¯=0
Repeat
(i) Compute the minimum integerw (with 1≤w≤|Δ|) such that the algorithm
max_sp (Hw,z,nw(Δ)) outputs a spider S¯ in Hw reaching a set X for which
C(X)=|{D∈nw(Δ):D∩X≠∅}|≥|nw(Δ)|/2=|Δ|/2
(ii) From the spiderS¯ in Hw obtain (via Lemma  4) w new spiders in G that cover
at least |Δ|/2 elements of Δ
(iii) LetΔ be the new family of uncovered subsets, put in 𝒮 the new w spiders,
set w¯=w¯+w.
Until  Δ=∅.
Output:  𝒮 and w¯.The total number of used spidersw¯ will be the sum of the number of spiders used at each iteration.We show now that the number of spiders returned by the algorithmsp_cov(G,s,𝒟) is at most log2|𝒟|+1 times the optimal number of spiders necessary for the given instance 〈G,s,𝒟〉 of the Spider Cover Problem.Theorem 3.3.
The number of spiders returned by the algorithmsp_cov(G,s,𝒟) is w¯≤w*(log2|𝒟|+1), where w* is the number of spiders in an optimal solution for the given instance 〈G,s,𝒟〉 of the problem.Proof.
Consider any iteration of the cycle. The algorithm computes the minimum integerw such that max_sp(Hw,z,nw(Δ)) outputs a spider covering at least |Δ|/2 elements of the family nw(Δ). This means that the current size of the family of yet uncovered groups is decreased of at least 1/2 of its value during each iteration. Hence, the algorithm sp_cov(G,s,𝒟) consists of at most log|𝒟|+1 iterations.
Moreover, at each iteration the minimum integerw computed by the algorithm is upperbounded by w*. In fact, it is certain that in Hw* there exists a spider reaching |Δ| elements of nw*(𝒟), for any Δ⊆𝒟, and the algorithm max_sp(Hw*,z,nw*(Δ)) is guaranteed to find a spider that covers at least |Δ|/2 elements of nw*(Δ).
We can then conclude that the total number of spidersw¯ used by sp_cov(G,s,𝒟), which is the sum of all the values obtained at the various iterations, is upperbounded by w*(log2|𝒟|+1).


## 4. Final Comments

We have provided a general framework for covering problems and shown that several seemingly different problems naturally fit in our scenario. We have given approximation algorithms with best possible approximation ratios, under widely believed computational complexity assumptions. We would like to point out that we can easily extend our results to undirected graphs or to spiders defined as a collection of vertex disjoint paths sharing only a common vertex, using standard tricks.In case the graphG=(V,E) is undirected, we can consider the corresponding directed symmetric graph G'=(V,E') where E' contains the pair of arcs (x,y) and (y,x) if and only if x and y are neighbors in G. One must only be careful in the case in which one could get a spider containing both the opposite arcs, say (x,y) and (y,x), corresponding to one edge of G. However, if two branches of a spider are of the form P1,x,y,P2 and Q1,y,x,Q2, one can modify the spider so to contain P1,x,Q2 and Q1,y,P2. This implies that we can always get spiders in G with edge disjoint branches. We can then apply the result of the present paper to the directed graph G'=(V,E').In case we are interested in spiders made of vertex disjoint paths sharing a single vertex, we can obtain the same results as for arc-disjoint spiders by substituting inG each node v with a pair of nodes v' and v′′, connected by the arc (v',v′′). Moreover, each arc entering v in G now enters v', and each arc leaving v in G now leaves v′′.



---

*Source: 347430-2012-11-28.xml*