www.wikidata.de-de.nina.az

Hitting Set Problem Das ist ein NP vollständiges Problem aus der Mengentheorie Es gehört zur Liste der 21 klassischen NP

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 eines „Universums“ , gesucht ist eine Teilmenge von so, dass jede Menge in mindestens ein Element aus enthält. Zusätzlich ist gefordert, dass die Anzahl der Elemente von einen gegebenen Wert nicht überschreitet.

Formale Definition Bearbeiten

Gegeben sind

  • eine Kollektion von Mengen , wobei jedes eine Teilmenge von ist und
  • eine positive ganze Zahl .

Die Aufgabe besteht darin festzustellen, ob eine Teilmenge von so existiert, dass die beiden Bedingungen und für jedes erfüllt sind.

NP-Vollständigkeit Bearbeiten

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 eine Instanz des Knotenüberdeckungsproblems und .

Wir setzen und fügen für jede Kante eine Menge zur Kollektion hinzu.

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

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

() Angenommen, es gibt eine Knotenüberdeckung für der Größe . Für jede Kante ist oder (oder beides). Mit ergibt sich somit ein Hitting Set der Größe .

Literatur Bearbeiten

  • Richard M. Karp: Reducibility Among Combinatorial Problems. In: Raymond E. Miller, James W. Thatcher (Hrsg.): Complexity of Computer Computations. Plenum Press, New York NY u. a. 1972, ISBN 0-306-30707-3, S. 85–103.
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das Hitting Set Problem ist ein NP vollstandiges Problem aus der Mengentheorie Es gehort zur Liste der 21 klassischen NP vollstandigen Probleme von denen Richard M Karp 1972 die Zugehorigkeit zu dieser Klasse zeigen konnte Gegeben ist eine Menge von Teilmengen S displaystyle S eines Universums T displaystyle T gesucht ist eine Teilmenge H displaystyle H von T displaystyle T so dass jede Menge in S displaystyle S mindestens ein Element aus H displaystyle H enthalt Zusatzlich ist gefordert dass die Anzahl der Elemente von H displaystyle H einen gegebenen Wert k displaystyle k nicht uberschreitet Formale Definition BearbeitenGegeben sind eine Kollektion von Mengen S 1 S 2 S n displaystyle S 1 S 2 ldots S n nbsp wobei jedes S i displaystyle S i nbsp eine Teilmenge von T displaystyle T nbsp ist und eine positive ganze Zahl k T displaystyle k leq vert T vert nbsp Die Aufgabe besteht darin festzustellen ob eine Teilmenge H displaystyle H nbsp von T displaystyle T nbsp so existiert dass die beiden Bedingungen H k displaystyle H leq k nbsp und H S i displaystyle H cap S i neq emptyset nbsp fur jedes i 1 2 n displaystyle i in 1 2 dotsc n nbsp erfullt sind NP Vollstandigkeit BearbeitenEs kann gezeigt werden dass das Hitting Set Problem NP vollstandig ist indem das Knotenuberdeckungsproblem Vertex Cover Problem darauf reduziert wird Beweis Es sei G k displaystyle langle G k rangle nbsp eine Instanz des Knotenuberdeckungsproblems und G V E displaystyle G V E nbsp Wir setzen T V displaystyle T V nbsp und fugen fur jede Kante u v E displaystyle u v in E nbsp eine Menge u v displaystyle u v nbsp zur Kollektion hinzu Nun zeigen wir dass es ein Hitting Set H displaystyle H nbsp der Grosse k displaystyle k nbsp genau dann gibt wenn G displaystyle G nbsp eine Knotenuberdeckung C displaystyle C nbsp der Grosse k displaystyle k nbsp hat displaystyle Rightarrow nbsp Angenommen es gibt ein Hitting Set H displaystyle H nbsp der Grosse k displaystyle k nbsp Da H displaystyle H nbsp mindestens einen Endpunkt jeder Kante enthalt ergibt sich mit C H displaystyle C H nbsp eine Knotenuberdeckung der Grosse k displaystyle k nbsp displaystyle Leftarrow nbsp Angenommen es gibt eine Knotenuberdeckung C displaystyle C nbsp fur G displaystyle G nbsp der Grosse k displaystyle k nbsp Fur jede Kante u v displaystyle u v nbsp ist u C displaystyle u in C nbsp oder v C displaystyle v in C nbsp oder beides Mit H C displaystyle H C nbsp ergibt sich somit ein Hitting Set der Grosse k displaystyle k nbsp Literatur BearbeitenRichard M Karp Reducibility Among Combinatorial Problems In Raymond E Miller James W Thatcher Hrsg Complexity of Computer Computations Plenum Press New York NY u a 1972 ISBN 0 306 30707 3 S 85 103 Karps 21 NP vollstandige Probleme Erfullbarkeitsproblem der Aussagenlogik Cliquenproblem Mengenpackungsproblem Knotenuberdeckungsproblem Mengenuberdeckungsproblem Feedback Arc Set Feedback Vertex Set Hamiltonkreisproblem Integer Linear Programming 3 SAT graph coloring problem Covering by cliques Problem der exakten Uberdeckung 3 dimensional matching Steinerbaumproblem Hitting set Rucksackproblem Job sequencing Partitionsproblem Maximaler Schnitt Abgerufen von https de wikipedia org w index php title Hitting Set Problem amp oldid 227024083