Algorithmen zur Erzeugung quasiregulärer Strukturen in Graphen (AREG)

• Applicant: Professor Dr. Rolf Niedermeier (†)
• Subject Area: Theoretical Computer Science
• Term: from 2008 to 2012
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 66926305

• Final Report Year: 2013

Final Report Abstract

Ziel des Projekts AREG war die Entwicklung effizienter Algorithmen zur Detektion und Erzeugung quasiregulärer Strukturen in Graphen. Bereits in der ersten Projektphase hatten wir die Problemstellung, möglichst viele Kopien eines gegebenen Graphen in einen anderen Graphen zu packen, erschöpfend untersucht. In der zweiten Projektphase spielte das Herstellen vererbbarer Grapheigenschaften durch Knotenlöschungen eine zentrale Rolle, also das Herstellen von Grapheigenschaften, die durch verbotene induzierte Teilgraphen charakterisiert werden können. Bis heute ist eine vollständige Klassifikation, für welche verbotenen induzierten Teilgraphen das Problem festparameter-handhabbar ist und wann nicht, offen. Immerhin gelang uns eine vollständige Klassifikation, für welche verbotenen induzierten Teilgraphen die Technik der iterativen Kompression sinnvoll ist. Das Themengebiet der Herstellung vererbbarer Grapheigenschaften durch Knotenlöschung, insbesondere das von uns eingeführte Problem UNIT INTERVAL VERTEX DELETION, blieb auch über die Dauer von AREG hinaus Forschungsgegenstand anderer Arbeitsgruppen. Bei der Entwicklung von Problemkernen für Knotenlöschungsprobleme für vererbbare Grapheigenschaften stellten wir wiederholt fest, dass Approximationsalgorithmen zur Beschleunigung von Datenreduktionsregeln eingesetzt werden können. Sie ermöglichten es, manche Datenreduktionsregeln überhaupt in polynomieller Zeit oder sogar in Linearzeit auszuführen. Laufzeiteffiziente Datenreduktion, konkreter Linearzeitkernelisierung, ist weiterhin ein auch von anderen Arbeitsgruppen bearbeitetes Thema. Die Projektarbeit hielt mehrere Überraschungen bereit. Einerseits ist dies zum Beispiel die Erkenntnis, dass zum Zerstören von Kopien eines Graphen in einem größeren Graphen die gleichen algorithmischen Ansätze funktionieren wie beim Finden möglichst vieler paarweise disjunkter Kopien eines Graphen in einem größeren Graphen, wobei die Korrektheitsbeweise jedoch völlig verschieden ausfallen. Ein weiteres Überraschungsmoment stellten die stark unterschiedlichen Lösungsansätze für die verwandten Probleme s-PLEX CLUSTER VERTEX DELETION und das Finden eines größtmöglichen s-Plexes dar. Das für das Finden größtmöglicher s-Plexe sehr nützliche Problem d- BOUNDED DEGREE DELETION spielte überhaupt keine Rolle für die Lösung von s-PLEX CLUSTER VERTEX DELETION.

Publications

• A problem kernelization for graph packing. In Proceedings of the 35th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’09), volume 5404 of LNCS, pages 401–412. Springer, 2009
  Hannes Moser
  
• Fixedparameter algorithms for cluster vertex deletion. Theory of Computing Systems, 47 (1):196–217, 2010
  Falk Hüffner, Christian Komusiewicz, Hannes Moser, and Rolf Niedermeier
  
• A complexity dichotomy for finding disjoint solutions of vertex deletion problems. ACM Transactions on Computation Theory, 2(2):5, 2011
  Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier
  
• A generalization of Nemhauser and Trotter’s local optimization theorem. Journal of Computer and System Sciences, 77(6):1141–1158, 2011
  Michael R. Fellows, Jiong Guo, Hannes Moser, and Rolf Niedermeier
  
• Approximation and tidying - a problem kernel for s-plex cluster vertex deletion. Algorithmica, 62(3): 930–950
  René van Bevern, Hannes Moser, and Rolf Niedermeier
  (See online at https://doi.org/10.1007/s00453-011-9492-7)
• Exact combinatorial algorithms and experiments for finding maximum k-plexes. Journal of Combinatorial Optimization, 24(3):347–373, 2012
  Hannes Moser, Rolf Niedermeier, and Manuel Sorge
  (See online at https://doi.org/10.1007/s10878-011-9391-5)
• Interval scheduling and colorful independent sets. In Proceedings of the 23rd International Symposium on Algorithms and Computation, volume 7676 of LNCS, pages 247– 256. Springer, 2012
  René van Bevern, Matthias Mnich, Rolf Niedermeier, and Mathias Weller
  
• Towards optimal and expressive kernelization for d-hitting set. Algorithmica, 2013. Online verfügbar
  René van Bevern
  (See online at https://doi.org/10.1007/s00453-013-9774-3)