Exact Multi-Covering Problems with Geometric Sets

Abstract

The b-Exact Multicover problem takes a universe U of n elements, a family $\mathcal {F}$ of m subsets of U, a function ${\textsf {dem}}: U \rightarrow \{1,\ldots ,b\}$ and a positive integer k, and decides whether there exists a subfamily(set cover) $\mathcal {F}^{\prime }$ of size at most k such that each element u ∈ U is covered by exactly dem(u) sets of $\mathcal {F}^{\prime }$. The b-Exact Coverage problem also takes the same input and decides whether there is a subfamily $\mathcal {F}^{\prime } \subseteq \mathcal {F}$ such that there are at least k elements that satisfy the following property: u ∈ U is covered by exactly dem(u) sets of $\mathcal {F}^{\prime }$. Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by k, b-Exact Multicover is W[1]-hard even when b = 1. While b-Exact Coverage is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions, even when b = 1. In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property π. Specifically, we consider the universe to be a set of n points in a real space $\mathbb {R}^{d}$, d being a positive integer. When d = 2 we consider the problem when π requires all sets to be unit squares or lines. When d > 2, we consider the problem where π requires all sets to be hyperplanes in $\mathbb {R}^{d}$. These special versions of the problems are also known to be NP-complete. When parameterized by k, the b-Exact Coverage problem has a polynomial size kernel for all the above geometric versions. The b-Exact Multicover problem turns out to be W[1]-hard for squares even when b = 1, but FPT for lines and hyperplanes. Further, we also consider the b-Exact Max. Multicover problem, which takes the same input and decides whether there is a set cover $\mathcal {F}^{\prime }$ such that every element u ∈ U is covered by at least dem(u) sets and at least k elements satisfy the following property: u ∈ U is covered by exactly dem(u) sets of $\mathcal {F}^{\prime }$. To the best of our knowledge, this problem has not been studied before, and we show that it is NP-complete (even for the case of lines). In fact, the problem turns out to be W[1]-hard in the general setting, when parameterized by k. However, when we restrict the sets to lines and hyperplanes, we obtain FPT algorithms.

1 Introduction

The classic Set Cover problem is the following: For a set system $(U,\mathcal {F})$ where U is a finite universe of n elements and $\mathcal {F}$ is a family of subsets of U, and a positive integer k, is there a sub family of at most k sets in $\mathcal {F}$ whose union is U. We say that an element x in U is covered by a set S from $\mathcal {F}$ if the set S contains the element x.

For several applications, it turns out that we would like to not only cover elements of U using sets in $\mathcal {F}$, but also cover them uniquely. A common motivation involves problems where covering elements by more than one set leads to noise (for example, wireless networks), so we would like to ensure that an element is covered by only one of the sets. This desired refinement manifests itself in the following three natural variations of the Set Cover problem.

• All elements must be covered uniquely by at most k sets. (Exact Cover)

• All elements must be covered, and at least k elements must be covered uniquely. (Unique Set Cover)

• At least k elements are covered uniquely. (Unique Coverage)

In the first two variants, we are looking for a set cover with additional properties. Note that in the last setting, a valid solution may not be a set cover.

The Exact Cover problem was one of the twenty-one problems shown to be NP-complete by Karp [16]. The Unique Coverage problem was introduced by Demaine et al. in [5]. Another important point is that Unique Coverage is also a generalization of the Max Cut problem - in this case, from the input graph G we construct the universe U to be the set of edges E(G); each set in $\mathcal {F}$ corresponds to a vertex v ∈ V (G) and is the set of edges incident on v. The Unique Set Cover problem combines elements of both Exact Cover and Unique Coverage, and is NP-complete as well.

A generalization of the Set Cover problem is the Multicovering problem. Here, along with the input set system $(U,\mathcal {F})$ and the positive integer k, we are also provided with a function ${\textsf {dem}}:U\rightarrow \{1,\ldots ,b\}$, where b is an integer. The objective is to decide whether there is a set cover $\mathcal {F}^{\prime }$ that also satisfies the following property: for each u ∈ U, at least dem(u) sets from $\mathcal {F}^{\prime }$ cover u. This problem has a wide range of applications and has been extensively studied [2,3,4, 12, 13, 25]. In this paper, we consider the following related covering problems:

• All elements must be covered with at most k sets and each element u ∈ U must be covered exactly by dem(u) sets. (b-Exact Multicover)

• All elements must be covered such that for each u ∈ U at least dem(u) sets cover it, and there must be at least k elements with the following property: u ∈ U is covered by exactly dem(u) sets. (b-Exact Max. Multicover)

• At least k elements should have the following property: u ∈ U is covered by exactly dem(u) sets. (b-Exact Coverage)

The above problems are natural generalizations of the Exact Cover, Unique Coverage and Unique Set Cover problems.

The Geometric Setting

Geometric settings are among the most promising contexts for developing improved algorithms when faced with hardness in a general setting. The geometric nature of the problem opens up several algorithmic possibilities, and this is amply evidenced in the context of approximation algorithms. Many geometric problems are known to admit good approximation algorithms, even PTASes. In particular, the classical set cover and hitting set problems have been very well-explored in the context of geometric objects [14, 24]. In this situation, the universe is a point set in d-dimensional Euclidean space, and the sets are defined by intersection of geometric objects with the point set. An object covers a point if it contains it.

We study the unique coverage variants for several geometric objects, including lines, hyperplanes, squares, and rectangles. These objects are well studied in the context of the set cover problem and its many variants. The classical set cover problem is known to be NP-hard for all these objects [10, 22]. Point Line Cover is also shown to be APX-hard [17] and therefore, a PTAS algorithm is unlikely. However, Point Line Cover and the set cover problem for hyperplanes admit FPT algorithms and polynomial sized kernels [18]. Set cover using squares, on the other hand, is W[1]-hard [19] and therefore no FPT algorithm exists for this problem under standard complexity theoretic assumptions. This also implies that the PTAS algorithm given in [24] cannot be improved to an EPTAS. Variants of set cover are also studied for these geometric objects [3, 4, 15]

Our Approach

In this work, we focus on the parameterized complexity of these problems, both in the general setting and carefully considered special cases. In parameterized complexity each problem instance comes with a parameter k and a central notion in parameterized complexity is fixed parameter tractability (FPT). This means, for a given instance (x,k), solvability in time f(k) ⋅ p(|x|), where f is an arbitrary function of k and p is a polynomial in the input size. The parameterized problem is said to admit a polynomial kernel if there is a polynomial time algorithm (the degree of the polynomial is independent of k), called a kernelization algorithm, that reduces the input instance down to an instance with size bounded by a polynomial p(k) in k, while preserving the answer.

Studying the parameterized complexity of geometric problems has interesting implications. On the one hand, a tractability result demonstrates the utility of the geometric structure in contrast with the general setting. On the other, a hardness result often has consequences for hardness of approximation; usually it establishes evidence for the non-existence of the EPTAS. This has motivated several studies of geometric problems from a parameterized perspective [19].

Our Results

In this paper we study the capacitated version of all the above problems. In this variant, each vertex has a demand assigned to it and the solution family must fulfill the demand of vertices as required by the problem. More formally, we define the following three problems with respect to any positive integer b.

Notice that when b = 1 and the function dem is the constant function mapping to 1, then we obtain the uncapacitated versions of the problems.

We establish the following results, summarized also in Table 1.

• 1. We show that Exact Cover is W[1]-hard even in the restricted setting where all the objects are unit squares (Lemma 1). Hence, the b-Exact Multicover is W[1]-hard for unit squares. On the positive side, we show that b-Exact Multicover is FPT for lines (Lemma 2). Further, if the objects are hyperplanes in a d-dimensional Euclidean space, then b-Exact Multicover continues to be FPT parameterized by k and d (Theorem 2).

• 2. For b-Exact Coverage, a simple argument shows that the number of elements in the universe can be bounded by O(b²k³) (Theorem 3). This shows that the problem is FPT. It turns out that this also implies a polynomial kernel for various geometric objects (Corollary 3), using the fact that these objects have bounded VC Dimension.

• 3. We show that Unique Set Cover is W[1]-hard in the general setting (Lemma 4) and NP-complete when restricted to lines (Lemma 5). On the positive side, we show that b-Exact Max. Multicover is FPT for families of bounded intersection (Lemma 6) and hyperplanes in d dimensions (Theorem 4).

Table 1 A summary of our results

2 Preliminaries

Parameterized Complexity

