We consider the Minimum Coverage Kernel problem: given a set B of d-dimensional
boxes, find a subset of B of minimum size covering the same region as B. This
problem is NP-hard, but as for many NP-hard problems on graphs, the problem
becomes solvable in polynomial time under restrictions on the graph induced by
B. We con- sider various classes of graphs, show that Minimum Coverage Kernel
remains NP-hard even for severely restricted instances, and provide two
polynomial time approximation algorithms for this problem.