Spider Covers and Their Applications

Abstract EN

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 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 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.