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

• Erstellungsjahr: 2013

Zusammenfassung der Projektergebnisse

DARE hat im Bereich der effizienten Vorverarbeitung durch Erforschung neuer Themen und Betrachtung praxisnaher Probleme neue Entwicklungen angestoßen. Zum einen ist hier insbesondere die Beschäftigung mit strukturellen (Nichtstandard-) Parametern zu nennen, bezüglich derer wir und die holländische Arbeitsgruppe um Dr. Hans Bodlaender (die im Bereich der Kernelisierung in der jungen Vergangenheit viel bewegt hat) erste Kernelisierungsresultate veröffentlichen konnten. Zum anderen können wir uns die (aus praktischen Gründen) neuerdings stärkere Fokussierung auf Linearzeitvorverarbeitung im Bereich der parametrisierten Algorithmik zumindest teilweise zuschreiben. Wie bereits festgestellt ist eines der besonderen Merkmale unserer Arbeitsgruppe die Untersuchung praxisnaher Probleme. So ist es uns auch möglich durch Besuch von Konferenzen, bei denen Theoretische Informatik nicht im Vordergrund steht, das Gebiet der parametrisierten Algorithmik und dessen Möglichkeiten in vielen Anwendungsfeldern sichtbar zu machen. Dies gilt besonders für effiziente Vorverarbeitung, da diese als eines der wichtigsten „Exportgüter“ unseres Arbeitsfeldes gilt. So erzielen unsere Arbeiten in Bereichen wie Wahlsystemen, sozialen Netzwerken, Graph-Layout, Bioinformatik sowie Stahlverarbeitung und Routenplanung Aufmerksamkeit, was sich im letzteren Fall sogar in einer Einladung zum Schreiben eines Buchkapitels über die Komplexität von sogenannten „Arc-Routing“ Problemen zeigt. Weiterhin soll hier auf die erhöhte Benutzerfreundlichkeit unserer Software, sowie deren Verfügbarkeit hingewiesen werden. Im Falle der Implementierung unserer Ergebnisse zum EULERIAN EXTENSION Problem haben wir die Initiative ergriffen und eine Zusammenarbeit mit der BSR angestoßen, von der wir erwarten, dass sie noch Früchte trägt: Zum einen profitieren wir von realen Daten zum Testen unserer Algorithmen, zum anderen liefern wir optimierte Routen für die Planung von Kehrmaschienenrouten sowie sogenannten „Kontrollfahrten“ (Fahrten zum Testen des Glättegrades zum Beispiel auf Brücken). Einige der Vorhaben aus den Anträgen zu DARE konnten wir allerdings nicht verwirklichen. So steht für die Erschaffung einer Reduktionsdatenbank mit unseren Anforderungen einfach keine ausgereifte Software zur Verfügung. Desweiteren hat sich das Interesse und die Expertise der in DARE Beschäftigten von einer automatisierten Reduktionsregelerzeugung zu eher theoretischen Aspekten von Vorverarbeitung wegentwickelt. Wie im Falle von CLIQUE COVER sind uns gelegentlich auch andere Arbeitsgruppen einfach zuvorgekommen, sodass unsere Überlegungen teilweise überholt wurden.

Projektbezogene Publikationen (Auswahl)

• Fixed-parameter algorithms for Kemeny rankings. Theoretical Computer Science, 410(45):4554–4570, 2009
  N. Betzler, M. R. Fellows, J. Guo, R. Niedermeier, and F. A. Rosamond
  
• Separator-based data reduction for signed graph balancing. Journal of Combinatorial Optimization, 20(4):335–360, 2010
  F. Hüffner, N. Betzler, and R. Niedermeier.
  
• Linear-time computation of a linear problem kernel for dominating set on planar graphs. In Proceedings of the 6th International Symposium on Parameterized and Exact Computation (IPEC ’11), pages 194–206
  R. van Bevern, S. Hartung, F. Kammer, R. Niedermeier, and M. Weller
  
• On the parameterized complexity of consensus clustering. In Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC ’11), volume 7074 of Lecture Notes in Computer Science, pages 624–633, Springer 2011
  M. Dörnfelder, J. Guo, C. Komusiewicz, and M. Weller.
  
• An improved branching algorithm for two-layer planarization parameterized by the feedback edge set number. In Proceedings of the 12th International Symposium on Experimental Algorithms (SEA ’13), volume 7933 of Lecture Notes in Computer Science, pages 337– 353, Springer 2013
  M. Weller
  
• Confluence in data reduction: bridging graph transformation and kernelization. Computability, 2(1):31–49, 2013
  H. Ehrig, C. Ermel, F.Hüffner, R. Niedermeier, O. Runge
  
• On tractable cases of target set selection. Social Network Analysis and Mining, 3(2):233–256, 2013
  A. Nichterlein, R. Niedermeier, J. Uhlmann, and M. Weller.
  
• Two-layer planarization parameterized by feedback edge set. Theoretical Computer Science, 494:99–111, 2013
  J. Uhlmann and M. Weller