Minimum Membership Covering and Hitting

Abstract

Set cover is a well-studied problem with application in many fields. A well-known variation of this problem is the Minimum Membership Set Cover problem. In this 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. In this 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 variations 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 at least one boundary edge (top or bottom) with one of the input horizontal lines). For each of these problems either we prove NP-hardness or design a polynomial-time algorithm. More precisely, 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. We also provide approximation algorithms for some of the problems. In addition, we study a generalized version of the Minimum Membership Hitting Set problem.

J.S.B. Mitchell—Partially supported by the National Science Foundation (CCF-1526406) and the US-Israel Binational Science Foundation (project 2016116).

S. Pandit—Partially supported by the Indo-US Science & Technology Forum (IUSSTF) under the SERB Indo-US Postdoctoral Fellowship scheme with grant number 2017/94, Department of Science and Technology, Government of India.

1 Introduction

The set cover problem is one of the fundamental problems in computer science and combinatorial optimization. This problem and its many variations play an important role in modelling various problems arising in practical scenarios. One of its variations is the problem, which is defined in a geometric setting as follows.

A related problem that is “dual” to the MMSC problem is the problem, defined as follows.

In addition to the above two problems, we consider a version of the MMHS problem, the problem, where, instead of a point set and a object set, we are given two sets R (“red”) and B (“blue”) of objects. The objective is to stab (intersect) all of the objects in B using a subset $R'\subseteq R$ such that the maximum number of red objects in $R'$ hitting any single object in B is minimized.

1.1 Previous Work

The standard set cover problem is NP-hard. A simple greedy heuristic gives a $O(\log n)$-factor approximation, and it is NP-hard to compute an approximation better than logarithmic [11]. The Minimum Membership Set Cover variation was first introduced by Kuhn et al. [6]. They showed that the problem cannot be approximated better than $O(\log n)$ and gave an approximation factor that matches this lower bound. Erlebach and van Leeuwen [3] considered the geometric variation of the problem, proving that for unit squares and unit disks the problem is NP-hard and there does not exist a polynomial-time factor 2 approximation algorithm, unless P = NP. Further, for unit squares, they provided a factor 5 approximation for the case in which the optimum objective value is bounded by a constant. Recently, Nandy et al. [9] reconsidered the same problem and gave polynomial-time algorithms for both unweighted and weighted intervals on the real line. Recently, Narayanaswamy et al. [10], considered the problem of hitting a set of horizontal segments with vertical segments while minimizing the number of times a vertical segment is hit by the chosen horizontal segments. They showed that this problem is NP-hard and cannot be approximated better than factor 2. Further, if the segments are of unbounded length (i.e., they are lines), then it can be solved in polynomial time (see also [2] for this algorithm and some generalizations of this problem).

1.2 Our Contributions: Overview

• Minimum Membership Set Cover ( MMSC ) problem

  We give a polynomial-time algorithm for deciding if there exists a cover with depth one for the MMSC problem with objects that are rectangles anchored on a horizontal line. In contrast, we show that if the objects are rectangles that intersect a horizontal line (versus that are anchored, sharing a side with a horizontal line), the MMSC problem is NP-hard. We also prove NP-hardness for the cases of objects that are axis-parallel strips or rectangles anchored on two horizontal lines.

• Minimum Membership Hitting Set ( MMHS ) problem

  We give a polynomial-time algorithm for deciding if there exists a hitting set with depth one for the MMHS problem with objects that are rectangles anchored on a horizontal line. In contrast, we show that if the objects are rectangles that intersect a horizontal line, the MMHS problem is NP-hard. We also prove NP-hardness for the cases of objects that are axis-parallel strips or rectangles anchored on two horizontal lines.

• Generalized Minimum Membership Hitting Set ( GMMHS ) problem

  We show that GMMHS, with objects R, B given as horizontal/vertical line segments, is NP-hard; even deciding if a solution exists with depth one is NP-complete. We also give a 5-approximation algorithm if the optimal objective function is bounded by a constant.