A parameterized problem π is a subset of ${\varSigma }^{*} \times \mathbb {N}$. Given a parameterized decision problem with input x ∈Σ^∗ of size n, and an integer parameter k, the goal in parameterized complexity is to design a deterministic algorithm which decides the membership of the instance (x,k) in π in time $f(k)n^{\mathcal {O}(1)}$, where f is a function of k alone. Problems which admit such algorithms are said to be fixed parameter tractable (FPT). We call an algorithm, with a running time of $f(k)n^{\mathcal { O}(1)}$, an FPT algorithm, and such a running time, an FPT running time. The theory of parameterized complexity was developed by Downey and Fellows [7]. For recent developments, see the book by Flum and Grohe [9].

Definition 1

A parameterized problem π FPT-many-one reduces to another parameterized problem Γ, if there is a polynomial p, computable functions $f,g:N\rightarrow N$, and a Turing machine T such that, given any input instance (x,k), T outputs an instance $(x^{\prime },k^{\prime })$ within f(k)p(|x|) time, with (x,k) ∈π if and only if $(x^{\prime },k^{\prime })\in {\varGamma }$, and $k^{\prime } \leq g(k)$.

There is a hierarchy of problems in parameterized complexity. For the purpose of this paper we will define the class W[1] with respect to a hard problem in this class. The class W[1] is the class of all parameterized problems that FPT-many-one reduce to the k-Clique problem parameterized by k. A parameterized problem is W[1]-hard if there is a FPT-many-one reduction from k-Clique, parameterized by k, to the given problem. It is widely believed that FPT ⊂ W[1]. For further understanding of the various parameterized classes, refer to Flum and Grohe [9].

Kernelization

A kernelization algorithm for a parameterized problem π is a polynomial time procedure which takes as input an instance (x,k), where k is the parameter, and returns an instance $(x^{\prime },k^{\prime })$ such that (x,k) ∈π if and only if $(x^{\prime },k^{\prime })\in {{\varPi }}$ and $|x^{\prime }| \leq g(k)$ and $k^{\prime } \leq h(k)$, for some computable functions g,h. The returned instance $(x^{\prime },k^{\prime })$ is said to be the kernel for the instance (x,k) of π.

Problem Definitions

A set system is a pair $(U,\mathcal {F})$, where U is a universe of n elements and $\mathcal {F}$ is a family of m subsets of U. Given a set system $(U,\mathcal {F})$, a set S is said to cover an element p ∈ U if p ∈ S. An element p is said to be covered uniquely by a subfamily $\mathcal {F}^{\prime } \subseteq \mathcal {F}$ if there is exactly one set in $\mathcal {F}^{\prime }$ which contains p. The Set Cover problem asks for a smallest collection of subsets whose union covers every element in the universe. We are now ready to define some of the variations of this problem that we consider in our work.

For completeness, we also define the capacitated versions of the above problems that we study.

As mentioned earlier, when b = 1 and the function dem is the constant function mapping to 1, then we obtain the uncapacitated versions of the problems.

We consider some notions that will be useful in defining special set systems that we will encounter during our study of these problems. Given a set system $(U,\mathcal {F})$, a demand function dem and a subfamily $\mathcal {F}^{\prime } \subseteq \mathcal {F}$, an element u ∈ U is said to be tight if it is covered exactly by dem(u) sets of $\mathcal {F}^{\prime }$. A set system $(U,\mathcal {F})$ is said to have bounded intersection when there is a universal constant c, independent of |U|, such that for any pair of sets $F_{1},F_{2} \in \mathcal {F}$, |F₁ ∩ F₂|≤ c. A set system $(U,\mathcal {F})$ is said to be a set system of squares (lines) if U is a subset of n points in $\mathbb {R}^{2}$ and each set $F \in \mathcal {F}$ is the maximal set of points of U that are contained in a square (line) defined in $\mathbb {R}^{2}$. Similarly, a set system $(U,\mathcal {F})$ is said to be a set system of hyperplanes if U is a set of n points in $\mathbb {R}^{d}$, for a fixed positive integer d, and each set $F \in \mathcal {F}$ is the maximal set of points of U that are contained in a hyperplane defined in $\mathbb {R}^{d}$.

Given a set system $(U,\mathcal {F})$ of n elements and m sets, for every subset $A \subseteq U$ we define the family of sets $\mathcal {F}_{A} = \{S \cap A | S \in \mathcal {F} \}$.

Definition 2 (VC Dimension)

Let $(U,\mathcal {F})$ represent a set system. A subset $A \subseteq U$ is said to be shattered if for every $B \subseteq A$, there exists $F\in \mathcal {F}$ such that F ∩ A = B. The Vapnik-Chervonenkis dimension (or VC dimension) of $(U,\mathcal {F})$ is the supremum of the sizes of all shattered subsets of U.

Therefore, in general, the VC dimension of a set system could be infinite. However, set systems of several geometric objects are known to have bounded VC dimension. We refer the reader to [21] for further details on VC Dimension. The following result is known from [26] about set systems of finite VC dimension.

Proposition 1

Let $(U,\mathcal {F})$ be a set system with |U| = n and VC dimension d. Then $| \mathcal{F}| \leq {n\choose 0}+{n\choose 1}+\cdots+{n\choose d}.$

Hyperplanes

An i-flat in $\mathbb {R}^{d}$ is the affine hull of i + 1 affinely independent points. The dimension of a (possibly infinite) set of points P, denoted as dim(P), is the minimum i such that the entire set P is contained in an i-flat of $\mathbb {R}^{d}$ [18].

Observation 1

[18] For a pair of i-flat H₁ and j-flat H₂, 1 ≤ i ≤ d − 1 and 1 ≤ j ≤ d − 1, if H₁⊄H₂ and H₂⊄H₁, then dim(H₁ ∩ H₂) < min{i,j}.

In this paper we refer to (d − 1)-flats of $\mathbb {R}^{d}$ as hyperplanes in $\mathbb {R}^{d}$.

3 Exact Multicover

In this section, we consider the b-Exact Multicover problem, parameterized by the number k of sets in a solution family. Since the Exact Cover problem is known to be W[1]-hard, it is natural to introduce properties on the input set family and see whether the added structure makes the b-Exact Multicover problem easier in these special cases. Here, we restrict ourselves to geometric versions, where the universe is a set of points in a real space $\mathbb {R}^{d}$, for an appropriate integer d, while the set family is such that every set satisfies a particular geometric property.

The W[1]-hardness of Exact Cover was shown in [23]. We give an alternative proof for this W[1]-hardness. This proof, with a little bit of modification, shows that Exact Cover on set systems of unit squares is also W[1]-hard.

Theorem 1

Exact Cover is W[1]-hard.

Proof

We give a polynomial time reduction from the Clique problem, where the input is a graph G and a positive integer k and the objective is to determine if there is a clique of size k in G. The Clique problem is known to be W[1]-hard when parameterized by the size k of the solution clique [7]. We begin by giving a reduction to Exact Cover in the general setting. Given an instance (G = (V,E),k) of the Clique problem, we construct the following instance $(U,\mathcal {F},k^{\prime })$ of Exact Cover. The idea of the construction is similar to that given in [20].

The reduced instance consists of k² selection gadgets arranged as a k × k grid. The selection gadgets placed along the diagonal of this underlying grid will correspond to the k vertices of the potential clique in the Clique instance. The remaining selection gadgets make sure that all pairs of selected vertices are adjacent. Roughly, to capture the information that the vertex initialized for x_i and the vertex initialized for x_j are adjacent, the selection gadgets responsible are the ones placed along rows i,j and along columns i, j of the underlying grid.

Before we describe the construction, let us define a notation. For the ease of description, we will assume that if a set [a,b] is such that a > b then this set is equivalent to the empty set. In particular, a set [n + 1,n] is an empty set. Again, for an enumerated set S, S[i,j] denotes the subset containing all the elements between the i^th and j^th elements of S. The construction is as below:

• We add k² new elements $U^{\prime } = \{e_{a,b}| 1\leq a,b\leq k\}$.

• We create k(k − 1) copies of V = {1,2,…,n} denoted as H_a,b for a ≤ k, and b ≤ k − 1. We also create k(k − 1) copies of V denoted as V_a,b for a ≤ k − 1 and b ≤ k. $U = U^{\prime } \cup \bigcup _{a,b} (H_{a,b}\cup V_{a,b})$.

• For each i ∈ V, we construct a set $S_{i,i}^{1,1}= H_{1,1}[1,i]\cup V_{1,1}[1,i]\cup \{e_{1,1}\}$ and a set $S_{i,i}^{k,k}= H_{k,k-1}[i+1,n]\cup V_{k-1,k}[i+1,n]\cup \{e_{k,k}\}$.

• For every edge (i,j) ∈ E, we construct a set $S_{i,j}^{k,1}=H_{k,1}[1,i]\cup V_{k-1,1}[j+1,n] \cup \{e_{k,1}\}$ and a set $S_{i,j}^{1,k}=H_{1,k-1}[i+1,n]\cup V_{1,k}[1,j]\cup \{e_{1,k}\}$.

