Spider covers and their applications (Q1935978)

Summary: We introduce two new combinatorial optimization problems: the \textsc{Maximum Spider} problem and the \textsc{Spider Cover} problem; we study their approximability and illustrate their applications. In these problems we are given a directed graph \(G = (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 \textit{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 \textsc{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 \textit{Maximum Spider} and \textsc{Spider Cover} problems by pointing out a variety of applications. We show that a natural greedy algorithm gives a 2-approximation algorithm for the \textit{Maximum Spider} problem and a \((\log|\mathcal D| + 1)\)-approximation algorithm for the \textsc{Spider Cover} problem.