Tight Approximation Bounds for Connectivity with a Color-Spanning Set

摘要

Given a set of points Q in the plane, define the r/2 -Disk Graph, Q(r), as a generalized version of the Unit Disk Graph: the vertices of the graph is Q and there is an edge between two points in Q iff the distance between them is at most r. In this paper, motivated by applications in wireless sensor networks, we study the following geometric problem of color-spanning sets: given n points with m colors in the plane, choosing m points P with distinct colors such that the r/2 -Disk Graph, P(r), is connected and r is minimized. When at most two points are of the same color ci (or, equivalently, when a color ci spans at most two points), we prove that the problem is NP-hard to approximate within a factor 3 - ε. And we present a tight factor-3 approximation for this problem. For the more general case when each color spans at most k points, we present a factor- (2k-1) approximation. Our solutions are based on the applications of the famous Hall's Marriage Theorem on bipartite graphs, which could be useful for other problems.