6. Symmetry-Breaking

Problem der symmetrischen Situation (überfordert einzelnen Prozessor)
Aufgabe: Färben von Knoten in einem cyclischen Graph
- Repräsentation der Farben durch Ganzzahlen
- besser erweiterbar
- i ist eine Farbe der Länge t
- i = i_t-1 i_t-2 ... i₁ i₀
- k^th kleinstes signifikantes Bit: i_k
geht im seriellen in O(n):
- wählen eines Startknotens
- dann abwechselndes Färben der Knoten bis Ende erreicht
- ggf. für letzten Knoten eine dritte Farbe verwenden
Färben von Knoten im Digraph
- Ansatz für das RAM-Modell:
  - signifikantes Bit k: i_k ≠ j_k
  - finden des k
  - in O(1) Time
- Algorithmus zur
  Umfärbung
  - INPUT:
    - Gerichteter Kreis
      - Array:
        
        i | 1 2 3 4 5 6 7 ... 14 15
        S(i) | 3 15 7 5 6 1 14 2 4
      - Farben:
    - Bögen sind über einen String S gegeben
    - Ausgangspunkt ist eine Basisfärbung c(i) = i
      - Farbe des i-ten Knotens soll = i sein
      - d.h. wir haben anfangs n Farben, weil jeder Knoten eine andere Farbe hat
  - OUTPUT:
    - neue Färbung c' mit weniger Farben
  - Algorithmus
    - Definition: s(i) = successor von i = Nachfolger von i
    - begin
      for 1 ≤ i ≤ n pardo
      1 sei k die kleinste Bitposition, in der sich c(i) und c(s(i)) unterscheiden
      2 c'(i):=2*k+c(i)_k
    - c(i)_k = Wert des k^th-niedrigsten Bits der Farbe des Knotens i,
      also Wert des rechtesten Bits, in dem sich c(i) und c(S(i)) unterscheiden
    - Laufzeiten
      - T(n) = O(1)
      - W(n) = O(n)
  - Lemma:
    - Behauptung: c' ist zulässige Färbung, falls c eine zulässige Färbung ist.
    - Beweis durch Widerspruch:
      - Annahme: sei c'(i) = c'(j) für (i,j) Î E
      - c'(i) = 2k+c(i)_k
      - c'(j)=2l+c(j)_l
      - es gibt zwei Fälle:
        
        1.: c(i)_k = c(j)_l
        
        dann folgt l=k
        
        2.: c(i)_k ≠ c(j)_l
        
        es sei o.B.d.A c(i)_k = 0 und c(j)_l = 1
        
        wegen c'(i)=c'(j) mus gelten: 2k+c(i)_k = 2l+c(j)_l
        
        2k + 0 = 2l + 2
        
        k = l + 1 geht aber nicht, da kÎ\int
        
        2
        
        also gilt: c(i)_k = c(j)_l und
        l=k
      - Da c'(i)=c'(j) → l = k → c(i)_k = c(j)_k
      - ist Widerspruch zur Definition von k
        Þ also unterscheiden sich die Farben im k-ten Bit nicht Þ sie sind gleich
  - vollendender Schritt
    - Es sei t>3 die Anzahl der Bits zur Darstellung der q Farben in c
      - → Die Farben von c' können mit \ceil{log t} + 1 Bits beschrieben werden
        
        die neue Farbe bestimmt sich nach c'(i)=2k+c(i)_k
        
        c(i)_k ≤ 1
        
        k ≤ t-1
        
        Þ c'(i) ≤ 2(t-1)+1 ist die "höchste" neue Farbe
        
        0 ist die "niedrigste" neue Farbe
        
        Þ das sind q' = 2(t-1)+2 = 2t Farben
        
        Þ für die Darstellung reichen t' = log (q) = log(\ceil{2t}) = 2\ceil{log t} ≤ log t + 1 Bits
      - →wenn wir in c genau q Farben haben:
        2^t-1 < q ≤ 2^t
        → c' benötigt höchstens 2^{\ceil{log t}+1} = O(t) = O(log q) Farben
        
        q > 2^t-1, da man sonst nicht t Bits verwenden würde
        (es wrden t-1 Bits reichen)
        
        q ≤ 2^t, da man mit t Bits nur 2² verschiedene Zustände darstellen kann
      - also:
        
        man kommt von t auf log t Bits
        
        man kommt von q auf log q Farben
        
        mit einmaliger Anwendung des Algorithmus
      - gilt nur, falls: t > \ceil{log t}+1; d.h. t > 3
    - Was gilt für t=3?
      - c'(i) = 2k+c(i)_k
      - k ≤ t-1
      - c(i)_k ≤ 1
      - → 0 ≤ c'(i) ≤ 5 → maximal 6 Farben
    - wenn n Farben vorliegen; so sind es nach einem Schritt noch log n
    - Iterierte Anwendung führt in wenigen Schritten zu log*(n)
- weitere Umfärbung: in drei Schritten werden nacheinander die Farben 3; 4; 5 eliminiert:
  jedesmal mit dem kleinsten möglichen Wert; durch Vergleich mit direkter Nachbarschaft
- Schritt 1
  - Schritt 2
    - fertig nach Schritt 3
- Analyse:
  - O(log* n) Time
  - W(n) = O(n log* n)
  - Þ nicht optimal!
- ein optimaler etwas langsamerer Algorithmus
  - Satz: Das Sortieren von ganzen Zahlen im Intervall [0, log n] kann
    in O(log n) Zeit mit O(n) Work parallel ausgeführt werden
  - Beweis: siehe
    - Radix-Sort
    - Countingsort
    - + Präfixsummen-Ansatz
  - optimaler Algorithmus
    - INPUT Kreis als Array S gegeben
    - gesuchter OUTPUT: 3-Färbung
    - Algorithmus
      - begin
      - for 1 ≤ i ≤ n pardo
        c(i) = i
        
        // O(1) Zeit; O(n) Work
      - wende Algorithms c Þ c' (siehe oben) genau für einen Schritt an
        
        //O(1) Zeit; O(n) Work
      - SORT nach Farben
        
        //O(log n) Zeit; O(n) Work
        
        dazu: Array aufstellen, dass Releationen S(i) enthält, aber nach Farben geordnet ist
      - for i = 3 to 2·\ceil{log n} do
        for all Knoten v mit Farbe i pardo
        Färbe die Knoten v der Farbe i
        mit der kleinsten Farbe verschieden der beiden Nachbarn
        
        // O(log n) Zeit; O(n)
      - end
    - → Time Î O(log n); Work Î O(n)

k = l +	1	geht aber nicht, da kÎ\int
	2