Entscheidungs- und Optimierungsprobleme für Graphen mit gegebener Baumzerlegung

• Applicant: Professor Dr. Peter Rossmanith
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2015
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 77821027

Es gibt eine große Anzahl NP-schwerer, graphentheoretischer Probleme, die man in der Praxis exakt lösen muß. Vielen dieser Probleme ist gemein, daß sie für allgemeine Graphen zwar schwer, für Bäume oder baumähnliche Graphen allerdings leicht bzw. leichter lösbar sind. Bruno Courcelle hat gezeigt, daß alle Probleme, die in einer monadischen Logik zweiter Stufe formulierbar sind, auf Graphen mit beschränkter Baumweite in linearer Zeit gelöst werden k¨onnen. Allerdings führte dieser Beweis bisher nicht zu praktisch verwendbaren Algorithmen. Das hier vorgestellte Projekt zielt in erster Linie darauf ab, diese Lücke zu schließen: Unsere Vorarbeiten liefern einen neuen Beweis, der nicht auf Baumautomaten beruht, sondern einen direkteren, näher am Graphen orientierten Ansatz verfolgt, jedoch bisher nur für eine eingeschränkte Logik anwendbar ist. Zunächst soll dieser Beweis verfeinert und auf die volle Logik erweitert werden. Der wesentliche Forschungsgegenstand soll in der weiteren Verbesserung unseres Verfahrens liegen, mit dem Ziel, ein praktisch nutzbares Werkzeug zu entwickeln. Aufgrund der Ausdrucksstärke der monadischen Prädikatenlogik zweiter Stufe wäre ein solches Werkzeug für fast alle Entscheidungs- und Optimierungsprobleme für Graphen anwendbar.

• DFG Programme: Research Grants