• For each 1 < a < k, and every vertex i ∈ V, we construct a set $S_{i,i}^{a,a}=H_{a,a-1}[i+1,n]\cup H_{a,a}[1,i]\cup V_{a-1,a}[i+1,n]\cup V_{a,a}[1,i]\cup \{e_{a,a}\}$.

• For each 1 < a < k, and every edge (i,j) ∈ E, we construct a set $S_{i,j}^{a,1}=H_{a,1}[1,i]\cup V_{a-1,1}[j+1,n]\cup V_{a,1}[1,j]\cup \{e_{a,1}\}$ and a set $S_{i,j}^{a,k} = H_{a,k-1}[i+1,n]\cup V_{a-1,k}[j+1,n] \cup V_{a,k}[1,j]\cup \{e_{a,k}\}$.

• For each 1 < b < k, and every edge (i,j) ∈ E, we construct a set $S_{i,j}^{1,b}=H_{1,b-1}[i+1,n]\cup H_{1,b}[1,i]\cup V_{1,b}[1,j]\cup \{e_{1,b}\}$ and a set $S_{i,j}^{k,b}=H_{k,b-1}[i+1,n]\cup H_{k,b}[1,i]\cup V_{k-1,b}[1,j]\cup \{e_{k,b}\}$.

• For each 1 < a≠b < k, and every edge (i,j) ∈ E, we construct a set $S_{i,j}^{a,b}=H_{a,b-1}[i+1,n]\cup H_{a,b}[1,i]\cup V_{a-1,b}[j+1,n]\cup V_{a,b}[1,j]\cup \{e_{a,b}\}$.

• $\mathcal {F} = \{S_{i,i}^{a,a}| i \in V, 1\leq a\leq k \} \cup \{S_{i,j}^{a,b}| (i,j)\in E, 1\leq a \neq b \leq k \}$.

• $k^{\prime } = k^{2}$.

In the construction, for an element e_a,a,1 ≤ a ≤ k, we ensure that each set containing e_a,a encodes a distinct vertex of the graph G. On the other hand, for an element e_a,b,1 ≤ a≠b ≤ k, each set containing e_a,b encodes a distinct edge of G.

Claim 1

The constructed Exact Cover instance, $(U,\mathcal {F},k^{\prime })$, has a solution of size $k^{\prime }=k^{2}$ if and only if there is a clique of size k in G.

Proof

Assume there is a clique C of size k in G. Let the vertex set of C be C(V ) = {i₁,i₂,…,i_k}, such that i₁ > i₂ > … > i_k. Then the sets $\{S_{i_{j},i_{j}}^{j,j}| 1\leq j \leq k\} \cup \{S_{i_{j},i_{l}}^{j,l}| 1\leq j\neq l \leq k \}$ form a solution for the above Exact Cover instance.

Conversely, let $\mathcal {S}$ be a solution for the Exact Cover instance. For any (a,b),1 ≤ a,b ≤ k, two sets $S_{i_{1},j_{1}}^{a,b}$ and $S_{i_{2},j_{2}}^{a,b}$ will have the point e_a,b in their intersection. Therefore, for a pair (a,b) at most one set $S_{i,j}^{a,b}$ can be picked in any solution. In fact, the point e_a,b can only be covered by a set $S_{i,j}^{a,b},1\leq i,j\leq n$. This implies that for every pair (a,b), exactly one set $S_{i,j}^{a,b}$ belongs to $\mathcal {S}$. Let {i₁,i₂,…,i_k} be indices such that $\{S_{i_{j},i_{j}}^{j,j}|1\leq j \leq k \} \subseteq \mathcal {S}$. The construction ensures that any other set picked in $\mathcal {S}$ corresponds to an edge of G. For a pair (a,b), if a set $S_{i,j}^{a,b}$ is picked with i < n, then to cover the element H_a,b[i + 1] while maintaining exact coverage, we must pick a set $S_{i,l}^{a,b+1}$, for some 1 ≤ l ≤ k. When i = n, then to cover the element e_a,b+ 1 while maintaining unique coverage, we must pick a set $S_{i,l}^{a,b+1}$, for some 1 ≤ l ≤ k. By similar arguments, if for a pair (a,b), a set $S_{i,j}^{a,b}$ is picked, we must pick a set $S_{l,j}^{a+1,b}$ where 1 ≤ l ≤ k. This implies that for a pair 1 ≤ a≠b ≤ k, the set chosen in $\mathcal {S}$ must be $S_{i_{a},i_{b}}^{a,b}$, where $S_{i_{a},i_{a}}^{a,a}$ and $S_{i_{b},i_{b}}^{b,b}$ have been chosen respectively to cover e_a,a and e_b,b. Then, by construction, i_a≠i_b and (i_a,i_b) ∈ E in the graph G. Thus, the set {i₁,i₂,…,i_k} correspond to a set of k distinct vertices in G, which are pairwise adjacent. This tells us that the induced subgraph G[i₁,…,i_k] is a clique in G. □

This proves W[1]-hardness for Exact Cover. □

Lemma 1

Exact Cover on set systems of unit squares is W[1]-hard.

Proof

We will show that the above reduction in the general case can in fact be made to work for the special case, when each set is a unit square. This will complete the proof of Lemma 1. We need the following specifications for the reduction to go through for this case (See Figs. 1 and 2):

• The element $e_{a,b} \in U^{\prime }$ is the point (b,a).

• The element H_a,b[i],1 ≤ i ≤ n, is the point $(b+\frac {i}{n+1},a)$.

• The element V_a,b[i],1 ≤ i ≤ n, is the point $(b,a+\frac {i}{n+1})$.

• The set $S_{i,j}^{a,b}, 1 \leq i,j \leq n, 1 \leq a,b \leq k$, is the unit square defined by the 4 lines $x = (b-1) + \frac {i}{n+1} +\frac {1}{2(n+1)} , x = b + \frac {i}{n+1} +\frac {1}{2(n+1)} , y = (a-1) + \frac {j}{n+1} +\frac {1}{2(n+1)} , y = a + \frac {j}{n+1} +\frac {1}{2(n+1)}$.

Other than this, the construction of the instance of Exact Cover from an instance (G,k) of the Clique problem is the same as above. The argument for the correctness of the reduction is same as above. This proves that Exact Cover for unit squares is W[1]-hard.

□

Fig. 1

Arrangement of points in a reduced instance

Fig. 2

Sets in a reduced instance

Kernels for Exact Cover with Lines and Hyperplanes

In contrast with the hardness results that we have seen so far, we now turn to some algorithmic results of b-Exact Multicover. First, when we consider our input universe to be a set of n points in $\mathbb {R}^{2}$ and our sets to be maximal sets of collinear points, we obtain a quadratic kernel using a “high degree” reduction rule. This version of Exact Cover is also NP-complete, and the proof for NP-hardness is very similar to the proof of Lemma 5.

Let $((P,{\mathscr{L}}), {\textsf {dem}},k)$ be the input instance of b-Exact Multicover. In our discussion, we use the terms sets and lines interchangeably. The input family could contain sets containing single points. Our first reduction rule is taken directly from [18]. We remove most of the lines that pass through exactly one point.

Reduction Rule 1

For any input point p, from the set ${\mathscr{L}}_{p} = \{L| L \in {\mathscr{L}} \text {and } L \cap P = \{p\} \}$, delete all but dem(p) lines.

Proposition 2

Reduction Rule 1 is sound.

Reduction Rule 2

In an instance $((P,{\mathscr{L}}), {\textsf {dem}},k)$, if there is a line L that contains at least k + 1 input points then delete L and decrease k by one. For each point p contained in L, dem(p) is reduced by 1. If dem(p) becomes 0, then p is deleted from the universe U and all lines containing p are also deleted.

A similar reduction was given in [18] to exhibit a polynomial kernel for Point Line Cover. We show the correctness of this reduction in this case.

Claim 2

Reduction Rule 2 is sound.

Proof

Suppose there is a solution, ${\mathscr{L}}^{\prime }$, for $((P,{\mathscr{L}}), {\textsf {dem}},k)$ which does not contain L. Since ${\mathscr{L}}^{\prime }$ is a set cover that excludes L, it includes at least (k + 1) other lines to cover the points on L, as two lines intersect at at most one point. This contradicts that ${\mathscr{L}}^{\prime }$ is a solution of the instance $((P,{\mathscr{L}}), {\textsf {dem}},k)$. Note that this argument shows that any valid solution of the instance $((P,{\mathscr{L}}), {\textsf {dem}},k)$ must contain L. Now, consider a set $\hat {P}$ of points on L that had demand 1. Consider the subfamily of ${\mathscr{L}}$ comprising of lines that contain points from $\hat {P}$:

