Find set of non-overlapping rectangles in a 2D grid

Question

I have a $n \times m$ rectangular grid of cells, and a set $R$ of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.)

I want to find a subset $S$ of rectangles, so that $S \subseteq R$, so that no two rectangles in $S$ overlap, and so that $S$ is as large as possible. (Alternatively, you can think of this as finding a maximum independent set in a graph where we have one vertex per rectangle, and an edge between two rectangles if they overlap.)

Can this problem be solved in polynomial time? Is it NP-hard?

I can see how to solve the one-dimensional analog (maximum set of non-overlapping intervals) in polynomial time using dynamic programming, but that algorithm doesn't seem to extend to this case. Wikipedia calls this the maximum disjoint set problem and says that when the set of shapes is arbitrary, the problem is NP-hard, but it doesn't discuss the specific case of axis-aligned rectangles with integer coordinates. That makes me suspect this problem might be NP-hard, but I haven't found a reference or proof of that.

Answer 1

The problem you state is shown to be NP-Hard [1, 2]. However, there is an $O(\log \log n)$ approximation algorithm for the problem [3].

[1] H. Imai, T. Asano. Finding the Connected Components and a Maximum Clique of an Intersection Graph of Rectangles in the Plane. Journal of Algorithms 4(4): 310-323, 1983.

[2] R.J. Fowler, M.S. Paterson and S.L. Tanimoto, Optimal packing and covering in the plane are NPcomplete. Information Processing Letter. 12 3 (1981), pp. 133137.

[3] Parinya Chalermsook, Julia Chuzhoy: Maximum independent set of rectangles. SODA 2009: 892-901