2
$\begingroup$

I have this problem:

Given a finite set of rectangles R, and a rectangle P, show that the problem of fitting R's rectangles inside P so that no two rectangles of R overlap and all their sides are parallel to P's respective sides, is NP-complete.

I have proved that it belongs to NP using the verifier method, but I'm struggling to reduce to SAT to show that it is NP-hard as well

Improve this question
$\endgroup$
2
  • $\begingroup$ SAT might be too abstract to encode into rectangles. You might find a more suitable problem, for example partition $\endgroup$ Commented Jan 23, 2025 at 18:44
  • 2
    $\begingroup$ the problem is that in my course, we haven't been taught about partition, so I am not totally sure I can use it without proving its NP-complete as well. The only ones I know for sure we can use as is are n-SAT, Hamiltonian Path, Vertex Cover and Clique $\endgroup$ Commented Jan 23, 2025 at 19:31

1 Answer 1

Reset to default
2
$\begingroup$

You can show it's NP-hard by doing 5 reductions from 3SAT ... (if this's your homework then this's probably not what you want, at least reading the last reduction may give you some inspiration though. You're welcome to self-answer if you figure out a short reduction) $$ 3SAT\le_p3DimentionalMatching\le_p ABCDPartition\le_p 4Partition\\ \le_p 3Partition\le_pRectanglePacking $$

$3SAT\le_p3DimentionalMatching$ : This's a long one, in the book "algorithm design" by Jon and Eva 8.6 Partitioning Problems.

$3DimentionalMatching \le_p ABCDPartition\le_p 4Partition \le_p 3Partition$ : see wiki (section: proofs)

$3Partition\le_p RectanglePacking$ : This one is nice and simple, see wiki (section: Packing different rectangles in a given rectangle).

Improve this answer
$\endgroup$
3
  • $\begingroup$ I thought maybe I could use SUBSET SUM also, construct a rectangle P with dimensions (TARGET SUM)x1 and if I find a subset such that SUM(elements of set) == TARGET SUM, I construct a set of rectangles R with dimensions (i-th element of subset)x1 $\endgroup$ Commented Jan 25, 2025 at 11:05
  • $\begingroup$ @ManosMastronikolas yeah you can give a try, given an instance of subset sum $(S,T)$ convert it to an instance of rectangle packing $(P,\mathcal R)$ in polynomial time such that there's a way to fit all rectangles of $\mathcal R$ into $P$ iff there's a subset of $S$ that sums to $T$. $\endgroup$ Commented Jan 26, 2025 at 2:17
  • $\begingroup$ @ManosMastronikolas just note that you cannot $\bf first$ find the subset that sum to $T$ $\bf then$ construct the rectangles because it's not known it can be done in polynomial time. $\endgroup$ Commented Jan 26, 2025 at 2:19

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.