Wechselwirkungen bei parametrisierter Datenreduktion

• Antragsteller: Professor Dr. Rolf Niedermeier (†)
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2022
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 389085303

Problemkernberechnungen gehören nachweislich zu den Hauptbeiträgen der parametrisierten Komplexitätsanalyse zur Algorithmik: gegeben eine Instanz eines typischerweise NP-schweren Problems, so berechnet man in polynomieller Zeit eine äquivalente Instanz, deren Größe durch eine nur vom Parameter abhängige Funktion nach oben beschränkt werden kann. Viele Problemkernberechnungen fußen auf der erschöpfenden Anwendung von Datenreduktionsregeln.Basierend auf vieljähriger Erfahrung mit verschiedensten Facetten von Problemkernberechnungen wollen wir in diesem Projekt die Entwicklung neuer Aspekte, insbesondere von Wechselwirkungen, deutlich vorantreiben. Dabei sind wir insbesondere in Wechselwirkungen von Zeiteffizienz und effektiver Problemkerngröße mit verschiedenen Qualitätsmaßen für Problemkerne. Dazu zählen Pareto-optimale Problemkerne, wobei durch Hintereinanderausführung verschiedener Kernberechnungen Beschleunigungen erzielt werden können. Weiterhin planen wir die systematische Untersuchung von Konzepten wie partielle Problemkerne, approximative und randomisierte Problemkernberechnungen und Turing-Problemkerne. All dies geschieht mit dem letztendlichen Ziel sich eine bessere Laufzeit und/oder Kerngröße durch Relaxierung des Problemkernkonzepts zu erkaufen. In diesem Kontext streben wir sowohl theoretische (inklusive neuer Methoden und unterer Schranken) und praktische (bis hin zum Algorithm Engineering) Beiträge an.Unser Schwerpunkt liegt auf NP-schweren Problemen, jedoch sollen vereinzelt auch polynomzeitlösbare Probleme untersucht werden.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Russische Föderation
• Partnerorganisation: Russian Foundation for Basic Research
• Kooperationspartner: Professor Dr. René van Bevern