Proseminar Parametrisierte Algorithmen

Allgemeines

Parametrisierte Algorithmen stellen eine "neue" Alternative zu Heuristiken und Approximationen dar. Leider kommt es in der Praxis häufig vor, dass man ein Problem lösen will oder muss, von dem von schlauen Theoretikern gezeigt wurde, dass es NP-vollständig ist und damit vermutlich jede Hoffnung auf einen polynomiellen Algorithmus, der dieses Problem immer lösen kann, vergeblich ist. Parametrisierte Algorithmen sind eine Art solche Probleme anzufassen. Hierbei spricht man von einem fpt-Algorithmus, wenn er die Laufzeit f(k)*poly(n) hat. Dabei ist f(k) irgendeine Funktion, die nur von einem Parameter k abhängt. Das kann zum Beispiel die Anzahl von Kanten sein, der der maximale/durchschnittliche Grad der Knoten oder soetwas ungewöhnliches wie die Baumweite des Graphen. Die Möglichkeiten sind hierbei endlos. Der zweite Teil, poly(n), ist eine polynomielle Funktion, die nur von der gesamten Eingabegröße der Probleminstanz abhängt, also z.B. n und m, Anzahl der Knoten und Kanten in einem Graphen. Ein fpt-Algorithmus garantiert dabei immer eine genaue und optimale Lösung in vorher bekannter Zeit, das klingt natürlich gut. Das Problem daran ist: Manchmal existiert kein solcher Algorithmus, oder er muss noch gefunden werden. Es gibt auf diesem Feld also viel zu tun!

Themen

Im Proseminar nähern wir uns der Thematik auf zwei unterschiedliche Arten:

(1.) Eine spezielle Technik an mehreren Problemen:

- Dynamische Programmierung
Dynamische Programmierung ist vielleicht noch das bekannteste Konzept ausserhalb der Welt der Parametrisierten Algorithmen. Das Grundprinzip ist hierbei häufig benötigte Zwischenergebnisse z.B. in einer Tabelle vorzuhalten und damit aus kleineren Lösungspuzzleteilen ein größeres Puzzleteil zu errechnen. Diese Technik ist häufig Teil komplizierterer Algorithmen auf dem Weg zu einem fpt-Algorithmus.
- Distanz zur trivialen Instanz
Häufig gibt zu NP-vollständigen Problemen Gruppen, in denen das Problem doch in polynomieller Zeit lösbar ist. Planare Graphen oder Bäume gehören häufig dazu. Als Distanz könnte man beispielweise die Anzahl zu löschender Kanten sehen, damit ein nicht planarer Graph planar wird. Diese Technik führt zu fpt-Algorithmen.
- Datenreduktion
Manchmal kann man schon lokal sagen, dass etwas nie Teil der Lösung sein kann, oder immer Teil der Lösung sein muss. Datenreduktion nutzt diese Erkenntnisse aus. Man verwendet damit eine Art Preprocessing, hier aber sogar mit der Garantie, dass die verbleibende Instanz niemals eine bestimmte Größe (die von einem Parameter abhängt) überschreiten kann.
- Tiefenbeschränkter Suchbaum
Eine Technik um strukturiert den Lösungsraum nach der Lösung abzusuchen. Dabei gibt die Größe des Suchbaumes an, wie lange der Algorithmus braucht. Häufig findet kann man mithilfe dieser Technik fpt-Algorithmen finden.
- Iterative Kompression
Eine neuere und sehr interessante Technik. Hierbei baut man die Lösung sukzessive auf und bessert im aktuellen Schritt eventuelle Fehler der vergangenen Schritte aus. Da diese Verbesserungsmöglichkeiten durch einen Parameter beschränkt sind führt auch diese Technik zu fpt-Algorithmen. Sie ähnelt vom Prinzip her einer Verquickung von Datenreduktionsregeln und Induktion.


(2.) Verschiedene Techniken zu einem Problem:

- Kontrolle in Wahlsystemen
In dem Problem Kontrolle wird untersucht, ob man einen bestimmten Kandidaten bei gegebenem Wahlsystem (z.B. Plurality = Abstimmen per Handzeichen) gewinnen lassen kann, wenn man andere Kandidaten aus der Wahl ausschließt. Dabei weiß man schon vorher, wie sämtliche Wähler in jedem Fall wählen werden. Man will aber nur so wenig Kandidaten wie möglich von der Wahl ausschließen um sein Ziel zu erreichen!
- Graphen transitiv machen
Bei diesem Problem handelt es sich um ein sogenanntes Graphenmodifikationsproblem: Man hat einen Graphen, und möchte, dass dieser eine bestimmte Eigenschaft erhält, die er bislang u.U. nicht hat. Wir wünschen uns Transitivität, wenn also ein Pfad von Knoten v nach u existiert, dann soll auch eine Kante von v nach u vorhanden sein. Dafür dürfen wir (je nach Problemstellung) Kanten löschen oder hinzufügen.