${\mathscr{L}}^{\prime \prime } := \{T \in {\mathscr{L}} ~|~ T \neq L, T \cap \hat {P} \neq \emptyset \}.$

Clearly, any solution that contains L does not contain any element of ${\mathscr{L}}^{\prime \prime }$, therefore, it is safe to remove these sets from the instance and the points from $\hat {P}$. Consider any other point p on L. Since all k-sized solutions must contain L, there are exactly dem(p) − 1 other lines in the solution that contain p. Therefore, in the reduced instance, we decrease the demand of p by 1. This establishes the correctness of Reduction Rule 2. □

The reduction is very robust, in the sense that a line as described above will belong to any solution of the b-Exact Multicover instance. On exhaustive application of this reduction, a YES instance can have at most k² remaining input points, since k lines can only cover k² points when each line has at most k points.

Therefore, if our reduced instance has more than k² points, we correctly return NO. Otherwise, due to Reduction Rule 1 and by the property of lines, we can also bound the number of lines in the reduced instance to at most k⁴. Thus, we have shown the following.

Lemma 2

b-Exact Multicover on set systems of lines is FPT, with a polynomial kernel.

A natural question is to consider input instances of b-Exact Multicover which are set systems of hyperplanes in $\mathbb {R}^{d}$. We parameterize the Exact Cover problem in this case by k + d. The following Lemma is obtained by extending the reduction rules in [18]. In particular, it is shown in [18] that for any 1 ≤ i ≤ d − 1, if an i-flat covers more than kⁱ + 1 points, then these points can be replaced with one representative. The crux of the argument is that all of these points are covered “together” by a single hyperplane in any valid solution. In our argument, we extend this reduction rule. Let $((P,\mathcal {F}), {\textsf {dem}},k)$ be an input instance for b-Exact Multicover on set systems of hyperplanes.

Theorem 2

b-Exact Multicover on set systems of hyperplanes in $\mathbb {R}^{d}$ is FPT parameterized by k + d.

Proof

First, we try to reduce the number of elements per hyperplane.

Reduction Rule 3

Repeat for i = 1 to d − 1: for j = 1 to b: If there exists $P^{\prime } \subset P$ such that $| P^{\prime }| \geq k^{i}+1$, each point p in $P^{\prime }$ has dem(p) = j and all points in $P^{\prime }$ lie on a i-flat, then delete all but one points from $P^{\prime }$. We denote the single point that remains behind as $p^{\prime }$. Also, delete all hyperplanes in $\mathcal {F}$ which intersect with a proper subset of $P^{\prime }$.

Proof

We prove the correctness of this reduction rule by induction on i. In the base case, i = 1 and the i-flat is a line L, while $P^{\prime }$ is a set of at least k + 1 points. Consider a solution $\mathcal {F}^{\prime }$ with at most j − 1 hyperplanes that contain the line L. Since $P^{\prime }$ has at least k + 1 points with demand j, each point needs to be covered by at least one more hyperplane of $\mathcal {F}^{\prime }$ that does not contain the line L. Due to Observation 1, this means that $\mathcal {F}^{\prime }$ has at least k + 1 hyperplanes, which is a contradiction as the size of a solution family must be at most k. As the demand of the points in $P^{\prime }$ is j, any solution family $\mathcal {F}^{\prime }$ must contain exactly j hyperplanes that contain the line L. Thus, any hyperplane in $\mathcal {F}$ that intersects with a proper subset of $P^{\prime }$ cannot be part of any solution family and they can be safely deleted. In the remaining instance, any hyperplane that covers the point $p^{\prime }$ will also contain the line L and therefore the points set $P^{\prime }$.

By the induction hypothesis, let the reduction rule be correct till $i^{\prime }<i$. We need to show that the reduction rule is correct for i. Suppose there is an i-flat L with a point set $P^{\prime }$ of at least kⁱ + 1 points, each with demand j. Consider a solution $\mathcal {F}^{\prime }$ with at most j − 1 hyperplanes that contain L. Since $P^{\prime }$ has at least kⁱ + 1 points with demand j, each point needs to be covered by at least one more hyperplane of $\mathcal {F}^{\prime }$ that does not contain the line L. Due to Observation 1, for any hyperplane $H \in \mathcal {F}^{\prime }$ that does not contain L, the intersection H ∩ L is of dimension at most i − 1. By the induction hypothesis, an $i^{\prime }$-flat, for $i^{\prime } \leq i-1$, contains at most $k^{i^{\prime }}$ points. This means that at least k + 1 extra hyperplanes from $\mathcal {F}^{\prime }$ are required to meet the demand of the kⁱ + 1 points of $P^{\prime }$. This is a contradiction as the size of a solution family must be at most k. As the demand of the points in $P^{\prime }$ is j, any solution family $\mathcal {F}^{\prime }$ must contain exactly j hyperplanes that contain the line L. Thus, any hyperplane in $\mathcal {F}$ that intersects with a proper subset of $P^{\prime }$ cannot be part of any solution family and they can be safely deleted. In the remaining instance, any hyperplane that covers the point $p^{\prime }$ will also contain the line L and therefore the points set $P^{\prime }$. □

After exhaustive application of this Reduction Rule, any hyperplane H contains at most bk^(d− 1) points. Since a b-Exact Multicover solution is also a set cover of size at most k, there can be at most bk^d points in the reduced instance. The VC dimension of a hyperplane in $\mathbb {R}^{d}$ is d. From Proposition 1, for a set system of VC Dimension d, the number of distinct sets is bounded by O(n^d). Hence, the number of sets in $\mathcal {F}$ is bounded by $\mathcal {O}(b^{d}k^{d^{2}})$. Thus we can design an algorithm similar to that described in Lemma 2. □

4 Exact Coverage

The Unique Coverage problem was studied in [23] and was found to be FPT. However, the problem does not admit any polynomial kernel unless $NP \subseteq coNP/poly{}$, as shown in [6]. In this section, we first obtain polynomial sized element kernels for b-Exact Coverage. We then exhibit polynomial sized kernels for several geometric versions, exploiting the geometric property satisfied by each set of the input set system.

Recall that the b-Exact Coverage problem is parameterized by the number of elements that we desire to cover tightly. To begin with, in the general setting, we show that the number of elements in the universe can be bounded by bk³.

First, we remove some redundant elements from the universe.

Reduction Rule 4

Let u ∈ U be an element such that ${\textsf {dem}}(u) > | \{ S | u \in S, S \in \mathcal {F}\} |$. Then we delete u from U.

Claim 3

Reduction Rule 4 is sound.

Proof

Let u be an element such that dem(u) is greater than the number of sets in $\mathcal {F}$ that contain u. Then in any solution subfamily $\mathcal {F}^{\prime }$, u cannot be a tight element. Thus, we can safely delete u. □

We exhaustively apply Reduction Rule 4. In the end, we know that each element in the universe is contained is at least as many sets of $\mathcal {F}$ as dem(u).

We try to bound the number of elements in each set of $\mathcal {F}$. Before that we need a definition.

Definition 3

Given a set $S \in \mathcal {F}$ and a positive integer i, an i-intersection in S is the intersection of i − 1 sets of $\mathcal {F}-S$ and S itself.

Lemma 3

Let $\mathcal {F}$ be part of an input instance of Exact Coverage such that Reduction Rule 4 is not applicable. Then we can either correctly conclude that it is a YES instance or the following statement holds : Given a set $S \in \mathcal {F}$ and an i ∈{1,2,…,b}, then |{u|u ∈ S,dem(u) = i}|≤ (k − 1)².

Proof

Since Reduction Rule 4 is no longer applicable, any element u ∈ S that has dem(u) = i must be contained in an i-intersection in S. Consider all the i-intersections in S. If there is an i-intersection that contains at least k elements then we say YES. Thus, we assume that each i-intersection has at most k − 1 elements. Arbitrarily pick an element u₁ from an i-intersection and discard all the i-intersections in S that contain u₁. From the remaining i-intersections, pick another element u₂, and continue this process till possible. If we can pick k such elements, then again we say YES. Otherwise, we were able to pick at most k − 1 elements during the greedy subroutine on the i-intersections. Notice that the set of elements picked during the subroutine form a hitting set of the i-intersections in S. Thus, if we discard these elements the size of each i-intersection in S goes down by at least 1. We repeat the greedy subroutine, till all elements in the i-intersections have been discarded. We started with each i-intersection having at most k − 1 elements. Moreover, each time the subroutine ended with us not concluding that the input instance was a YES instance, we picked at most k − 1 elements greedily that formed a hitting set for all the i-intersections in S. Thus, the total number of elements that belong to i-intersections in S is at most (k − 1)². □