Equivalence of MMSC and MMHS with Unit Disks/Squares. There is a connection (equivalence) between the MMSC and MMHS problems where the input objects are either unit disks or unit squares. Consider the case of unit squares. Given an instance $C=(P,T)$ of the MMSC problem, with a set P of points and a set T of unit squares, we consider a “dual” instance, H, of a MMHS problem whose regions are specified by the set of unit squares centered on the points $p\in P$, and whose points are specified as the centerpoints of the squares $t\in T$. We then note that determining a solution to the MMSC problem C is equivalent to determining a solution to the MMHS problem H. Thus, we conclude, by applying the results in [3, 9]: The MMHS problem is NP-complete with unit squares and unit disks and there exists a 5-approximation for the MMHS problem with unit squares where the optimal objective value is bounded by a constant.

1.3 Definitions and Notations

In a 3SAT problem we are give a CNF formula $\phi$ with n variables $\mathcal{X}=x_1,x_2,\ldots ,x_n$ and m clauses $\mathcal{C}= \{C_1,C_2, \ldots , C_m\}$ where each clause is a disjunction of exactly 3 literals, and the objective is to decide whether there is a truth assignment to variables such that $\phi$ is satisfiable. This problem is known to be NP-complete [4]. In a planar version of this problem, each variable or clause represents a vertex and there is an edge between a variable vertex and a clause vertex if and only if the corresponding clause contains the corresponding literal. Finally, the resulting bipartite graph is planar. This problem is called the Planar-3SAT problem and Lichtenstein [7] proved that this problem is also NP-complete. Later on, Knuth and Raghunathan [5] showed that every Planar-3SAT problem can be represented using the following rectilinear representation. The variables are placed on a horizontal line and the clauses containing 3 legs each connecting those variables either from above or below the horizontal line such that no two clause legs intersect. This problem is called the Rectilinear-Planar-3SAT problem and is also NP-complete [5]. A Positive-1-in-3SAT problem is a 3SAT problem, however the objective is different: Here, the objective is to decide whether there is a truth assignment to the variables such that exactly one literal per clause is true. Schaefer [12] proved that this problem is NP-complete. This problem can be represented using the rectilinear representation as defined above; we refer to it as the Rectilinear-Positive-Planar-1-in-3SAT problem (see Fig. 1). Surprisingly, Mulzer and Rote [8] proved that it is also NP-complete. We now define some terminology. Let $\mathcal{C}_{above} \subseteq \mathcal{C}$ be the set of clauses in a PP1in3SAT formula $\phi$ that connect to the variables from above. Similarly, let $\mathcal{C}_{below}\subseteq \mathcal{C}$ be the set of clauses that connect to the variables from below. For each variable $x_i$, $1\le i\le n$, we order the clauses in $\mathcal{C}_{above}$ left to right that connect $x_i$. Let $C_\ell \in \mathcal{C}_{above}$ be a clause containing the three variables $x_i$, $x_j$, and $x_k$. Then, according to the ordering defined above, we assume that $C_\ell$ is the $\ell _1$-, $\ell _2$-, and $\ell _3$-th clause for the variables $x_i$, $x_j$, and $x_k$, respectively. For example, the clause $C_3$ is a 3-rd, 1-st, and 1-st clause for the variables $x_3$, $x_4$, and $x_5$, respectively, in the PP1in3SAT instance in Fig. 1. We also say that the clause $C_\ell$ connects to $x_i$ by left, to $x_j$ by middle, and to $x_k$ by right legs.

Fig. 1.

Representation of a Rectilinear-Positive-Planar-1-in-3SAT problem.

2 Minimum Membership Set Cover Problem

2.1 Rectangles Anchored on a Horizontal Line

In polynomial time, one can decide if there exists a cover of depth one for the MMSC problem with rectangles anchored on a horizontal line from one side (MMSCRAHL), as follows. Let the weight of a rectangle be the number of points it contains. Now, apply the algorithm of [1] to compute a maximum weight independent set of rectangles (no two of them share an input point). Then, to see if there is a cover of points having depth exactly 1, check if the total weight of the independent set is equal to the number of input points.

2.2 Axis-Parallel Strips

In this section we prove that the MMSC problem with axis-parallel strips (MMSCS) is NP-hard. We give a reduction from the Positive-1-in-3SAT (P1in3SAT) problem (see Sect. 1.3 for the definition). Let $\phi$ be a P1in3SAT formula. We generate an instance Z(S, P) of the MMSCS problem from $\phi$ in the following way, where S is a set of strips and P is a set of points.

