main-content

21.07.2021

# Exact Multi-Covering Problems with Geometric Sets

Zeitschrift:
Theory of Computing Systems
Autoren:
Pradeesha Ashok, Sudeshna Kolay, Neeldhara Misra, Saket Saurabh
Wichtige Hinweise
A preliminary version of this paper has appeared in 21st International Computing and Combinatorics Conference (COCOON 2015).

## Publisher’s Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## 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 uU 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: uU 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 uU is covered by at least dem(u) sets and at least k elements satisfy the following property: uU 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.

### Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

• über 69.000 Bücher
• über 500 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien
• Elektrotechnik + Elektronik
• Energie + Umwelt
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Maschinenbau + Werkstoffe
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

• über 58.000 Bücher
• über 300 Zeitschriften

aus folgenden Fachgebieten:

• Bauwesen + Immobilien
• Finance + Banking
• Management + Führung
• Marketing + Vertrieb
• Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

### Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

• über 50.000 Bücher
• über 380 Zeitschriften

aus folgenden Fachgebieten:

• Automobil + Motoren
• Bauwesen + Immobilien