Corollary 1

Let $\mathcal {F}$ be part of an input instance of Exact Coverage such that Reduction Rule 4 is not applicable. Then we can either correctly conclude that it is a YES instance or the following statement holds : Given a set $S \in \mathcal {F}$, there are at most b(k − 1)² elements in S.

Proof

Since Reduction Rule 4 is no longer applicable, each element in a set $S\in \mathcal {F}$ must belong to an i-intersection in S, i ∈{1,2,…,b}. Therefore, there are at most b(k − 1)² elements on each set $S \in \mathcal {F}$. □

Next, we define a b-minimal multicover.

Definition 4

Given a set system $(U,\mathcal {F})$ and a demand function dem, a b-minimal multicover is a subfamily $\mathcal {F}^{\prime }$ where (i) for each u ∈ U, u is covered by at least dem(u) sets in $\mathcal {F}^{\prime }$, (ii) for each set $S\in \mathcal {F}^{\prime }$, there is an element u ∈ U such that $\mathcal {F}^{\prime }- S$ does not cover u with at least dem(u) sets.

Observation 2

Given a set system $(U,\mathcal {F})$ where Reduction Rule 4 does not apply, and a demand function dem, if there is a b-minimal multicover $\mathcal {F}^{\prime }$ of size at least bk, then there are at least k elements that are tight in $\mathcal {F}^{\prime }$.

Proof

There is a tight element in each set of $\mathcal {F}^{\prime }$. Each tight element can be contained in at most b sets of $\mathcal {F}^{\prime }$. Therefore, by Pigeonhole Principle, if there are bk sets in $\mathcal {F}^{\prime }$ then there are at least k tight elements in $\mathcal {F}^{\prime }$. □

This helps us to obtain an element kernel for b-Exact Coverage.

Theorem 3

b-Exact Coverage has an element kernel of size b²k³.

Proof

We construct a b-minimal multicover $\mathcal {F}^{\prime }$ and if it has at least bk sets then we say YES. Otherwise, the number of sets in $\mathcal {F}^{\prime }$ is at most bk. By Corollary 1, each set in $\mathcal {F}^{\prime }$ has at most b(k − 1)² elements. Therefore, the total number of elements in the universe is at most b²k³. □

The following result regarding sets of bounded VC Dimension are now implied by Proposition 1 and Theorem 3.

Corollary 2

b-Exact Coverage on set systems of VC Dimension bounded by a constant d admits a polynomial kernel.

Proof

From Theorem 3, we know that b-Exact Coverage is FPT with an element kernel of $\mathcal {O}(b^{2}k^{3})$. By Proposition 1, the family $\mathcal {F}$ can have at most $\mathcal {O}((b^{2}k^{3})^{d})$ sets. Thus, we have a kernel for this version of Unique Coverage. □

As an immediate consequence, we get the existence of polynomial kernels in special geometric cases, since these geometric set families have constant VC Dimension.

Corollary 3

Unique Coverage admits a polynomial kernel for set systems of lines, hyperplanes, axis-parallel rectangles and disks.

Proof

The proof follows from the fact that these geometric set families have constant VC Dimension [21]. Following from Proposition 1, for a family of sets of VC Dimension d, the number of distinct sets is bounded by O(n^d). In particular, we have the following based on Theorem 3.

• 1. Since the VC Dimension of lines is two, b-Exact Coverage admits a kernel with O(b²k³) points and O(b⁴k⁶) lines.

• 2. Since the VC Dimension of hyperplanes in $\mathbb {R}^{d}$ is d, b-Exact Coverage admits a kernel with O(b²k³) points and O(b^2dk^3d) hyperplanes.

• 3. Since the VC Dimension of axis-parallel rectangles is four, b-Exact Coverage admits a kernel with O(k²) points and O(k⁸) axis-parallel rectangles.

• 4. Since the VC Dimension of disks is three, b-Exact Coverage admits a kernel with O(b²k³) points and O(b⁶k⁹) disks.

□

When we consider the Unique Coverage problem, we get better results. To begin with, in the general setting, we show that the number of elements in the universe can be bounded by k². Note that it is straightforward to bound the sizes of the individual sets in an instance of Unique Coverage, with the following observation.

Observation 3

If there exists $F_{i} \in \mathcal {F}$ such that |F_i|≥ k, then the given instance is a YES instance, with {F_i} serving as a valid solution.

We now turn to an argument for bounding the size of the universe in an instance of Unique Coverage.

Proposition 3

[23] Unique Coverage admits a quadratic element kernel.

The following result regarding sets of bounded VC Dimension are now implied by Propositions 1 and 3.

Corollary 4

Unique Coverage on set systems of VC Dimension bounded by a constant d admits a polynomial kernel.

Proof

From Proposition 3, we know that Unique Coverage is FPT with an element kernel of $\mathcal {O}(k^{2})$. By Proposition 1, the family $\mathcal {F}$ can have at most $\mathcal {O}((k^{2})^{d})$ sets. Thus, we have a kernel for this version of Unique Coverage. □

Again, we get the existence of polynomial kernels in special geometric cases, due to constant VC Dimension.

Corollary 5

Unique Coverage admits a polynomial kernel for set systems of lines, hyperplanes, axis-parallel rectangles and disks.

Proof

The proof follows from the fact that these geometric set families have constant VC Dimension. Following from Proposition 1, for a family of sets of VC Dimension d, the number of distinct sets is bounded by O(n^d). In particular, we have the following based on Proposition 3.

• 1. Since the VC Dimension of lines is two, Unique Coverage admits a kernel with O(k²) points and O(k⁴) lines.

• 2. Since the VC Dimension of hyperplanes in $\mathbb {R}^{d}$ is d, Unique Coverage admits a kernel with O(k²) points and O(k^2d) hyperplanes.

• 3. Since the VC Dimension of axis-parallel rectangles is four, Unique Coverage admits a kernel with O(k²) points and O(k⁸) axis-parallel rectangles.

• 4. Since the VC Dimension of disks is three, Unique Coverage admits a kernel with O(k²) points and O(k⁶) disks.

□

It may be noted that kernels of smaller size are known for lines. Using the fact that two lines intersect in at most one point and Theorem 3 in [23], we can see that Unique Coverage with lines admits a kernel with O(k²) lines.

5 Exact Max. Multicover

We show that Unique Set Cover is W[1]-hard. However, as with the other problems, assuming geometric properties on the set family provides positive algorithmic results for b-Exact Max. Multicover.

Lemma 4

Unique Set Cover is W[1]-hard.

Proof

We give a reduction from the Multicolored Clique problem, which is known to be W[1]-hard when parameterized by the size k of the solution clique [8]. An instance of the Multicolored Clique problem consists of a graph G and a partition of its vertex set into k parts, and the question is if there exists a clique involving exactly one vertex from each part. For an instance (G = (V₁ ⊎… ⊎ V_k,E),k) of Multicolored Clique we construct the following instance for Unique Set Cover:

• We create a set of elements corresponding to the vertices of G, denoted by A = {e_v|v ∈ V }. Note that there is a natural partition of A = A₁ ⊎ A₂ ⊎… ⊎ A_k based on the given partition of V.

• We add a set of elements B = {b_ij|1 ≤ i,j ≤ k}, and a set of elements C = {c_i|1 ≤ i ≤ k}.

• Let U = A ∪ B ∪ C.

• For each 1 ≤ i ≤ k we add a set S_i = {c_i}∪{e_v|v ∈ V_i} to our set family $\mathcal {F}$.

• For each edge (u,v) ∈ E, where u ∈ V_i and v ∈ V_j≠i, we add the following set to $\mathcal {F}$:

  $$S_{u,v} = \{b_{ij}\}\cup \{e_{w}| w \in (V_{i} \setminus u) \cup (V_{j} \setminus v)\}$$

• We assume, without loss of generality, that k > 2 (if not, the problem is solved in constant time and we define an appropriate trivial reduced instance).

• Finally, we set l = ${k \choose 2} + 2k$. This completes the description of the reduced instance.

In the forward direction, suppose X = {v₁,v₂,…,v_k} is a multi-coloured clique in G. The family of sets $\{S_{i}| 1 \leq i \leq k\} \cup \{S_{v_{i},v_{j}}| v_{i},v_{j} \in X\}$ is a set cover where the l elements in $\{e_{v_{i}} | v_{i} \in X\} \cup B \cup C$ are uniquely covered. Thus, this is a solution family for Unique Set Cover.

In the backward direction, since a solution must be a set cover, we must cover c_i for all 1 ≤ i ≤ k. Each element of C belongs to a unique set. Hence the subfamily of sets {S₁,…,S_k} must be present in any set cover and the k elements of C are uniquely covered by any set cover.

