%0 Journal Article
%T Spider Covers and Their Applications
%A Filomena De Santis
%A Luisa Gargano
%A Mikael Hammar
%A Alberto Negro
%A Ugo Vaccaro
%J ISRN Discrete Mathematics
%D 2012
%R 10.5402/2012/347430
%X 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 graph , a distinguished vertex , 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 -approximation algorithm for the Spider Cover Problem. 1. Introduction Given a digraph and a vertex , a spider centered at is a subgraph of consisting of arc-disjoint paths sharing the initial vertex and ending into pairwise distinct vertices. The vertex is called the center of the spider. The endpoints of the paths composing the spider ¡ªother than the center ¡ªare called the terminals of the spider. In other words, a spider is a subdivision of , where is the number of terminals. Given a spider , we say that reaches a vertex if is a terminal of ; we say that the spider covers a subset of vertices if reaches at least a vertex in . In this paper we consider the approximability of the following problems. Maximum Spider Problem (MSP) We are given a digraph , a distinguished node , and a family of subsets of vertices. The objective is to find a spider centered at such that the number of subsets covered by is maximum among all possible spiders centered at . 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 digraph , a distinguished vertex , and a family of subsets of vertices. The goal is to find a minimum cardinality collection of spiders centered at such that each subset 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
%U http://www.hindawi.com/journals/isrn.discrete.mathematics/2012/347430/