# Reduction from a geometric decision problem to its maximization problem

I am interested in the following NP-complete decision problem:

Given n collections of M axis-parallel squares in the plane,
is it possible to pick a single representative from each collection,
such that all n representatives are pairwise disjoint?


I found several useful approximation algorithms to the following maximization problem:

Given n axis-parallel squares in the plane,
find the largest set of pairwise disjoint squares.


(see Timothy M. Chan and Sariel Har-Peled, 2013, for a recent survey of approximation algorithms for this and similar problems).

I am trying to use them for solving my original problem, but in order to get a better understanding of the relation between these two problems, I ask the following theoretical question:

Given an oracle that solves the maximum-disjoint-squares problem, how can it be used for solving the square-representative-decision problem?

NOTE 1: The two problems can be seen as special cases of the following set packing problems:

Decision problem:

Given n collections of M sets,
is it possible to pick a single representative from each collection,
such that all n representatives are pairwise disjoint?


Maximization problem:

Given n sets,
find the largest set of pairwise disjoint sets.


In this case, there is a simple reduction from the decision problem to the maximization problem: add a unique element $A_i$ to all sets in collection $i$, find the largest set of pairwise disjoint sets, and return "true" if the largest set has $n$ sets. Unfortunately this reduction doesn't work in the geometric scenario.

NOTE 2: Both the decision problem and the maximization problem can be solved with an oracle to the following problem:

Given n collections of M axis-parallel squares in the plane,
find the maximum number of disjoint representatives, one per collection.


For the decision problem, just check if the maximum is $n$. For the maximization problem, take $M=1$.

• I am not sure a reduction exists. The colored version of your problem is potentially harder. I am guessing, naturally... – Sariel Har-Peled Jan 15 '14 at 21:55
• @SarielHar-Peled Nice to meet one of the authors here :) The decision problem in the case of general sets is reducible to the maximization problem, so I thought this might be the case also for squares. Of course this is not certain. – Erel Segal-Halevi Jan 16 '14 at 19:31