The Image Containment Problem and some classes of polynomial instances

The image containment problem (ICP) is a minimum cost design problem concerning the containment of particular polyhedra, called zonotopes, that are images of boxes through linear transformations. The ICP is NP-hard. Here we study a family of nontrivial ICP instances, called worst case demand (WCD) instances. We prove that such instances can be recognized and solved in polynomial time via linear programming. Then we characterize the classes of instances that are WCD independently on the choice of the cost vector (structurally worst case demand classes (SWCD)) and we show that recognizing whether a class of instances is SWCD is a coNP-complete problem. Finally, we describe two families of SWCD classes that are interesting from an applicative point of view: the classes defined by the incidence matrices of particular directed graphs and those defined by pre-Leontief matrices.