Recently in a contest I came across this question :

"Given *N* circles, defined by their *x* co-ordinate, *y* co-ordinate and radius *r*, remove the minimum number of circles such that the remaining circles are non intersecting. Touching a circle is also considered as intersecting."

**Constraints**

1 ≤ *N* ≤ 1000

0 ≤ *abs*(*X*), *abs*(*Y*), *abs*(*R*) ≤ 1000

The setter solution used a greedy solution (to remove the circle with maximum intersections everytime till all remaining are non intersecting), but this fails on a very simple test case.

Here, the greedy solution gives answer as 4, but we can do it by removing 3 circles also.

I could convert this problem into a graph (edges depict intersection between the vertices) for which we need the minimum vertex cover, which doesn't have a polynomial time solution. Can we convert it into some other problem and solve efficiently? What's the best complexity you can come up with ?

Isn't it just maximal independent subset problem? It can be solved in O(N*M) but, usually it gets bit faster if you start with lucky greedy starting matching.

Isn't the minimum vertex cover a complement problem of maximal independent set?

My bad, I misunderstood. It think it is still NP-hard because:[https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Independent_sets_in_geometric_intersection_graphs](https://en.wikipedia.org/wiki/Independent_set_(graph_theory)#Independent_sets_in_geometric_intersection_graphs). "Geometric" part says that it is still NP-hard there