Michael Dom: Fehlerkorrektur bei Leaf-Root-Problemen

Leaf-Roots, ähnlich den Graph-Roots, sind einerseits von theoretischem Interesse und haben andererseits Anwendungen in der Biologie (Stammbaumforschung).

Ein k-Leaf-Root eines Graphs G ist ein Baum, dessen Blätter den Knoten von G entsprechen und in dem zwei Blätter genau dann eine Distanz von höchstens k haben, wenn die entsprechenden Knoten in G verbunden sind (analog zum bekannteren k-Graph-Root).

Nicht jeder Graph hat ein k-Leaf-Root für ein gegebenes k; wir zeigen eine Charakterisierung mittels verbotener Teilgraphen für Graphen, die ein 3-Leaf-Root besitzen.

Für Graphen ohne k-Leaf-Root stellt sich das Graphmodifikationsproblem CLRk: Mit möglichst wenig Kanteneinfügungen oder -löschungen soll der Graph so modifiziert werden, daß er ein k-Leaf-Root hat. Die Motivation für dieses Problem ist die Beseitigung von Fehlern in einer Datenmenge, deren Darstellung als Graph ein Leaf-Root besitzen muß. Wir entwickeln FPT-Algorithmen (d.h. Algorithmen, deren Laufzeit nur exponentiell im - möglichst kleinen - Parameter, nicht aber in der Eingabegröße ist) für das NP-vollständige Problem CLR3 und seine Varianten, wobei der Parameter die Anzahl der Kantenänderungen (Fehler der Datenmenge) ist.

Mit deutlich mehr Aufwand können wir auch eine Charakterisierung mittels verbotener Teilgraphen für Graphen mit 4-Leaf-Roots sowie FPT-Algorithmen für die CLR4-Problemvarianten finden.