Generic programming for graph problems using tree decompositions

Abstract

Tree decompositions have been an increasingly useful tool for solving prob- lems on graphs due to the important algorithmic properties of the class of graphs of bounded treewidth. An important theorem by Courcelle [Cou90] stated that properties definable in MSO logic can be decided in linear time on graphs of bounded treewidth. This provided a theoretical base which re- vealed tractability of many graph problems, intractable in the general case, for the aforementioned class of graphs and instigated many algorithms solv- ing MSO-definable problems. Bodlaender proposed a dynamic programming approach to designing algorithms using tree decompositions [Bod97]. The approach encompassed several of the algorithms already invented, but was also used as a method for the construction of new ones for a variety of graph problems. In this thesis we studied and implemented this approach, delivering a sys- tem that operates using plug-ins to describe the specific parts of algorithms using Bodlaender's method. Furthermore we implemented a 3 colouring algorithm as a plug-in for the system in order to assess its usability and efficiency.

Tree decomposition hat eine zunehmende Bedeutung als Werkzeug zur Lösung von Graphenproblemen, bedingt durch wichtige algorithmische Eigenschaften der Klasse der Graphen mit beschränkter treewidth. Ein wichtiges Theo- rem von Courcelle [Cou90] besagt, dass Eigenschaften eines Graphen die in MSO Logik beschrieben werden können, in linearer Zeit für Graphen mit beschränkter treewidth entschieden werden können. Dies gibt den theoretis- chen Hintergrund für die tractability vieler Graphenprobleme, intractability im Allgemeinen und für die oben erwähnte Graphenklasse regte es zu vie- len Algorithmen für MSO-definierbaren Problemen an. Bodlaender schlägt in [Bod97] einen Ansatz vor zum Design von Algorithmen mittels dynamis- cher Programmierung unter der Verwendung von tree decomposition. Dieser Ansatz stellt eine verallgemeinerte Methode vor, mittels der sich auch bereits vor dieser Arbeit vorgestellte Algorithmen entwerfen hätten lassen, wichtiger jedoch diese Methode kann verwendet werden um neue Algorithmen für eine Vielzahl von Graphenproblemen zu konstruieren. In dieser Diplomarbeit haben wir diesen Ansatz untersucht und imple- mentiert. Das Ergebnis ist ein System, das Bodlaender's Methode ver- wendet und das es erlaubt spezifische Teile des Algorithmuses mittels Plu- gins zu beschreiben. Um die Verwendbarkeit und Effizienz des Systems einzuschätzen haben wir einen Algorithmus für Dreifärbung als Plugin im- plementiert.