Diese Ausarbeitung beschäftigt sich mit der Reduktion von Problemen auf einen Problemkern in Graphen. Es wird erläutert was ein Kern und was eine Reduktionsregel ist. Es werden verschiedene Reduktionsregeln vorgestellt um ein gegebenes Problem zu reduzieren. Anhand des Vertex Covers wird beispielhaft die Anwendung dieser Reduktionsregeln demonstriert. Mit dem Hitting-Set-Problem erweitert sich dann anschlieend das Feld der Reduktionsmöglichkeiten auf die Hypergraphen - dabei wird auch gezeigt, warum es so schwer ist, eine optimale Minimierung zu
finden. Das letzte Kapitel dagegen widmet sich den Reduktionsmöglichen mit Hilfe des Dominating-Sets. Hierbei handelt sich jedoch wieder um eine Reduktionsmöglichkeit von normalen
Graphen.
Zusammenfassung. Diese Ausarbeitung beschäftigt sich mit der Re- duktion von Problemen auf einen Problemkern in Graphen. Es wird erläutert was ein Kern und was eine Reduktionsregel ist. Es werden ver- schiedene Reduktionsregeln vorgestellt um ein gegebenes Problem zu re- duzieren. Anhand des Vertex Covers wird beispielhaft die Anwendung dieser Reduktionsregeln demonstriert. Mit dem Hitting-Set-Problem erweitert sich dann anschließend das Feld der Reduktionsmöglichkeiten auf die Hypergraphen - dabei wird auch gezeigt, warum es so schwer ist, eine optimale Minimierung zu finden. Das letzte Kapitel dagegen widmet sich den Reduktionsmöglichen mit Hilfe des Dominating-Sets. Hierbei handelt sich jedoch wieder um eine Reduktionsmöglichkeit von normalen Graphen.
1 Grundlagen
1.1 Vorwort (Parametrisierte Algorithmen FPT)
Ein Graphenproblem ist genau dann parametrisierbar (“fixed parameter tractable”), wenn ein Algorithmus existiert, der das Problem in einer Laufzeit von f (k) · p(n) löst. [1]
Hierbei ist:
- f eine beliebige berechenbare, nur von k abhängige Funktion,
- k der Parameter,
- p ein von n abhängiges Polynom,
- n die Eingabegröße (zum Beispiel Anzahl an Knoten im Graph).
1.2 Problemkernreduktion
Ziel ist es, ein gegebenes Problem in polynomieller Zeit zu vereinfachen.
Definition Problemkernreduktion: Sei L ein parametrisiertes Problem, be- stehend aus dem Eingabepaar (I, k) wobei I die Probleminstanz und k der Pa- rameter ist.
(I, k) ∈ L
Eine Reduktion auf den Problemkern ist das Ersetzen der Instanz (I, k) durch eine reduzierte Instanz (I′, k′), für die gilt:
1. k′ ≤ k
2. |I′| ≤ f (k) wobei f nur von k abhängt
3. (I, k) hat eine Lösung, genau dann wenn (I′, k′) eine Lösung hat.
Die Reduktion muss in polynomieller Zeit berechenbar sein. [3] 2
Definition Datenreduktionsregeln: Eine Datenreduktionsregel [1]ist eine Abbildung φ : (I, k) ⇒ (I′, k′) die folgende Eigenschaften erfüllt:
1. φ ist in polynominieller Zeit berechenbar
2. (I, k) ∈ L g.d.w. (I′, k′) ∈ L
3. |I| ≤ |I′| und |k′| ≤ |k|
1.3 Kurzeinführung Graph
Ein Graph G ist ein Zweitupel G = (V, E) wobei V die Menge aller Knoten und E die Menge aller Kanten ist.
Eine Kante e ist definiert als e = {u, v} wobei u, v ∈ V sind.
|V | ist die Anzahl an Knoten in G
Beispiel: |V | = 3 mit V = {a, b, c}
|E| ist die Anzahl an Kanten in G
Beispiel: |E| = 2 mit E = {{a, b}, {a, c}}
deg(v) ist der Grad des Knotens v das heißt die Anzahl aller zu v inzidenten Kanten.
N (v) ist Knotenmenge der Nachbarn von Knoten v.
2 Vertex Cover Problem
2.1 Definition Vertex Cover:
Für einen ungerichteten Graphen G = (V, E), heißt eine Knotenmenge S ⊆ V genau dann eine Knotenüberdeckung oder Vertex Cover von G, wenn für jede Kante {u, v} ∈ E mindestens einer der zwei Knoten in S liegt.
{u, v} ∈ E ⇒ u∈S ∨ v∈S
Beispiel: Gegeben sei ein ungerichteter Graph G = (V, E)
mit |V | = 11 und |E| = 14 wobei V = {a, b, c, d, e, f, g, h, i, j, k} und E = {{a, d}, {b, d}, {d, e}, {b, e}, {e, c}, {e, h}, {e, g}, {d, h}, {d, f }, {i, f }, {i, h}, {i, j}, {j, h}, {j, g}} ist.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 1. Die rot eingefärbten Knoten bilden ein Vertex Cover mit |S| = 4 und S = {d, e, i, j} (Beweis folgt später).
2.2 Parametrisierte Problemdefinition
Gegeben: Ein Graph G = (V, E) und ein Parameter k.
Gesucht: Eine Knotenmenge S ∈ V mit |S| ≤ k, sodass jede Kante in E mindestens einen ihrer Endknoten in S hat. [1]
Beispiel
Gegeben: Der obige ungerichtete Graph G = (V, E) mit |V | = 11, |E| = 14 und ein Parameter k = 4.
Gesucht: Eine Knotenmenge S ⊆ V mit |S| ≤ 4, sodass jede Kante in E mindestens einen ihrer Endknoten in S hat.
Gefunden: Ein Vertex Cover mit k = 4 (Beweis folgt), zu beachten ist das für k < 4 es keine Lösung gibt. [Beispiel siehe Abbildung 1]
2.3 Datenreduktion
Ein Verfahren zur Ermittlung eines Vertex Covers ist die Anwendung von Datenreduktionsregel. [1]
Datenreduktionsregel 1
Alle isolierten Knoten das heißt alle Knoten, die keine Nachbarknoten und des- halb keine inzidenten Kanten haben, werden aus dem Graphen entfernt wobei k gleich bleibt.
Korrektheit
Diese Regel ist korrekt, weil solche isolierten Knoten niemals Teil eines Vertex Covers sein können, da sie keine Kanten abdecken können.
Abbildung in dieser Leseprobe nicht enthalten
Abb. 2. Alle isolierten Knoten entfernen.
Datenreduktionsregel 2
Für jeden Knoten u mit deg(u) = 1 gilt:
nehme seinen Nachbarknoten v und füge v zu S (Vertex Cover) hinzu. Verringere als nächstes k um 1 (k = k − 1), nehme den Knoten v, lösche ihn und alle zu v inzidenten Kanten. [Beispiel Abbildung 3]
An diesem Beispiel [Abbildung 3] kann man sehen, dass durch die Anwendung der Reduktionsregel weitere Knoten mit Grad 1 entstehen können, auf die man diese Regel noch einmal anwenden kann. Durch Entfernen von Knoten d wurde Knoten a zu einem isolierten Knoten, diesen kann man aus G entfernen nach Reduktionsregel 1.
Korrektheit
Diese Regel ist korrekt, weil Kante e = {a, d} abgedeckt werden muss, da sonst ein Kante existiert deren beide Endknoten nicht im Vertex Cover sind. Dies ist jedoch nach Definition vom Vertex Cover ausgeschlossen. [1]
Datenreduktionsregel 3 (Buss)
Gibt es einen Knoten u mit deg(u) ≥ k + 1 nehme u in S (Vertex Cover) auf. Entferne alle zu u inzidenten Kanten sowie alle entstandenen isolierten Knoten aus dem Graphen und verringere k um 1 (k = k − 1). [3]
Als Beispiel wird auf Abbildung 3 verwiesen, da es zum gleichen Ergebnis führt, für einen Parameter k = 4 und ein Knoten d mit deg(d) = 5.
Korrektheit
Diese Regel ist korrekt, weil deg(d) ≥ k + 1 ist, das bedeutet d muss in die Lösungsmenge S aufgenommen werden. Sollte Knoten d nicht in S aufgenommen werden, so müssten alle k + 1 Nachbarknoten von d in S aufgenommen werden
Abbildung in dieser Leseprobe nicht enthalten
Abb. 3. Entferne den Nachbarknoten von a und alle seine inzidenten Kanten
um alle zu d inzidenten Kanten abzudecken. Dies ist jedoch nicht möglich, da sonst |S| > k werden würde.
Beispiel der drei Regeln
Wir suchen ein Vertex Cover mit k ≤ 4 unter Anwendung der drei Redukti- onsregeln.
Isolierte Knoten werden enfernt und k bleibt unverändert das heißt k = 4. [Ab- bildung 4]
Durch Anwendung von Regel 2 wird Knoten d in die Lösungsmenge S aufgenommen und k um 1 dekrementiert ⇒ k = 3.[Abbildung 5] Der entstandene isolierten Knoten a kann gleich mit entfernt, wobei k gleich bleibt.
-
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen. -
Laden Sie Ihre eigenen Arbeiten hoch! Geld verdienen und iPhone X gewinnen.