  Various real-world problems consist of partitioning a set of locations into
disjoint subsets, each subset spread in a way that it covers the whole set with
a certain radius. Given a finite set S, a metric d, and a radius r, define a
subset (of S) S' to be an r-cover if and only if forall s in S there exists s'
in S' such that d(s,s') is less or equal to r. We examine the problem of
determining whether there exist m disjoint r-covers, naming it the Solidarity
Cover Problem (SCP). We consider as well the related optimization problems of
maximizing the number of r-covers, referred to as the partition size, and
minimizing the radius. We analyze the relation between the SCP and a graph
problem known as the Domatic Number Problem (DNP), both hard problems in the
general case. We show that the SCP is hard already in the Euclidean 2D setting,
implying hardness of the DNP already in the unit-disc-graph setting. As far as
we know, the latter is a result yet to be shown. We use the tight approximation
bound of (1-o(1))/ln(n) for the DNP's general case, shown by U.Feige,
M.Halld'orsson, G.Kortsarz, and A.Srinivasan (SIAM Journal on computing, 2002),
to deduce the same bound for partition-size approximation of the SCP in the
Euclidean space setting. We show an upper bound of 3 and lower bounds of 2 and
sqrt(2) for approximating the minimal radius in different settings of the SCP.
Lastly, in the Euclidean 2D setting we provide a general
bicriteria-approximation scheme which allows a range of possibilities for
trading the optimality of the radius in return for better approximation of the
partition size and vice versa. We demonstrate a usage of the scheme which
achieves an approximation of (1/16,2) for the partition size and radius
respectively.
