# Maximum disjoint set: what is the actual approximation factor of the greedy algorithm?

Consider the problem of finding a maximum disjoint set - a maximum set of non-overlapping geometric shapes, from a given collection of candidates. This is an NP-complete problem, but in many cases, the following greedy algorithm yields a constant-factor approximation:

• For every candidate shape x, calculate its disjoint intersection number $DIN(x)$ = the largest number of disjoint shapes that intersect x.
• Select a candidate shape with a smallest DIN ($\arg \min_{x} DIN(x)$). Remove it and all the shapes it intersects.
• Continue until no more candidates remain.

The green disk intersects 5 other disks, but its DIN is 3 (the 3 red disks are disjoint). The topmost and bottommost red disks intersect 2 other disks, but they themselves intersect, so their DIN is 1. The yellow disks have a DIN of 2. The greedy algorithm thus selects the topmost or the bottommost red disk.

If the minimum DIN can be bounded by a constant, then the greedy algorithm is a polynomial constant-factor approximation.

For example, if all candidate shapes are unit disks, Marathe et al (1995) show that a disk with a DIN of at most 3 always exists: the leftmost disk (the disk with the smallest x coordinate) intersects at most 3 other disjoint disks. Therefore the greedy algorithm yields a 3-approximation because it obtains 1 disk for each (at most) 3 disks in the optimal solution.

Similarly, if all candidate shapes are disks of arbitrary size, the greedy algorithm yields a 5-approximation, because the smallest disk intersects at most 5 other disjoint disks, i.e. the minimum DIN is at most 5.

So far so good, but Are these factors of 3 and 5 tight? I am not sure.

Consider the figure above. Selecting the leftmost disk (green) will find a disjoint set of size 1, which is indeed a 3-approximation to the maximum disjoint set of size 3 (red), but, the greedy algorithm will not select the green disk - it will select the top/bottom red disk, whose DIN is 1. In this case the greedy algorithm will find the optimal solution.

I couldn't find a counter-example for general $n$, in which the greedy algorithm finds a disjoint set with $n$ unit disks while the maximum disjoint set has $3n$. Actually, I couldn't even construct a general counter-example in which the minimum DIN is indeed 3. The best I could come up with is the following, in which each unit disk intersects at most 2 other disjoint disks (i.e. the minimum DIN is 2). But even here, the greedy algorithm finds the optimal solution rather than a 2-approximation:

My questions are:

• What is the actual max min DIN in collections of unit-disks? Arbitrary-sized disks?
• What is the actual approximation factor of the greedy algorithm for collections of unit-disks? For arbitrary-sized disks? (this factor is at most as large as the max min DIN, but may be smaller).

UPDATE: For every k-tuple of shapes, $x_1,...,x_k$, define $DIN(x_1,...,x_k)$ = the largest number of disjoint shapes intersected by their union $x_1\cup...\cup x_k$. Define $minDIN_k$ as the minimum DIN of over all k-tuples of disjoint shapes.

For example, in Yury's answer below, $minDIN_1=3$, because every circle intersects 3 other circles. $minDIN_2=4$, because it is possible to select 2 disjoint circles, one from the outer circle and one from the inner circle, that together intersect only 4 other circles. For every $k$, $minDIN_k\leq k+2$.

I THINK that the approximation ratio of the greedy algorithm can be bounded by $\frac{minDIN_k}{k}$, because, for every $minDIN_k$ shapes in the optimal solution, we have at least $k$ shapes in the algorithm output. Is this correct?

EDIT: I am now reading the excellent book Research problems in discrete geometry. While I haven't found this exact problem, I found a problem that looks related. In section "2.5 Thin Packings with Many Neighbors", there are examples of circle packings in which each circle touchese 5 other circles. I wonder if such a packing can yield a configuration of circles with DIN = 5.

• It might be interesting to note that computing the DIN may be as hard as computing a maximum independent set itself. For example, in the case of disk graphs (rather than unit disk graphs) one could add a big disk intersecting all other objects in the arrangement; computing its DIN corresponds to computing a maximum independent set in the original arrangement. – Bart Jansen Jan 27 '14 at 11:35
• @BartJansen True, but the greedy algorithm actually doesn't need to calculate the DIN for every shape - it only needs a shape with the minimum DIN. Since the minimum DIN is at most 5 (in the case of arbitrary-sized disks), it only has to check all subsets with at most 6 disks, and see whether one of them is independent. This can be done in time $O(n^6)$ for each shape. – Erel Segal-Halevi Jan 27 '14 at 12:13
• For your last question - yes, it is correct. – domotorp Jan 31 '14 at 19:44