4
$\begingroup$

I am interested in the following problem:

There are n collections of M axis-parallel squares (not necessarily disjoint).
Pick a single square from each collection,
     such that the n selected squares are pairwise interior-disjoint.

One way to approach the problem is to discretize the squares such that each square becomes a set of small squares. This makes the problem an instance of the following set packing problem:

There are n collections of sets (not necessarily disjoint).
Pick a single set from each collection, 
     such that the n selected sets are pairwise disjoint.

The set packing problem is equivalent to the independent set problem, and both are known to be NP-complete.

My question is: does the fact that the sets in this case are discretizations of axis-parallel squares make the problem any easier?

Particularly, is it possible to solve the problem, or at least approximate it to a constant factor, in time polynomial in $n$ (the number of collections), assuming $M$ is constant?

Improve this question
$\endgroup$
0
3
$\begingroup$

I think your problem is NP-complete already for M=3, as there is a quite straight-forward reduction to it from 3SAT. Just for each variable xi, make a pair of squares, truei and falsei. For a clause Cj, make a pair of squares for each of its literals, e.g., Aj1, Bj1, Aj2, Bj2, Aj3, Bj3. Let Aj1 intersect the respective square of the variable (e.g., truei) (but disjoint from any other similar clause-squares intersecting it), while the Bj1, Bj2 and Bj3 are put somewhere in a disjoint way. Finally, for each clause we have a collection of three squares, which is also Bj1, Bj2 and Bj3.

Improve this answer
$\endgroup$
7
  • 1
    $\begingroup$ I don't see why you need a pair of squares for each of the literals of a clause. Can't you simply have a set containing 2 big squares for each variable, and a set containing three little squares for each clause? The little square you choose for each clause will force the variable to take on the correct value. $\endgroup$
    – Peter Shor
    Dec 24 '13 at 14:20
  • $\begingroup$ @Peter: Of course, you are correct. First I wanted to prove it with M=2, but then I thought it does not matter, so I picked M=3 and simplified things, apparently not enough. $\endgroup$
    – domotorp
    Dec 24 '13 at 18:22
  • 1
    $\begingroup$ Can't M=2 can be solved in polynomial time? The relations between the squares are pairwise, so when M=2, all the constraints are pairwise, yielding an instance of 2-SAT, which is polynomial. $\endgroup$
    – Peter Shor
    Dec 24 '13 at 18:43
  • $\begingroup$ Of course, again you are correct. That explains why I did not manage with M=2... $\endgroup$
    – domotorp
    Dec 24 '13 at 20:34
  • $\begingroup$ Thanks! What about approximation to a constant factor? The general set packing problem cannot be approximated to a constant factor in polynomial time (unless $P=NP$). Does it become possible when the sets are squares? $\endgroup$
    – Erel Segal-Halevi
    Dec 25 '13 at 16:00

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.