Variable Gadget: For variable $x_i$, the gadget consists of one vertical strip $v_i$, one horizontal strip $h_i$, and a point $p_i$. The point is covered by both $v_i$ and $h_i$ (see Fig. 2). Clearly, either $v_i$ or $h_i$ will cover $p_i$ with depth one. We assume that choosing $h_i$ makes $x_i$ true, while choosing $v_i$ makes $x_i$ false.

Overall Structure: We place the variable gadgets (points) along a diagonal line. For each clause we take a vertical bounded . The clause gadgets are placed sequentially one by one to the right of the variable gadgets, and each gadget is confined to its corresponding region. Between two consecutive variable horizontal strips there is an , where we place some points corresponding to the clauses.

Clause Gadget: Let $C_\ell = (x_i\vee x_j \vee x_k)$ be a clause. For this clause, we take 5 points $p^\ell _i, p^\ell _j, p^\ell _k, p^\ell _1, p^\ell _2$ and 4 vertical strips $q^\ell , r^\ell , s^\ell , t^\ell$ (see Fig. 2). The points $p^\ell _i$, $p^\ell _j$, and $p^\ell _k$ are corresponding to the variables $x_i$, $x_j$ and $x_k$ respectively and are placed inside the strips $h_i$, $h_j$, and $h_k$ respectively. The other two points $p^\ell _1$ and $p^\ell _2$ are placed in any empty space between the variable horizontal strips of $x_i, x_j$ (i.e., between $h_i$ and $h_j$) and $x_j,x_k$ (i.e., between $h_j$ and $h_k$) respectively. Points $\{p^\ell _i,p^\ell _1\}$ are contained in $q^\ell$. Similarly, $\{p^\ell _1,p^\ell _j\}$, $\{p^\ell _j,p^\ell _2\}$, and $\{p^\ell _2,p^\ell _k\}$ are contained in $r^\ell$, $s^\ell$, and $t^\ell$, respectively. These 5 points and 4 rectangles are strictly contained inside the vertical region of $C_\ell$ (Fig. 2).

Fig. 2.

Gadgets of variables $x_i$, $x_j$, $x_k$, and clause $C_\ell$ and their interaction.

Theorem 1

The MMSCS problem is NP-hard.

Proof

We prove that, $\phi$ is satisfiable (i.e., at least one literal is true per clause) if and only if Z(P, S) has a solution of depth one. Assume that $\phi$ has a satisfying assignment. If $x_i$ is true, take $h_i$; otherwise, take $v_i$. Now, for each clause, exactly one of $p_i^\ell ,p_j^\ell ,p_k^\ell$ is covered by the solution. Hence, the remaining 4 points are covered by exactly two strips with depth one.

On the other hand, assume that there is a cover of the points with depth one. Now, for each variable gadget, to cover $p_i$ we need one of the two strips $h_i$ or $v_i$. We set variable $x_i$ to be true if $h_i$ is in the solution; otherwise, we set $x_i$ to be false. Now consider any clause $C_\ell$. Since the depth of the solution (indeed a cover of all points) is one, exactly one of $p_i^\ell ,p_j^\ell ,p_k^\ell$ corresponding to $C_\ell$ is covered by a variable horizontal strip. We set this variable to be true. Hence, exactly one literal per clause is true in $\phi$.    $\square$

Corollary 1

The MMSC problem with rectangles anchored on two orthogonal lines (MMSCRATOL) is NP-hard. (Take a vertical and a horizontal line both at $-\infty$ to restrict the axis-parallel strips.)

2.3 Rectangles Intersecting a Horizontal Line

In this section we prove that the MMSC problem with rectangles intersecting a horizontal line (MMSCRIHL) is NP-hard. The reduction is from the PP1in3SAT problem [8]. From an instance $\phi$ of the PP1in3SAT problem, we generate an instance Z, where the rectangles in Z intersect a horizontal line L.

