LAUSR

The b - Exact Multicover problem takes a universe U of n elements, a family F $\mathcal {F}$ of m subsets of U , a function dem : U → { 1 , … , b } ${\textsf {dem}}: U \rightarrow \{1,\ldots ,b\}$ and a positive integer k , and decides whether there exists a subfamily(set cover) F ′ $\mathcal {F}^{\prime }$ of size at most k such that each element u ∈ U is covered by exactly dem ( u ) sets of F ′ $\mathcal {F}^{\prime }$ . The b - Exact Coverage problem also takes the same input and decides whether there is a subfamily F ′ ⊆ F $\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 F ′ $\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 ℝ d $\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 ℝ d $\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 F ′ $\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 F ′ $\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.