<p>I am interested in the following NP-complete decision problem:</p>

<pre><code>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?
</code></pre>

<p>I found several useful approximation algorithms to the following maximization problem:</p>

<pre><code>Given n axis-parallel squares in the plane, 
find the largest set of pairwise disjoint squares.
</code></pre>

<p>(see <a href="http://link.springer.com/article/10.1007/s00454-012-9417-5" rel="nofollow">Timothy M. Chan and Sariel Har-Peled, 2013</a>, for a recent survey of approximation algorithms for this and similar problems).</p>

<p>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:</p>

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

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

<p>Decision problem:</p>

<pre><code>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?
</code></pre>

<p>Maximization problem:</p>

<pre><code>Given n sets, 
find the largest set of pairwise disjoint sets.
</code></pre>

<p>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.</p>

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

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

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

CC BY-SA 3.0
2014-01-15T21:55:05.313Z
I am not sure a reduction exists. The colored version of your problem is potentially harder. I am guessing, naturally...
Sariel Har-Peled
CC BY-SA 3.0
2014-01-16T19:31:46.030Z
@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
<cg.comp-geom><oracles><packing>
Reduction from a geometric decision problem to its maximization problem
Erel Segal-Halevi
# Reduction from a geometric decision problem to its maximization problem

(Asked by: username_0 on 2013-12-31)

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

**Tags:** cg.comp-geom, oracles, packing

> **Comments:**
> **username_1**: I am not sure a reduction exists. The colored version of your problem is potentially harder. I am guessing, naturally...  
> **username_0**: @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.  

---

## 0 answers

