Datenreduktion und Problemkerne

• Antragsteller: Professor Dr. Jiong Guo; Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2012
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 43721172

Ziel des Projekts DARE ist die Entwicklung von in Polynomzeit ausführbaren Datenreduktionsregeln zur Gewinnung von Problemkernen für NP-schwere, parametrisierte Probleme. Dabei versteht man unter einem Problemkern eine zur Ursprungsinstanz äquivalente Instanz, deren Größe jedoch allein durch eine Funktion des Parameters beschränkt ist. Besonders wünschenswert sind Problemkerne polynomieller oder sogar linearer Größe. Mit dem Konzept der Problemkerne besteht erstmals ein theoretisch fundierter Zugang zur Analyse der Wirksamkeit von Datenreduktionsregeln und Preprocessing, ein wichtiger Ansatz zur Lösung NP-schwerer Probleme. Die „Problemkernalgorithmik“ hat sich in wenigen Jahren zu einem herausragend wichtigen Teilgebiet der parametrisierten Algorithmik gemausert. Die Antragsteller haben hierzu einen wesentlichen Beitrag geleistet und wollen diese erfolgreiche, international sichtbare Arbeit auf möglichst breiter Basis fortführen und ausbauen. Es gilt, die Pioniertage dieses auch außerhalb der parametrisierten Algorithmik sehr heißen und immer populärer werdenden Themas mitzugestalten. Das Projekt DARE soll hierfür das Fundament bilden.

• DFG-Verfahren: Sachbeihilfen