Unique Covering Problems with Geometric Sets

The

Exact Cover

problem takes a universe

U

of

n

elements, a family

$$\mathcal F $$

F

of

m

subsets of

U

and a positive integer

k

, and decides whether there exists a subfamily(set cover)

$$\mathcal F '$$

F

′

of size at most

k

such that each element is covered by exactly one set. The

Unique Cover

problem also takes the same input and decides whether there is a subfamily

$$\mathcal F ' \subseteq \mathcal F $$

F

′

⊆

F

such that at least

k

of the elements

$$\mathcal F '$$

F

′

covers are covered uniquely(by exactly one set). Both these problems are known to be NP-complete. In the parameterized setting, when parameterized by

k

,

Exact Cover

is W[1]-hard. While

Unique Cover

is FPT under the same parameter, it is known to not admit a polynomial kernel under standard complexity-theoretic assumptions.

In this paper, we investigate these two problems under the assumption that every set satisfies a given geometric property

$$\Pi $$

Π

. Specifically, we consider the universe to be a set of

n

points in a real space

$${\mathbb R}^d$$

R

d

,

d

being a positive integer. When

$$d = 2$$

d

=

2

we consider the problem when

$$\Pi $$

Π

requires all sets to be unit squares or lines. When

$$d >2$$

d

>

2

, we consider the problem where

$$\Pi $$

Π

requires all sets to be hyperplanes in

$${\mathbb R}^d$$

R

d

. These special versions of the problems are also known to be NP-complete. When parameterizing by

k

, the

Unique Cover

problem has a polynomial size kernel for all the above geometric versions. The

Exact Cover

problem turns out to be W[1]-hard for squares, but FPT for lines and hyperplanes. Further, we also consider the

Unique Set Cover

problem, which takes the same input and decides whether there is a set cover which covers at least

k

elements uniquely. To the best of our knowledge, this is a new problem, 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 abstract setting, when parameterized by

k

. However, when we restrict ourselves to the lines and hyperplanes versions, we obtain FPT algorithms.