4
$\begingroup$

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$.

$\endgroup$
  • 1
    $\begingroup$ I am not sure a reduction exists. The colored version of your problem is potentially harder. I am guessing, naturally... $\endgroup$ – Sariel Har-Peled Jan 15 '14 at 21:55
  • $\begingroup$ @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. $\endgroup$ – Erel Segal-Halevi Jan 16 '14 at 19:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.