Minimum Membership Covering and Hitting

Abstract

Set Cover is a well-studied problem with application in many fields. A well-known variant of this problem is the Minimum Membership Set Cover problem: Given a set of points and a set of objects, the objective is to cover all points while minimizing the maximum number of objects that contain any one point. A dual of this problem is the Minimum Membership Hitting Set problem: Given a set of points and a set of objects, the objective is to stab all of the objects while minimizing the maximum number of points that an object contains. We study both of these variants in a geometric setting with various types of geometric objects in the plane, including axis-parallel�line segments, axis-parallel strips, rectangles that are anchored on a horizontal line from one side, rectangles that are stabbed by a horizontal line, and rectangles that are anchored on one of two horizontal lines (i.e., each rectangle shares its top or its bottom edge (or both) with one of the input horizontal lines). For each of these problems we either prove NP-hardness or we give a polynomial-time algorithm. In particular, we show that it is NP-complete to decide whether there exists a solution with depth exactly 1 for either the Minimum Membership Set Cover or the Minimum Membership Hitting Set problem. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.