Zahlreiche kombinatorische Probleme können auf Bäumen effizient gelöst werden. Mithilfe von Width-Parametern, die die "Baumartigkeit" von Strukturen quantitativ fassen, können Algorithmen für Bäume auf beliebige Eingaben verallgemeinert werden. Diese Algorithmen sind effizient, solange der zugehörige Width-Parameter klein ist.
Diese Lehrveranstaltungen soll einen Überblick über gängige Width-Parametern für Graphen und Hypergraphen und deren Anwendungen in Künstlicher Intelligenz und Datenbanktheorie geben. Zunächst werden Graphenparameter wie Baumweite und Verallgemeinerungen wie Clique-Width und Rank-Width vorgestellt. In weiterer Folge werden wir uns Parametern für Hypergraphen widmen, inbesondere Hypertree-Width und fractional Hypertree-Width.
Zudem werden wir auf Anwendungen von Width-Parametern für verschiedene Probleme eingehen, wie etwas das Zählen aussagenlogischer Modelle, die Auswertung von Conjunctive Queries, und probabilistisches Schließen in Bayes’sches Netzen.
- Jörg Flum, Martin Grohe: Parameterized Complexity Theory. Texts in Theoretical Computer Science. An EATCS Series, Springer 2006.
- Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algorithms. Springer 2015.
