Finde unabhängige Menge der Größe k

Algorithmus TM. Testen aller möglichen Teilmengen:

Gegeben: $G = (V, E)$ mit $n$ Knoten, $k \geq 1$ .
Problem: Finde unabhängige Menge der Größe k.

Für jede Teilmenge $X \subseteq V$ teste
Hat $X$ die Größe $k$ und gibt es kein $u, v \in X$ mit ${u, v} \in E$ und $u \neq v$ ?
Wenn ja: Gib $X$ aus.
Wenn kein geeignetes $X$ gefunden wurde, gib nein aus.

Laufzeit: Exponentiell weil $2^{n}$ Teilmengen
Warum schlecht?: Es werden alle $2^{n}$ Teilmengen von $V$ durchlaufen. Damit ist es ein Exponentialzeitalgorithmus

Algorithmus kTM. Iteriere über k-elementige Mengen

Gegeben: $G = (V, E)$ mit $n$ Knoten, $k \geq 1$ .
Problem: Finde unabhängige Menge der Größe k.

Algorithmus:

Für jede $k$ -elementige Teilmenge $X \subseteq V$ teste
Gibt es $u, v \in X$ mit ${u, v} \in E$ und $u \neq v$ ?
Wenn nein: Gib $X$ aus.
Wenn kein geeignetes $X$ gefunden wurde, gib nein aus.

Laufzeit: Im Wesentlichen Anzahl der k-elementigen Teilmengen: $(\binom{n}{k})$

Algorithmus rec-IS. Iteriere über die Knoten von $V$

Gegeben: $G = (V, E)$ mit $V = {v 0, . . ., v_{n - 1}}, k \geq 1$ .
Problem: Finde unabhängige Menge der Größe k.

Algorithmus: rufe $rec-ind (G, k, 0, \emptyset)$ auf.
Algorithmus: $rec-ind (G, k, i, X)$

Wenn $X$ unabhängige Menge $⇝$ gib $X$ aus
Falls $(n - 1) - i < k$ oder $i \geq n$ , dann gib nein zurück.
Falls $k = 0$ :
1. Wenn $X$ unabhängige Menge $⇝$ gib $X$ aus
2. Ansonsten, gib nein zurück.
Rufe rekursiv $rec-ind (G, k - 1, i + 1, X \cup {v_{i}})$ auf.
1. Wenn Rückgabe Menge $X^{'}$ , gib $X^{'}$ aus.
2. Ansonsten, gib das Ergebnis von $rec-ind (G, k, i + 1, X)$

Laufzeit: Rekursion: $L (n, k) = L (n - 1, k - 1) + L (n - 1, k)$