Anki Deck Changes

Konsequenz: Long-Path ist mindestens so schwer wie Hamiltonkreis, also ebenfalls NP-schwer.
Idee: Konstruiere in \(O(n^2)\) Zeit einen Graphen \(G'\) mit \(n' \leq 2n - 2\) Knoten, sodass \(G\) einen Hamiltonkreis hat \(\Leftrightarrow\) \(G'\) einen Pfad der Länge \(n\) hat.

QuickSelect(A, ℓ, r, k):
  p ← Uniform({ℓ, ℓ+1, ..., r})
  t ← Partition(A, ℓ, r, p)
  if t = ℓ + k - 1: return A[t]    # gefunden
  else if t > ℓ + k - 1:
    return QuickSelect(A, ℓ, t-1, k)     # links
  else:
    return QuickSelect(A, t+1, r, k - t) # rechts

Im Gegensatz zu QuickSort rekursiert QuickSelect nur in eine der beiden Hälften (oder gibt direkt zurück, falls Pivot bereits an der gesuchten Position liegt). Das macht den Unterschied zwischen \(O(n \log n)\) und \(O(n)\) erwartet.

Bei einem Aufruf von QuickSelect ist die Anzahl Vergleiche \(T = \sum_{i=1}^{N} (r_i - \ell_i)\), wobei \(N\) die Anzahl Partition-Aufrufe ist.

Achtung: Die Färbung muss hier nicht zulässig im üblichen Sinn sein, also benachbarte Knoten dürfen dieselbe Farbe haben. Wichtig ist nur, dass entlang eines bunten Pfades keine Farbe doppelt vorkommt.

BUNT(G, i):
  for all v in V:
    P_i(v) := empty set
    for all x in N(v):
      for all R in P_{i-1}(x) with γ(v) ∉ R:
        P_i(v) := P_i(v) ∪ { R ∪ {γ(v)} }

Initialisierung: \(P_0(v) = \{\{\gamma(v)\}\}\) für alle \(v \in V\).
Antwort JA \(\Leftrightarrow\) nach \(k-1\) Iterationen ist \(P_{k-1}(v) \neq \emptyset\) für irgendein \(v\).

Sei \(v^* \in V\) ein beliebig gewählter Knoten.
Konstruiere \(G'\) wie folgt:

1. Ersetze \(v^*\) durch zwei Kopien \(v_1^*\) und \(v_2^*\); jede Kopie erhält dieselben Nachbarn wie \(v^*\) in \(G\).
2. Hänge an \(v_1^*\) und \(v_2^*\) je einen neuen Knoten \(w_1\) bzw. \(w_2\) an (jeweils Grad 1).

Dann hat \(G'\) genau \(|V| + 1 = n + 1 \leq 2n - 2\) Knoten (für \(n \geq 3\)) und kann in \(O(n^2)\) Zeit gebaut werden.

\(\Rightarrow\): Aus einem Hamiltonkreis in \(G\) erhält man durch Aufschneiden bei \(v^*\) und Anhängen von \(w_1, w_2\) einen Pfad \(w_1 \to v_1^* \to \dots \to v_2^* \to w_2\) der Länge \(n\) in \(G'\).
\(\Leftarrow\): Ein Pfad der Länge \(n\) in \(G'\) muss bei \(w_1\) starten und bei \(w_2\) enden (oder umgekehrt) und liefert nach Verschmelzen von \(v_1^*, v_2^*\) einen Hamiltonkreis in \(G\).

Achtung: \(B\) ist die Anzahl Kanten, also hat ein Pfad der Länge \(B\) genau \(B+1\) Knoten.

Faktor \((2e)^k\) statt \(e^k\): einmalige bunte Färbung kostet \(O(2^k \cdot k \cdot m)\) (Mengen \(S \subseteq [k]\) im DP), und es werden \(\Theta(\varepsilon \cdot e^k)\) Versuche gemacht.
Bemerkung: \((2e)^k\) ist konstant in \(n\). Damit wird Long-Path für festes \(k\) in Polynomialzeit lösbar (FPT-Resultat von Alon, Yuster, Zwick 1995).

\(P_i(v)\) sammelt also alle möglichen Farbmengen, die ein bunter Pfad der Länge \(i\) ausschöpfen kann, wenn er bei \(v\) endet.
Ziel des Algorithmus: Berechne \(P_i(v)\) für alle \(v \in V\) und alle \(i \in \{0, 1, \dots, k-1\}\) per dynamischer Programmierung.
Es existiert ein bunter Pfad der Länge \(k-1\) genau dann, wenn \(P_{k-1}(v) \neq \emptyset\) für ein \(v \in V\).

Beweis von (1): \(\Pr[P \text{ wird bunt}] = \tfrac{k!}{k^k} \geq e^{-k}\) per Stirling.
Beweis von (2): geometrisch verteilte Wartezeit mit Erfolgswahrscheinlichkeit \(p\), Erwartungswert \(1/p\).

Das ist polynomiell in \(n\), aber exponentiell in \(B\): unbrauchbar, sobald \(B\) mit \(n\) wächst.
Ziel der nachfolgenden Konstruktion (Color-Coding): Laufzeit \(O(c^B)\) für eine Konstante \(c\), also unabhängig von \(n\) im Exponenten.

Idee: Ein bunter Pfad der Länge \(i\), der in \(v\) endet, entsteht aus einem bunten Pfad der Länge \(i-1\), der in einem Nachbarn \(x\) von \(v\) endet, dessen Farbmenge \(\gamma(v)\) noch nicht enthält.

Daraus folgt: Bei einer zufälligen Färbung mit \(k\) Farben ist die Wahrscheinlichkeit, dass \(P\) bunt wird, \[ p = \frac{k!}{k^k} \geq e^{-k} \] (per Stirling: \(k! \geq (k/e)^k\)).

Die Umkehrung gilt nicht: stetige Funktionen müssen nicht differenzierbar sein (z.B. \(|x|\) bei \(x_0 = 0\)).