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]
Häufig gestellte Fragen
Was ist das Ziel dieser Ausarbeitung?
Diese Ausarbeitung beschäftigt sich mit der Reduktion von Problemen auf einen Problemkern in Graphen. Es werden Kerne und Reduktionsregeln erläutert, und verschiedene Reduktionsregeln zur Vereinfachung gegebener Probleme vorgestellt. Die Anwendung dieser Regeln wird am Beispiel des Vertex Cover Problems demonstriert. Anschließend wird das Feld der Reduktionsmöglichkeiten auf Hypergraphen mit dem Hitting-Set-Problem erweitert. Abschließend werden Reduktionsmöglichkeiten mit Hilfe des Dominating-Sets für normale Graphen behandelt.
Was bedeutet "parametrisierbar" (fixed parameter tractable, FPT) in Bezug auf Graphenprobleme?
Ein Graphenproblem ist genau dann parametrisierbar, wenn ein Algorithmus existiert, der das Problem in einer Laufzeit von f(k) · p(n) löst. Dabei ist f eine beliebige berechenbare, nur von k abhängige Funktion, k der Parameter, p ein von n abhängiges Polynom und n die Eingabegröße.
Was ist eine Problemkernreduktion?
Ziel ist es, ein gegebenes Problem in polynomieller Zeit zu vereinfachen. Eine Reduktion auf den Problemkern ersetzt die Instanz (I, k) durch eine reduzierte Instanz (I′, k′), für die gilt: k′ ≤ k, |I′| ≤ f(k) (wobei f nur von k abhängt), und (I, k) hat eine Lösung, genau dann wenn (I′, k′) eine Lösung hat. Die Reduktion muss in polynomieller Zeit berechenbar sein.
Was sind Datenreduktionsregeln?
Eine Datenreduktionsregel ist eine Abbildung φ : (I, k) ⇒ (I′, k′) die folgende Eigenschaften erfüllt: φ ist in polynominieller Zeit berechenbar, (I, k) ∈ L g.d.w. (I′, k′) ∈ L, und |I| ≤ |I′| und |k′| ≤ |k|.
Wie ist ein Graph definiert?
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, und |E| ist die Anzahl an Kanten in G. deg(v) ist der Grad des Knotens v (die Anzahl aller zu v inzidenten Kanten), und N(v) ist die Knotenmenge der Nachbarn von Knoten v.
Was ist ein 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.
Wie ist das parametrisierte Vertex Cover Problem definiert?
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.
Welche Datenreduktionsregeln werden für das Vertex Cover Problem vorgestellt?
Es werden drei Datenreduktionsregeln vorgestellt:
- Regel 1: Alle isolierten Knoten werden aus dem Graphen entfernt, wobei k gleich bleibt.
- Regel 2: Für jeden Knoten u mit deg(u) = 1 wird sein Nachbarknoten v zu S hinzugefügt, k um 1 verringert, und der Knoten v sowie alle zu v inzidenten Kanten werden gelöscht.
- Regel 3 (Buss): Gibt es einen Knoten u mit deg(u) ≥ k + 1, wird u in S aufgenommen, alle zu u inzidenten Kanten sowie alle entstandenen isolierten Knoten werden aus dem Graphen entfernt, und k um 1 verringert.
Warum ist Regel 1 (Entfernen isolierter Knoten) korrekt?
Diese Regel ist korrekt, weil isolierte Knoten niemals Teil eines Vertex Covers sein können, da sie keine Kanten abdecken können.
Warum ist Regel 2 (Knoten mit Grad 1) korrekt?
Diese Regel ist korrekt, weil jede Kante e = {a, d} abgedeckt werden muss, da sonst eine Kante existiert, deren beide Endknoten nicht im Vertex Cover sind, was der Definition des Vertex Covers widerspricht.
Warum ist Regel 3 (Buss) korrekt?
Diese Regel ist korrekt, weil wenn deg(d) ≥ k + 1 ist, muss d 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, um alle zu d inzidenten Kanten abzudecken. Dies ist jedoch nicht möglich, da sonst |S| > k werden würde.
- Quote paper
- Sebastian Schäf (Author), Albert Bub (Author), 2013, Datenreduktion und Problemkerne, Munich, GRIN Verlag, https://www.hausarbeiten.de/document/214875