For a fixed 1 ≤ i ≤ k, consider the collection of elements B_i = {b_ij|1 ≤ j≠i ≤ k}. Each b_ij must be covered by at least one set $S_{u^{j},v^{j}}$, where (u^j,v^j) ∈ E and u^j ∈ V_i while v^j ∈ V_j. Assuming k > 2, if each u^j,1 ≤ j≠i ≤ k is the same vertex u ∈ V_i then the set cover considered so far covers e_u uniquely, since all sets $S_{u,v^{j}}$ do not contain e_u. On the other hand, suppose u^p = e_p and u^q = e_q for 1 ≤ p≠q ≤ k. Then $S_{u^{p},v^{p}}$ covers all elements of A except for u_p and $S_{u^{q},v^{q}}$ covers all elements of A except for u_q. Since u_p≠u_q, both u_p and u_q are covered at least once by $S_{u^{p},v^{p}} \cup S_{u^{q},v^{q}}$. Recall that these elements are already covered by S_i, and therefore we cannot cover any of the elements of A_i uniquely. This is true for all 1 ≤ i ≤ k. Thus, we can only hope to uniquely cover at most k elements from the set A.

The remaining elements are from B, add to ${k \choose 2}$ and must all be uniquely covered in a solution. Let the set chosen to uniquely cover the element of b_ij ∈ B be $S_{u_{ij},v_{ij}}$. This set corresponds to an edge (u_ij,v_ij) ∈ E such that u_ij ∈ V_i and v_ij ∈ V_j for some 1 ≤ i≠j ≤ k.

To meet the given budget, a solution for Unique Set Cover must cover exactly k elements of A uniquely. From the above argument, this can only happen if we cover exactly one element $e_{u_{i}}$ from each partition A_i. Also, for this to happen, for each i, and each pair $1 \leq j \neq j^{\prime }\leq k$ such that j≠i and $j^{\prime } \neq i$, $u_{ij} = u_{ij^{\prime }} = u_{i}$.

Now consider the set of vertices $X = \{u_{i}| 1 \leq i\leq k\} \subseteq V$. This is a set of k vertices where no two vertices are from the same partition of V. For any pair 1 ≤ i≠j ≤ k, the set $S_{u_{i},u_{j}}$ chosen to cover the element b_ij ensures that there is an edge (u_i,u_j) ∈ E. Hence, X is a multicoloured clique in G.

This proves the W[1]-hardness of Unique Set Cover. □

The reduction also shows that Unique Set Cover is NP-hard. In fact, even when we consider the special case when the universe U is a set of n points in $\mathbb {R}^{2}$ and each set is a line, the Unique Set Cover problem turns out to be NP-hard, as we show in our next lemma.

Lemma 5

Unique Set Cover on set systems of lines is NP-complete.

Proof

The NP-hardness reduction is very similar to the NP-hardness reduction for Point Line Cover [22]. We reduce the problem from 1-IN-3-SAT, whose NP-hardness was shown in [11]. Given a boolean formula F in conjunctive normal form where each clause has three literals, 1-IN-3-SAT asks whether there is a truth assignment to the variables of F such that each clause of F has exactly one true literal. Let ϕ be an instance of 1-IN-3-SAT, with n variables {v₁,v₂,…,v_n} and m clauses {C₁,…C_m}. we construct an instance $(U,\mathcal {F},k)$ for Unique Set Cover with lines in the following manner:

• For each clause C_i,1 ≤ i ≤ m, we create a point P_i.

• For each variable v_j,1 ≤ j ≤ n, we create a grid of m² points $p^{j}_{ab}, 1\leq a,b\leq m$.

• For a fixed 1 ≤ j ≤ n and a fixed 1 ≤ a ≤ m, the set of points $\{p^{j}_{qa} | 1 \leq q \leq m\}$ are contained in a line L_ja and the set of points $\{p^{j}_{aq} | 1 \leq q \leq m\}$ are contained in a line $\bar {L}_{ja}$.

• For each 1 ≤ i ≤ m and 1 ≤ j ≤ n, if the literal v_j is in C_i, then the point P_i is contained in L_ji. If the literal $\bar {v}_{j}$ is in C_i then the point P_i is contained in $\bar {L}_{ji}$.

• The above description gives the exact points that can lie on each line.

• $U = \{P_{i} | 1\leq i \leq m\} \cup \bigcup _{1\leq j\leq n} \{p_{ab}^{j} | 1\leq a,b \leq m\}$. |U| = nm² + m.

• $\mathcal {F} = \{L_{jb} | 1 \leq j \leq n, 1 \leq b \leq m\} \cup \{\bar {L}_{jb} | 1 \leq j \leq n, 1\leq b\leq m\}$.

• We set k = nm² + m.

Suppose ϕ is a YES instance for 1-IN-3-SAT and let Γ be a truth assignment. If Γ(v_j) = 1 we pick the lines {L_jb|1 ≤ b ≤ m}. If Γ(v_j) = 0 we pick the lines $\{\bar {L}_{jb} | 1 \leq b \leq m\}$. By construction, all points $p^{j}_{ab}, 1 \leq j \leq n, 1 \leq a,b \leq m,$ are covered uniquely. Since, Γ is a satisfying assigment for 1-IN-3-SAT, the points P_i,1 ≤ i ≤ m, are also covered uniquely. Thus, our constructed instance is a YES instance for Unique Set Cover with lines.

Conversely, suppose $(U,\mathcal {F},k)$ has a solution family $\mathcal {F}^{\prime }$ for Unique Set Cover. By the value of k, each element in the instance has to be covered uniquely. Each point P_i is contained in exactly 3 lines, by our construction. Suppose the line L_ji,1 ≤ j ≤ n covers the point P_i uniquely in $\mathcal {F}^{\prime }$. Then it is possible to cover all the m² points $p^{j}_{ab},1 \leq a,b\leq m$ uniquely only by the subfamily {L_jq|1 ≤ q ≤ m}. Hence, all these lines must belong to $\mathcal {F}^{\prime }$. Suppose the line $\bar {L}_{ji}, 1\leq j\leq n$ covers the point P_i uniquely in $\mathcal {F}^{\prime }$. Then, by a similar argument, the subfamily $\{\bar {L}_{jq} | 1\leq q\leq m\}$ must belong to $\mathcal {F}^{\prime }$. Suppose the line L_ji,1 ≤ j ≤ n is not picked to cover the point P_i uniquely in $\mathcal {F}^{\prime }$. Then it is only possible to cover the m² points $p^{j}_{ab},1 \leq a,b\leq m$ uniquely by the subfamily $\{\bar {L}_{jq}|1\leq q\leq m\}$, and all these lines must belong to $\mathcal {F}^{\prime }$. Suppose the line $\bar {L}_{ji}, 1\leq j\leq n$ is not picked to cover the point P_i uniquely in $\mathcal {F}^{\prime }$. Then, by a similar argument, the subfamily {L_jq|1 ≤ q ≤ m} must belong to $\mathcal {F}^{\prime }$. From this, we construct a satisfying assignment Γ for ϕ. If the family {L_jb|1 ≤ b ≤ m} is used to cover the points $\{p^{j}_{ab}| 1 \leq a,b\leq m\}$, then Γ(v_j) = 1. Otherwise, Γ(v_j) = 0. Under this assignment, any clause C_i is satisfied only by the literal corresponding to the line uniquely covering P_i.

Thus Unique Set Cover with lines is NP-hard. □

This implies that Unique Set Cover on set systems with bounded intersection and Unique Set Cover on set systems of hyperplanes are also NP-hard. In the parameterized context, although Unique Set Cover is W[1]-hard in the general setting, we look at some special cases where the problem of b-Exact Max. Multicover can be solved in FPT time. First, we make a few observations.

Observation 4

Let $\mathcal {F}^{\prime }$ be a solution for b-Exact Max. Multicover. Then any b-minimal multicover contained in $\mathcal {F}^{\prime }$ is also a solution for b-Exact Max. Multicover.

Thus, it is enough to find a b-minimal multicover that covers at least k elements tightly.

Now, we turn to algorithmic results for special cases of b-Exact Max. Multicover.

Sets of Bounded Intersection.

First, we consider set systems $(U,\mathcal {F})$ where $\mathcal {F}$ has the property that for any pair of sets $F_{1},F_{2} \in \mathcal {F}$, |F₁ ∩ F₂|≤ c.

Lemma 6

b-Exact Max. Multicover for sets of bounded intersection c is FPT when parameterized by c + k.

Proof

