Hitting-Set-Problem

Hitting-Set-Problem

Das Hitting-Set-Problem ist ein NP-vollständiges Problem aus der Mengentheorie.

Es gehört zur Liste der 21 klassischen NP-vollständigen Probleme von denen Richard M. Karp 1972 die Zugehörigkeit zu dieser Klasse zeigen konnte.

Gegeben ist eine Menge von Teilmengen S eines „Universums“ T, gesucht ist eine Teilmenge H von T so, dass jede Menge in S mindestens ein Element aus H enthält. Zusätzlich ist gefordert, dass die Anzahl der Elemente von H einen gegebenen Wert k nicht überschreitet.

Inhaltsverzeichnis

Formale Definition

Gegeben sind

  • eine Kollektion von Mengen \{ S_1, S_2,\ldots , S_n \}, wobei jedes Si eine Teilmenge von T ist und
  • eine positive ganze Zahl k \leq \vert T \vert .

Die Aufgabe besteht darin festzustellen, ob eine Teilmenge H von T so existiert, dass die beiden Bedingungen |H| \le k und H \cap S_i \ne \emptyset für jedes i\in\{1,2,\dots n\} erfüllt sind.

NP-Vollständigkeit

Es kann gezeigt werden, dass das Hitting-Set-Problem NP-vollständig ist, indem das Knotenüberdeckungsproblem (Vertex Cover Problem) darauf reduziert wird.

Beweis

Es sei \langle G,k \rangle eine Instanz des Knotenüberdeckungsproblems und G = (V,E).

Wir setzen T = V und fügen für jede Kante (u, v) \in E eine Menge {u,v} zur Kollektion hinzu.

Nun zeigen wir, dass es ein Hitting Set H der Größe k genau dann gibt, wenn G eine Knotenüberdeckung C der Größe k hat.

(\Rightarrow) Angenommen, es gibt ein Hitting Set H der Größe k. Da H mindestens einen Endpunkt jeder Kante enthält, ergibt sich mit C = H eine Knotenüberdeckung der Größe k.

(\Leftarrow) Angenommen, es gibt eine Knotenüberdeckung C für G der Größe k. Für jede Kante (u,v) ist u \in C oder v \in C (oder beides). Mit H = C ergibt sich somit ein Hitting Set der Größe k.

Literatur

  • Richard M. Karp: Reducibility Among Combinatorial Problems. In: R. E. Miller, J. W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York 1972, S. 85–103.

Wikimedia Foundation.

Игры ⚽ Поможем написать курсовую

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Hitting set — The hitting set problem is an NP complete problem in set theory.For a given list of sets, a hitting set is a set of elements so that each set in the given list is touched by the hitting set.In the hitting set problem, the task is to find a small… …   Wikipedia

  • Hitting set — Dieser Artikel oder Abschnitt ist nicht hinreichend mit Belegen (Literatur, Webseiten oder Einzelnachweisen) versehen. Die fraglichen Angaben werden daher möglicherweise demnächst gelöscht. Hilf Wikipedia, indem du die Angaben recherchierst und… …   Deutsch Wikipedia

  • K-approximation of k-hitting set — In computer science, k approximation of k hitting set is an approximation algorithm for weighted hitting set. The input is a collection S of subsets of some universe T and a mapping W from S to non negative numbers called the weights of the… …   Wikipedia

  • Set cover problem — The set covering problem is a classical question in computer science and complexity theory. As input you are given several sets. They may have some elements in common. You must select a minimum number of these sets so that the sets you have… …   Wikipedia

  • Problem der exakten Überdeckung — Das Problem der exakten Überdeckung (englisch Exact Cover) ist ein Entscheidungsproblem der Kombinatorik. Es gehört zu den 21 klassischen NP vollständigen Problemen, von denen Richard M. Karp 1972 gezeigt hat, dass sie NP vollständig sind.… …   Deutsch Wikipedia

  • Covering problem — In combinatorics and computer science, covering problems are computational problems that ask whether a certain combinatorial structure covers another, or how large the structure has to be to do that. Covering problems are minimization problems… …   Wikipedia

  • set — 1 /set/ verb past tense and past participle set PUT DOWN 1 PUT (transitive always + adv/prep) to carefully put something down somewhere, especially something that is difficult to carry: set sth down/on etc: She set the tray down on a table next… …   Longman dictionary of contemporary English

  • Vertex cover problem — In computer science, the vertex cover problem or node cover problem is an NP complete problem and was one of Karp s 21 NP complete problems. It is often used in complexity theory to prove NP hardness of more complicated problems. Definition A… …   Wikipedia

  • Feedback Vertex Set — Der Begriff Feedback Vertex Set bzw. kreiskritische Knotenmenge bezeichnet in der Komplexitätstheorie ein graphentheoretisches Entscheidungsproblem, das NP vollständig ist. Definition Es fragt, ob es zu einem ungerichteten Multigraphen G = (V,E) …   Deutsch Wikipedia

  • Phase problem — The phase problem is the name given to the problem of loss of information (the phase) from a physical measurement. The name itself comes from the field of x ray crystallography, where the phase problem has to be solved for the determination of a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”