Variable Gadget: The gadget for the variable $x_i$ consists of 12m rectangles $\{1,2,\ldots ,12m\}$ and $12m-1$ points $\{p_1,p_2,\ldots ,p_{12m-1}\}$ (see Fig. 3(a)). The points are along the top edge of the rectangles. The 1-st and the 12m-th rectangles contain the points $p_1$ and $p_{12m-1}$, respectively, and the j-th rectangle contains the $p_{j-1}$-th and $p_j$-th points, for $2 \le j \le 12m-1$. We note that the first 6m rectangles $\{1,2,\ldots ,6m\}$ are responsible for the clauses in $\mathcal{C}_{above}$, whereas the next 6m rectangles $\{6m+1,6m2,\ldots ,12m\}$ are responsible for the clauses in $\mathcal{C}_{below}$. All of the rectangles are intersecting a horizontal line L. Now, in order to cover all of the points while minimizing the depth, we have only two distinct optimal solutions: Either all even-numbered or all odd-numbered rectangles with depth exactly one. This gives the truth value of the variable $x_i$.

Fig. 3.

(a) A variable gadget. (b) Position of the clause gadgets.

Clause Gadget: We first modify the PP1in3SAT problem in the following way. Note that the variables of $\phi$ are placed on a horizontal line ($y=0$). We move the variables vertically up such that they are placed on a horizontal line $y=m+1$ (above the y-values of all the clauses in $\mathcal{C}_{above}$) (see Fig. 4). The clauses in $\mathcal{C}_{above}$ are placed above L and below the line $y=m+1$ while connecting the same set of variables as before. Note that these clauses now connect the variables from below. On the contrary, the clauses in $\mathcal{C}_{below}$ are placed below L and still connect to the same set of variables from below.

Let us now consider the set $\mathcal{C}_{above}$ of clauses. Notice that, in the definition of the PP1in3SAT problem these clauses can be ordered in increasing y-direction (see Fig. 1). Here we reverse the order of the clauses (see Fig. 3(b)). Now for each clause $C\in \mathcal{C}_{above}$ we take a whose top boundary is the segment of C in the modified construction. The bottom boundary of the box touches the line L. Each box has a thin strip along the top edge of that box, called the of that clause. Similarly, we reverse the order of the clauses in $\mathcal{C}_{below}$ and for each clause C we take a box whose bottom boundary is the segment of C in the modified construction. The top boundary of the box touches the line L. Now here the tape is along the bottom boundary of each box.

Let $C_\ell = (x_i\vee x_j \vee x_k)$ be a clause in $\mathcal{C}_{above}$. We say that $x_i$ is a , $x_j$ is a , and $x_k$ is a variable for $C_\ell$. We take 5 points; point $p^\ell _i$ corresponding to $x_i$, points $p^\ell _j, q^\ell _j, r^\ell _j$ corresponding to $x_j$, and point $p^\ell _k$ corresponding to $x_k$; and 4 rectangles $s^\ell _1, s^\ell _2, s^\ell _3, s^\ell _4$. The rectangle $s^\ell _1$ covers the points $\{p^\ell _i, p^\ell _j\}$, $s^\ell _2$ covers the points $\{p^\ell _i, q^\ell _j\}$, $s^\ell _3$ covers the points $\{p^\ell _j, p^\ell _k\}$, and $s^\ell _4$ covers the points $\{r^\ell _j, p^\ell _k\}$ (see Fig. 4). The rectangles are placed inside the box and the points are placed inside the tape of $C_\ell$.

Variable and Clause Interaction: We now describe the placement of the clause rectangles and points with respect to the variable rectangles. Let $1,2,\ldots$ be the left to right order the clauses in $\mathcal{C}_{above}$ which connects to the variable $x_i$. In this order, assume that $C_\ell$ be the $\ell _1$-, $\ell _2$-, and $\ell _3$-th clause for the variables $x_i$, $x_j$, and $x_k$ respectively. Then we do the following.

• $\leadsto$ Since $x_i$ is a left variable in $C_\ell$, place the point $p_i^\ell$ inside the ($6\ell _1-2$)-th rectangle of the gadget of $x_i$.

• $\leadsto$ Since $x_j$ is a middle variable in $C_\ell$, place the point $p_j^\ell$ inside the ($6\ell _2-2$)-th rectangle of the gadget of $x_j$. Also place the point $q_j^\ell$ and $r_j^\ell$ inside the ($6k-3$)-th and ($6k-1$)-th rectangles of the gadget of $x_j$.

• $\leadsto$ Since $x_k$ is a right variable in $C_\ell$, place the point $p_k^\ell$ inside the ($6\ell _3-2$)-th rectangle of the gadget of $x_k$.