Suppose there is an element u ∈ U such that ${\textsf {dem}}(u) > | \{ H | u\in H, H \in \mathcal {F} \} |$, then we say NO. Otherwise, we construct a b-minimal multicover $\mathcal {S}$ for the instance. If the size of $\mathcal {S}$ is at least bk, then it is a solution for Unique Set Cover, by definition of a b-minimal multicover and by Observation 2. Similarly, if there is a set $S \in \mathcal {S}$ that contains at least k tight elements, then $\mathcal {S}$ is a solution for Unique Set Cover. Suppose there are at most bk − 1 sets in $\mathcal {S}$ and each set has at most k − 1 tight elements. Since $\mathcal {S}$ is a set cover, by the Pigeonhole Principle there must be a set $S\in \mathcal {S}$ which contains at least n/(bk − 1) elements of U. The number of elements in S that can belong to other sets of $\mathcal {S}$ is at most c(bk − 2), because of the bounded intersection property. There are $\frac {n}{bk-1} - c(bk-2)$ elements that belong only to S and their demand must be equal to 1, as otherwise we would have said NO. Thus all these elements are tight. If $\frac {n}{bk-1} - c(bk-2) \geq k$ then the given instance is a YES instance. Otherwise, $\frac {n}{bk-1} - c(bk-2) \leq k-1$, which implies that n ≤ (1 + c)(bk − 1)².

Since the sets have bounded pairwise intersection of at most c, any subset of c + 1 elements can appear together in at most one set. Therefore, the number of sets are bounded by n^c+ 1 ≤ ((1 + c)(bk − 1)²)^c+ 1. We can now guess the uniquely covered elements, and the distribution of the uniquely covered elements in a Unique Set Cover solution. Finally, we can check whether there are sets in $\mathcal {F}$ to validate the guess in polynomial time. As the number of guesses is an FPT function, the running time of this algorithm is FPT. □

Hyperplanes in $\mathbb {R}^{d}$.

Next, we consider a geometric set system $(U, \mathcal {F})$ where U is a set of n points in $\mathbb {R}^{d}$ and sets in $\mathcal {F}$ are defined by hyperplanes in $\mathbb {R}^{d}$. When d = 2, these are lines and this is a special case of sets with bounded intersection. For d > 2, hyperplanes do not have this property. Nonetheless, we obtain an FPT algorithm for hyperplanes, by reducing the given instance to an instance of b-Exact Max. Multicover for sets with bounded intersection.

Theorem 4

The b-Exact Max. Multicover problem on set systems of hyperplanes in $\mathbb {R}^{d}$ is FPT.

Proof

Let U be a universe of n elements and $\mathcal {F}$ be a family of m hyperplanes in $\mathbb {R}^{d}$. The following Reduction Rule aims at reducing the number of points, while maintaining the Unique Set Cover solution if there exists one.

Reduction Rule 5

for i from 1 to d − 1: for j from 1 to b: Suppose $P \subseteq U$ is a set of at least ((b + 1)k)ⁱ points such that for each p ∈ Pdem(p) = j, dim(P) = i, and P is contained in at least one hyperplane of $\mathcal {F}$. Let $\mathcal {F}_{P} \subseteq \mathcal {F}$ is the set of all hyperplanes that contain P. If for some subfamily $\mathcal {F}_{P}^{\prime } \subseteq \mathcal {F}_{P}$ of exactly j − 1 hyperplanes, $(\mathcal {F} \setminus \mathcal {F}_{P})\cup \mathcal {F}_{P}^{\prime }$ has a b-minimal multicover for U, then we say YES for our input instance and exit. Otherwise, we delete all but ((b + 1)k)ⁱ points of P from the universe. If a hyperplane becomes empty, we delete that hyperplane from $\mathcal {F}$.

We prove the correctness of this reduction rule by induction on i. When i = 1, P is contained in a line and has more than (b + 1)k points each with demand j. Suppose there is an $\mathcal {F}_{P}^{\prime } \subseteq \mathcal {F}_{P}$ of exactly j − 1 hyperplanes such that $(\mathcal {F} \setminus \mathcal {F}_{P})\cup \mathcal {F}_{P}^{\prime }$ is a set cover such that for each point the number of hyperplanes of the set cover containing p is at least dem(p). Let $\mathcal {G}$ be a minimal set cover obtained from $\mathcal {F} \setminus \mathcal {F}_{P}$. Then, by Observation 1 and by the definition of a b-minimal multicover, any set in $\mathcal {G}\setminus \mathcal {F}_{P}^{\prime }$ can contain at most one point of P. To cover all elements of P, there must be at least bk sets in $\mathcal {G}$. By Observation 2, we correctly say YES. If no such set cover exists, then we know that any set cover for the input instance must contain at least j hyperplanes from $\mathcal {F}_{P}$. Let $P^{\prime } \subset P$ be the set of all but (b + 1)k points that are deleted by the Reduction Rule and $P^{\prime \prime }=P\setminus P^{\prime }$. Also, let $\mathcal {F}^{\prime }$ be the family of hyperplanes that became empty and got deleted from $\mathcal {F}$. Suppose $\mathcal {G} = \{H_{1}, \ldots , H_{l}\}$ is a b-minimal solution for $(U,\mathcal {F},k)$. Since P is a line with more than (b + 1)k points, there must be at least jH_i that contains all of P. Now, the following cases can occur:

