Skip to main content
main-content

Tipp

Weitere Artikel dieser Ausgabe durch Wischen aufrufen

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.

Bitte loggen Sie sich ein, um Zugang zu diesem Inhalt zu erhalten

Sie möchten Zugang zu diesem Inhalt erhalten? Dann informieren Sie sich jetzt über unsere Produkte:

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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • 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
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Umwelt
  • Maschinenbau + Werkstoffe




Testen Sie jetzt 30 Tage kostenlos.

Literatur
Über diesen Artikel

Premium Partner