Fig. 4.

Interaction with the variable and clause gadgets. We demonstrate the interaction of $C_3$ and $C_4$ with the variables in the P1in3SAT instance in Fig. 1.

A similar construction can be made for the clauses in $\mathcal{C}_{below}$, but using the last 6m rectangles in the variables. See Fig. 4.

Theorem 2

The MMSCRIHL problem is NP-hard.

Proof

We prove that exactly one literal is true in every clause of $\phi$ if and only of the MMSCRIHL problem has a cover of depth 1. Assume that there is an assignment to the variables of $\phi$ that satisfies exactly one literal per clause. For a variable $x_i$, if it is true then select the even indexed rectangles otherwise select the odd indexed rectangles from the gadget of $x_i$. Let us consider a clause $C_\ell = (x_i\vee x_j \vee x_k)$. Since exactly one literal per clause is true, exactly one of $p_i^\ell$ or $p_j^\ell$, or $p_k^\ell$ is covered by a variable rectangle. Clearly, the remaining points in the clause gadget are covered by the clause rectangles with depth one.

In the reverse direction, assume that the MMSCRIHL problem has a cover of depth 1. To cover the points in a variable gadget and in order to make their depth 1, there are only two possibilities to select the rectangles. We set the variable $x_i$ to be true if all even indexed rectangles are selected from the gadget of $x_i$, otherwise set $x_i$ to be false. Now consider a clause $C_\ell = (x_i\vee x_j \vee x_k)$. Now in $C_\ell$, if more than one literal is true then the depth of a point in the gadget of $C_\ell$ will be more than 1. If the clause is not satisfiable then also either at least one point is not covered of there will be a point whose depth will be more than one. The only possibility is exactly one literal per clause is true. Hence, the theorem.     $\square$

2.4 Rectangles Anchored on Two Horizontal Lines

We prove that the MMSC problem with rectangles anchored on two horizontal lines (MMSCRATHL) is NP-hard by a reduction from PP1in3SAT problem [8].

Variable Gadget: For the variable gadget of $x_i$, we consider 12m points in two horizontal lines $l_1$ and $l_2$ each contains 6m points. We also consider 12m rectangles such that each rectangles i covers exactly two points $p_i$ and $p_{i+1}$, for $1\le i\le 12m-1$ and the rectangles 12m covers points $p_{12m}$ and $p_1$ (see Fig. 5(a)). Rectangles $1,2,\ldots ,6m$ are anchored on line $l_1$ and the remaining Rectangles are anchored on line $l_2$. Now in order to cover all the points while minimizing the depth, we have only two different optimal solutions. Either all even numbered or all odd numbered rectangles with depth exactly 1. This gives the truth value of the variable $x_i$.

Clause Gadget: We first consider the set $\mathcal{C}_{below}$ of clauses in $\phi$. These clauses can be ordered in decreasing y-direction (see Fig. 1). Now for each clause $C\in \mathcal{C}_{below}$ we take a whose top boundary is the segment of C. The bottom boundary of the box touches the line $l_1$. Each box has a thin strip along the top edge of that box, called the of that clause. Similarly, we construct the boxes and tapes for the clauses for $\mathcal{C}_{above}$. See Fig. 5(b).

Fig. 5.

(a) A variable gadget. (b) Position of the clause gadgets.

The placement of the clause points and rectangles is similar to the placement of the clause points and rectangles described in Sect. 2.3. The clause structure is exactly the same as in Sect. 2.3. For a clause $C_\ell = (x_i\vee x_j \vee x_k)$ in $\mathcal{C}_{below}$ with $x_i$, $x_j$, and $x_k$ as , , and variable, we take 5 points; point $p^\ell _i$ corresponding to $x_i$, points $p^\ell _j, q^\ell _j, r^\ell _j$ corresponding to $x_j$, and point $p^\ell _k$ corresponding to $x_k$; and 4 rectangles $s^\ell _1, s^\ell _2, s^\ell _3, s^\ell _4$. The rectangle $s^\ell _1$ cover the points $\{p^\ell _i, p^\ell _j\}$, $s^\ell _2$ cover the points $\{p^\ell _i, q^\ell _j\}$, $s^\ell _3$ cover the points $\{p^\ell _j, p^\ell _k\}$, and $s^\ell _4$ cover the points $\{r^\ell _j, p^\ell _k\}$. The rectangles are placed inside the box and the points are placed inside the tape of $C_\ell$.