• 1. Suppose there are j + 1 hyperplanes of $\mathcal {G}$, all of which contain the set P. Then none of the points in P are tightly covered by this solution. The points which are tightly covered are not deleted as a result of this Reduction Rule. Also, by definition of b-minimality, no hyperplane of $\mathcal {G}$ could have become empty after this Reduction Rule was applied. Hence, $\mathcal {G}$ remains a solution for b-Exact Max. Multicover in $(U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

• 2. Suppose l > j + (b + 1)k. Since we have dealt with the case when P is covered be at least j + 1 hyperplanes of $\mathcal {G}$, we can assume that there are exactly j hyperplanes in $\mathcal {G}$ that contain P. There are at least bk remaining hyperplanes in $\mathcal {G}$. Since, $\mathcal {G}$ is a b-minimal solution for b-Exact Max. Multicover, each of these remaining hyperplanes contain a tight point, and none of these tightly covered points belong to P. Hence, by Observation 2, $\mathcal {G}$ remains a solution for $(U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

• 3. Finally, suppose l ≤ j + (b + 1)k, and as before, let the family ${\mathscr{H}}$ of exactly j hyperplanes of $\mathcal {G}$ contain all points in P. Then at most l − j points of P are not tightly covered. All other points of P must be tightly covered. In particular, at most l − j points of $P \setminus P^{\prime }$ are not tightly covered, which implies that at least (b + 1)k − l + j points in $P \setminus P^{\prime }$ are tightly covered by $\mathcal {G}$. If (b + 1)k − l + j ≥ k then we say YES. Otherwise, (b + 1)k − l + j < k, or bk < l − j. By b-minimality, for each hyperplane $H^{\prime }$ in $\mathcal {G} \setminus {\mathscr{H}}$ there is a point $p_{H^{\prime }}$ that is tightly covered by $H^{\prime }$, and none of these points are from P. By Observation 2, at least k points from $\mathcal {G} \setminus \{H\}$ are covered tightly. Again, by b-minimality, no hyperplane of $\mathcal {G}$ could have become empty because of application of the Reduction Rule. Hence, $\mathcal {G}$ is a solution in $(U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

On the other hand, let $\mathcal {G}^{\prime }$ be a b-minimal solution for $(U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$. Assume $\mathcal {G}^{\prime }$ is not a solution for $(U, \mathcal {F} , k)$ but has a set $\hat {\mathcal {F}}^{\prime }$ of c hyperplanes from $\mathcal {F}_{P}$. Then each point in $P^{\prime \prime }$ is covered by at least one different hyperplane in $\mathcal {G}^{\prime }$. Let this subfamily of $\mathcal {G}^{\prime }$, with at least (b + 1)k hyperplanes, be ${\mathscr{H}}^{\prime }$.Let $\hat {\mathcal {F}} \in \mathcal {F}_{P}$ be a subfamily of j − c hyperplanes. Consider $\mathcal {G}^{\prime } \cup \hat {\mathcal {F}}$, which is clearly a set cover for $(U, \mathcal {F})$ that meets the demands of all points of U. Let $\mathcal {S} \subset \mathcal {G}^{\prime }\cup \hat {\mathcal {F}}$ be a b-minimal multicover of $(U,\mathcal {F})$. Notice that none of the hyperplanes in $\hat {\mathcal {F}}\cup \hat {\mathcal {F}}^{\prime }$ will be deleted from $\mathcal {S}$. Consider the points of $P^{\prime \prime }$. Either a point p is tight, or there is at least one hyperplane in $\mathcal {S} \setminus (\hat {\mathcal {F}} \cup \hat {\mathcal {F}}^{\prime })$ that contains the point p and no other point from $P^{\prime \prime }$. Let $\hat {P} \subseteq P^{\prime \prime }$ be the set of t points that are tight in $\mathcal {S}$. Since $\hat {\mathcal {F}} \subseteq \mathcal {S}$, $\mathcal {S}$ is still a b-minimal multicover for $U\setminus \hat {P}$. The number of hyperplanes in $\mathcal {S}$ is at least $| P^{\prime \prime }| -t = (b+1)k -t \geq b(k-t)$. Thus, by Observation 2, in $\mathcal {S}$ there are at least k − t tight points other than the set $\hat {P}$ of t points. Thus $\mathcal {S}$ still covers at least k points uniquely and is a solution for $(U, \mathcal {F} , k)$.

Now, assume i > 1 and the Induction Hypothesis is true for all $i^{\prime } <i$. Suppose P is a set of at least ((b + 1)k)ⁱ + 1 points such that dim(P) = i, and P is contained in at least 1 hyperplane. Suppose there is an $\mathcal {F}_{P}^{\prime } \subseteq \mathcal {F}_{P}$ of exactly j − 1 hyperplanes such that $(\mathcal {F} \setminus \mathcal {F}_{P})\cup \mathcal {F}_{P}^{\prime }$ is a set cover such that for each point the number of hyperplanes of the set cover containing p is at least dem(p). Let $\mathcal {G}$ be a minimal set cover obtained from $\mathcal {F} \setminus \mathcal {F}_{P}$. Then any set in $\mathcal {G}$ can intersect P at a subset $Q \subseteq P$ such that dim(Q) < i (Observation 1). By Induction Hypothesis, |Q|≤ ((b + 1)k)^i− 1. Thus, $\mathcal {G}$ must have at least (b + 1)k hyperplanes to cover all points of P. By Observation 2, we correctly output YES. Otherwise, every b-minimal multicover of the input instance must contain at least j hyperplanes from $\mathcal {F}_{P}$. Let $P^{\prime } \subset P$ be the set of all but ((b + 1)k)ⁱ points that are deleted by the Reduction Rule. Also, let $\mathcal {F}^{\prime }$ be the family of hyperplanes that became empty and got deleted from $\mathcal {F}$. Suppose $\mathcal {G} = \{H_{1}, \ldots , H_{l}\}$ be a minimal solution for $(U,\mathcal {F},k)$. The following cases can occur:

• 1. Suppose there are j + 1 hyperplanes in $\mathcal {G}$ all of which contain the set P. Then none of the points in P are tightly covered by this solution. The points which are tightly covered cannot be deleted as a result of this Reduction Rule. Also, by definition of b-minimality, no hyperplane of $\mathcal {G}$ could have become empty after this Reduction Rule was applied. Hence, $\mathcal {G}$ remains a solution for b-Exact Max. Multicover in $U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

• 2. Suppose l > j + (b + 1)k. Since we have dealt with the case when P is covered be at least j + 1 hyperplanes of $\mathcal {G}$, we can assume that there are exactly j hyperplanes in $\mathcal {G}$ that contain P. There are at least bk remaining hyperplanes in $\mathcal {G}$. Since, $\mathcal {G}$ is a b-minimal solution for Unique Set Cover, by Observation 2 there are at least k tight points. Hence, $\mathcal {G}$ remains a solution for $U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

• 3. Lastly, suppose $P^{\prime \prime }$ is covered by exactly j hyperplanes of a subfamily ${\mathscr{H}}$ of $\mathcal {G}$,and l ≤ j + (b + 1)k. For each $H^{\prime } \in \mathcal {G} \setminus {\mathscr{H}}$, the intersection set $Q = H^{\prime } \cap P$ can have at most ((b + 1)k)^i− 1 points, by Observation 1 and induction hypothesis. Then at most (l − j) ⋅ ((b + 1)k)^i− 1 points of P are not tightly covered. All other points of P must be tightly covered. In particular, at most (l − j) ⋅ ((b + 1)k)^i− 1 points of $P \setminus P^{\prime }$ are not tightly covered , which implies that at least ((b + 1)k)ⁱ − (l − j)((b + 1)k)^i− 1 points in $P \setminus P^{\prime }$ are uniquely covered by $\mathcal {G}$. If this is at least k points then we say YES. Otherwise, ((b + 1)k)ⁱ − (l − j)((b + 1)k)^i− 1 < k. This means that bk < l − j. Therefore, $\mathcal {G}$ has at least bk hyperedges other than the hyperedges in ${\mathscr{H}}$, and the tight points of each of these hyperplanes do not belong to P. Thus, by Observation 2, there are at least k tight points in $\mathcal {G}$. Again, by b-minimality, no hyperplane of $\mathcal {G}$ could have become empty because of application of the Reduction Rule. Hence, $\mathcal {G}$ is a solution in $U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$.

On the other hand, let $\mathcal {G}^{\prime }$ be a b-minimal solution for $(U\setminus P^{\prime }, \mathcal {F} \setminus \mathcal {F}^{\prime }, k)$. Assume $\mathcal {G}^{\prime }$ is not a solution for $(U, \mathcal {F} , k)$ but has a set $\hat {\mathcal {F}}^{\prime }$ of c hyperplanes from $\mathcal {F}_{P}$. By Induction Hypothesis, all the ((b + 1)k)ⁱ points in $P^{\prime \prime }$ are covered by a subfamily of at least (b + 1)k different hyperplanes, say ${\mathscr{H}}^{\prime }$, in $\mathcal {G}^{\prime }$. Let $\hat {\mathcal {F}} \in \mathcal {F}_{P}$ be a subfamily of j − c hyperplanes. Consider $\mathcal {G}^{\prime } \cup \hat {\mathcal {F}}$, which is clearly a set cover for $(U, \mathcal {F})$ that meets the demands of all points of U. Let $\mathcal {S} \subset \mathcal {G}^{\prime }\cup \hat {\mathcal {F}}$ be a b-minimal multicover of $(U,\mathcal {F})$. Notice that none of the hyperplanes in $\hat {\mathcal {F}}\cup \hat {\mathcal {F}}^{\prime }$ will be deleted from $\mathcal {S}$. Consider the points of $P^{\prime \prime }$. Let $\hat {P} \subseteq P^{\prime \prime }$ be the set of t points that are tight in $\mathcal {S}$. Since $\hat {\mathcal {F}} \subseteq \mathcal {S}$, $\mathcal {S}$ is still a b-minimal multicover for $U\setminus \hat {P}$. For each point in $P^{\prime \prime } \setminus \hat {P}$, since it is not tight there is a hyperplane in $\mathcal {S} \setminus (\hat {\mathcal {F}}\cup \hat {\mathcal {F}}^{\prime })$. By Induction Hypothesis, at least $\frac {((b+1)k)^{i} - t}{((b+1)k)^{i-1}} \geq bk$ hyperplanes are required to cover all the points in $P^{\prime \prime } \setminus \hat {P}$. Thus, by Observation 2, in $\mathcal {S}$ there are at least k − t tight points other than the set $\hat {P}$ of t points. Thus $\mathcal {S}$ still covers at least k points uniquely and is a solution for $(U, \mathcal {F} , k)$. Therefore $\mathcal {S}$ still covers at least k points tightly and is a solution for $(U, \mathcal {F} , k)$.

We exhaustively apply this Reduction Rule. At the end, any hyperplane contains at most ((b + 1)k)^d− 1 points for each j ∈{1,2,…,b}. Thus any hyperplane contains at most b((b + 1)k)^d− 1 points. Let $\mathcal {G}$ be a b-minimal multicover for the instance. If there are at least bk hyperplanes in $\mathcal {G}$, then due to Observation 2, we correctly say YES. Otherwise, there are at most bk hyperplanes in the set cover $\mathcal {G}$, which implies that |U|≤ (b((b + 1)k)^(d− 1)) ⋅ bk. The number of hyperplanes that can contain these points is at most (b((b + 1)k)^d)^d. Thus, we have a kernel for the problem. For the algorithm, we guess k points $P\subseteq U$ that are tightly covered by a solution and the b-minimal solution family $\mathcal {G}$ of at most bk hyperplanes that are responsible for this tight coverage. Let $\mathcal {F}^{P} = \{ H | H \in \mathcal {F}\setminus \mathcal {G}, \exists p\in P { s.t } p\in H\}$. Finally we check whether the family $\mathcal {F} \setminus \mathcal {F}^{P}$ meets the demands of all points in U. Thus the problem is FPT. □

6 Conclusion

In this paper, we looked at several variants of Set Cover, and considered the problems in different geometric settings. We settle the parameterized complexity of all these cases. It would be interesting to ask the Exact Cover question for disks, or even unit disks. Unique Set Cover for a set system of unit disks, or of unit squares is also open.