Optimal Box-in-a-Box-in-a-Boxing

Question

As inspired by this closely related problem, suppose I have $n$ cuboid boxes, all with arbitrary (possibly random) finite dimensions.

For any two boxes, $B_1$ with dimensions $w_1,h_1,d_1$, and $B_2$ with dimensions $w_2,h_2,d_2$, we suppose that $B_1$ can fit inside $B_2$ iff $w_1 \leq w_2$ and $h_1 \leq h_2$ and $d_1 \leq d_2$. (Assume the orientation of each box is fixed so that no rotations are allowed.)

We call a series of boxes packed one inside another (inside another...) a "group". Our objective is to pack our set of $n$ boxes into the fewest groups possible.

My questions are as follows:

1. Is this a known problem or a variant of a known problem, and if so, what is it called?

2. Does there exist (with proof) an algorithm polynomial in $n$ for determining a group-minimal packing of the boxes? If not, does there exist a proof (assuming $P \neq NP$) that no such algorithm is possible?

It is worth noting that the original problem is based on "book stacking" in two dimensions rather than three, hence if the answer depends on the number of dimensions $\geq 2$, I'd appreciate a heads-up.

Many thanks.

Answer 1

This can be done in polynomial time for any dimension.

Assume WLOG the boxes are distinct. Form a graph from the "fits inside" relation. This is a directed acyclic graph. Each group is a path in this graph, and we want to partition the vertices into as few paths as possible. This is exactly the problem of minimum path cover in directed acyclic graph. The Wikipedia page gives a reduction to Maximum Matching, which is polynomial time.

A small technicality is that a path cover might have paths reuse vertices and so fail to be a partition, but that's easy to fix by deleting repeated vertices from all but one path thanks to the fact that the graph represents a transitive relation.

Answer 2

As it turns out, several enterprising gentlemen discussing the original problem found a provably optimal $\mathcal{O}\left( n^2\right)$ algorithm, which can be generalized to the $p$-dimensional case, $p \geq 3$ via Dilworth's theorem. Hence this resolves question 2.

The question about whether this box-grouping problem or others similar to it have a formal name is still open.