Variable and Clause Interaction: The interaction of the variables and the clauses is similar to that in Sect. 2.3, but now here we consider a clause $C\in \mathcal{C}_{below}$. As in the proof of Theorem 2, we conclude:

Theorem 3

The MMSCRATHL problem is NP-hard.

3 Minimum Membership Hitting Set Problem

3.1 Rectangles Anchored on a Horizontal Line

Similar to Sect. 2.1, in polynomial time, one can decide if there exists a hitting set of depth one for the MMHS problem with rectangles anchored on a horizontal line from one side (MMHSRAHL), as follows. Define the weight of a point as the number of rectangles it stabs. Now, apply the algorithm of [1] to compute a maximum weight set of points (no two of them share a rectangle). Then, to see if there is a hitting set of rectangles having depth exactly 1, check if the total weight of the points is equal to the number of rectangles.

3.2 Axis-Parallel Strips

We prove that the MMHS problem with axis-parallel strips (MMHSS) is NP-hard using a reduction from the P1in3SAT problem. We generate an instance Z(S, P) of the MMHSS problem from $\phi$, an instance of the P1in3SAT problem.

The gadget for a variable $x_i$ includes 2m horizontal strips $\{1,2,\ldots ,2m-1\}$ and 2m points $\{p_1,p_2,\ldots , p_{2m}\}$. The j-th strip contains the points $p_j$ and $p_{j+1}$, for $1\le j\le 2m-1$ (see Fig. 6(a)). The points are on a vertical line. However, we move some of the points to the right to some clause gadgets at later stage. It is observed that there are exactly two different sets of points, either all even indexed or all odd indexed, which stab all the strips with depth exactly 1. We stack the variable gadgets vertically from top to bottom.

The gadget for a clause $C_\ell$ is a vertical strip $v^\ell$. The clause gadgets are placed one after another to the right of the points corresponding to the variable gadgets.

For each variable, we order the clauses that contains it. Let $C_\ell$ be a clause that contains $x_i, x_j,x_k$, then according to this ordering we say that $C_\ell$ is a $\ell _1$-th, $\ell _2$-th, and $\ell _3$-th clause for $x_i, x_j$, and $x_k$ respectively. Now for the clause $C_\ell$ we move the three points $p_{2\ell _1}$, $p_{2\ell _2}$, and $p_{2\ell _3}$ in the vertical orientation from $x_i, x_j$, and $x_k$ respectively to inside $v^\ell$.

Fig. 6.

(a) Variable gadget. (b) Clause gadget and its interaction with variable gadgets.

Clearly, the number of strips and points is polynomial with respect to the number of variables and clauses in $\phi$. Hence the construction can be done in polynomial time. We now prove the following theorem.

Theorem 4

The MMHSS problem is NP-hard.

Proof

We prove that exactly one literal is true in each clause of $\phi$ if and only if Z has a hitting set with depth exactly 1. For variable $x_i$, we choose even indexed points if $x_i$ is true, else choose odd indexed points. This clearly stabs all variable strips with depth 1. Since exactly one literal is true in each clause of $\phi$, exactly one point will stab a clause strip. On the other hand assume that there is a hitting set of points with depth exactly 1. Now stabbing all the variable strips with depth 1 requires either all even or all odd indexed points. So we set $x_i$ to be true if even indexed points are selected, otherwise, set $x_i$ to be false. Since the depth of the hitting set is 1, exactly one point in a clause strip is selected.    $\square$

3.3 Rectangle Intersecting a Horizontal Line

We show that the MMHS problem with rectangles intersecting a horizontal line (MMHSRIHL) is NP-hard using a reduction from the PP1in3SAT problem.

The variable gadget is similar to the variable gadget defined in Sect. 3.2, but now the strips are vertical and they are intersecting a horizontal line. The clause gadget is similar to that in Sect. 2.3, but now, for each clause, the rectangular box of Sect. 2.3 is itself a rectangle. Next, using a process as in Sect. 3.2, we shift (vertically) points from the variable gadgets to these clause rectangles. Hence, as in the proof of Theorem 4, we conclude the following.

Theorem 5

The MMHSRIHL problem is NP-hard.

Similar to Theorem 5, we prove that the MMHSRATHL problem is NP-hard.

4 Generalized Minimum Membership Hitting Set

NP-Hardness: We prove that the GMMHS problem of stabbing horizontal unit segments by vertical unit segments (GMMHSUSeg) is NP-hard. The reduction is from the PP1in3SAT problem.

Fig. 7.

A variable gadget.

Variable Gadget: Each variable gadget consists of a and at most 2m , each corresponding to a clause leg that connects to a variable.

Variable Chain: Each variable chain consists of $8m+ 2$ unit horizontal segments $\{h_1,h_2,\ldots ,h_{8m+2}\}$ positioned like a rectangular fashion (see Fig. 7). The segments $\{h_1,h_2,\ldots ,h_{4m}\}$ are on a horizontal line and are responsible for connecting the clause chains to the variable chain from above. Similarly, the segments $\{h_{4m+2},h_{4m+3},\ldots ,h_{8m+1}\}$ are on another horizontal line and are responsible for connecting the clause chains to the variable chain from below.

Clause Chains: Let $C_\ell$ be a clause in $\mathcal{C}_{above}$ that connects the variables $x_i$, $x_j$, and $x_k$ through left, middle, and right legs respectively. Then for a left or middle, or right leg, we construct a or , or chain respectively. The left and middle chains are depicted in Fig. 8(a) and (b) respectively. The right chain is similar to the left chain but flipped vertically.

Let us consider a clause $C \in \mathcal{C}_{above}$ that is a $\ell$-th clause for the variable $x_i$. In the variable chain of $x_i$, we shift the $h_{4\ell -2}$-th segment slightly left and the $h_{4\ell -1}$-th segment slightly right (see Fig. 8(c)). Place the chain for C above these two segments such that $h'$ and $h_{4\ell -2}$ are stabbed by a vertical segment and $h''$ and $h_{4\ell -1}$ are stabbed by another vertical segment. Note that for each variable at most 2m chains are connected with its variable chain, at most m from either above or below. The variable chain and at most 2m left, middle, or right chains together form a big circular like arrangements of segments, called . Note that, this big-cycle contains an even number of both horizontal and vertical segments and along the cycle at most 2 consecutive horizontal segments are stabbed by a vertical segment. We now have the following observation.

Observation 1

For each variable gadget, there are two optimal solutions, either all red or all blue vertical segments each of size half of the total number of vertical segments present in a big-cycle.

Fig. 8.

(a) A left chain. (b) A middle chain. (c) Attaching a clause chain to a variable chain. (d) Clause gadget and connection with the three variable gadgets.

Clause Gadget: Let $C_\ell \in \mathcal{C}_{above}$ be a clause that contains $x_i$, $x_j$, and $x_k$. The gadget for $C_\ell$ is a single horizontal segment $h^\ell$. The position of $h^\ell$ with respect to the three chains corresponding to $x_i$, $x_j$, and $x_k$ is shown in Fig. 8(d).

This completes the construction. Note that this construction can be done in polynomial time with respect to the number of the variables and clauses in $\phi$. An argument similar to that in the proof of Theorem 4 leads to the following theorem.

Theorem 6

The GMMHSUSeg problem is NP-hard.

Approximation for the GMMHSUSeg  Problem: First we convert this problem to the MMHS problem with unit squares. Let H and V be given sets of unit horizontal and vertical segments. For each horizontal segment $h\in H$, take a unit square $t_h\in T$ such that the bottom boundary of $t_h$ coincides with h and for each vertical segment $v\in V$, take the top endpoint, $p_v\in P$ of v. Clearly, finding a set $V'\subseteq V$ that stabs all the horizontal segments in H while minimizing the number of times a segment in H is stabbed by segments in $V'$ is equivalent to finding a set of points $P'\subseteq P$ that stabs all the unit squares in T while minimizing the number of points in $P'$ that is contained in a unit square in T.

Because the GMMHSUSeg problem is NP-hard, in another way we can say that the MMHS problem with unit squares is also NP-hard. Since for unit squares the MMHS and MMSC problems are dual to each other, the result of [3] ensures the following theorem.

Theorem 1

There exists a 5-approximation for the GMMHSUSeg problem where the optimal objective value is bounded by a constant.