Effizientere Algorithmen für polynomialzeitlösbare Graphprobleme

• Antragsteller: Dr. André Nichterlein, seit 5/2022
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2017 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 327762855

• Erstellungsjahr: 2023

Zusammenfassung der Projektergebnisse

Im Rahmen des FPTinP-Projektes entwickelten wir ein vertieftes Verständnis für die Parametrisierte Komplexität verschiedener polynomialzeitlösbarer Graphprobleme. Für etliche im Antrag beschriebenen Probleme publizierten wir parametrisierte Algorithmen und parametrisierte untere Laufzeitschranken. Nachfolgend gehen wir kurz auf vier Hauptergebnisse ein. • Wir entwickelten eine allgemeine Methoden zur Erlangung von parametrisierten unteren Laufzeitschranken [P18]. Mit diesen belegten wir, dass mehrere, zum Teil triviale, parametrisierte Algorithmen unter üblichen Annahmen nicht beschleunigt werden können. • Für die Berechnung von Matchings größtmöglicher Kardinalität bzw. Gewichts erwies sich Vorverarbeitung durch Datenreduktionsregeln als sehr vorteilhaft. Die vorherige Anwendung unserer Problemkerne beschleunigt aktuelle Algorithmen signifikant – durchschnittlich um mehr als Faktor 4. • Für verschiedene Probleme, wie z. B. der Berechnung der Betweeness Centrality oder von größtmöglichen Matchings konnten wir sogenannte „adaptive“ Algorithmen entwickeln, d. h., Algorithmen die bei großen Parameterwerten nicht langsamer als die aktuell schnellsten sind, aber bei kleinen Parameterwerten eine bessere Worst-Case-Komplexität haben. • Obwohl der Durchmesser eines Graphen polynomialzeitberechenbar ist, ergaben sich für die meisten betrachteten Parametrisierungen untere Laufzeitschranken mit exponentiellen Abhängigkeiten im Parameter.

Projektbezogene Publikationen (Auswahl)

• Listing All Maximal k-Plexes in Temporal Graphs. ACM Journal of Experimental Algorithmics, 24, 1-27.
  Bentert, Matthias; Himmel, Anne-Sophie; Molter, Hendrik; Morik, Marco; Niedermeier, Rolf & Saitenmacher, René
  
• An Adaptive Version of Brandes' Algorithm for Betweenness Centrality. Journal of Graph Algorithms and Applications, 24(3), 483-522.
  Bentert, Matthias; Dittmann, Alexander; Kellerhals, Leon; Nichterlein, André & Niedermeier, Rolf
  
• Efficient computation of optimal temporal walks under waiting-time constraints. Applied Network Science, 5(1).
  Bentert, Matthias; Himmel, Anne-Sophie; Nichterlein, André & Niedermeier, Rolf
  
• Data Reduction for Maximum Matching on Real-World Graphs. ACM Journal of Experimental Algorithmics, 26, 1-30.
  Koana, Tomohiro; Korenwein, Viatcheslav; Nichterlein, André; Niedermeier, Rolf & Zschoche, Philipp
  
• Detecting and enumerating small induced subgraphs in c-closed graphs. Discrete Applied Mathematics, 302, 198-207.
  Koana, Tomohiro & Nichterlein, André
  
• Finding Temporal Paths Under Waiting Time Constraints. Algorithmica, 83(9), 2754-2802.
  Casteigts, Arnaud; Himmel, Anne-Sophie; Molter, Hendrik & Zschoche, Philipp
  
• Multistage graph problems on a global budget. Theoretical Computer Science, 868, 46-64.
  Heeger, Klaus; Himmel, Anne-Sophie; Kammer, Frank; Niedermeier, Rolf; Renken, Malte & Sajenko, Andrej
  
• On 2-Clubs in Graph-Based Data Clustering: Theory and Algorithm Engineering. Journal of Graph Algorithms and Applications, 25(1), 521-547.
  Figiel, Aleksander; Himmel, Anne-Sophie; Nichterlein, André & Niedermeier, Rolf
  
• A refined complexity analysis of fair districting over graphs. Autonomous Agents and Multi-Agent Systems, 37(1).
  Boehmer, Niclas; Koana, Tomohiro & Niedermeier, Rolf
  
• Deepening the (Parameterized) Complexity Analysis of Incremental Stable Matching Problems. In: Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science, MFCS 2022. Bd. 241. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022, 21:1–21:15.
  N. Boehmer, K. Heeger & R. Niedermeier
  
• Exploiting c-Closure in Kernelization Algorithms for Graph Problems. SIAM Journal on Discrete Mathematics, 36(4), 2798-2821.
  Koana, Tomohiro; Komusiewicz, Christian & Sommer, Frank
  
• Parameterized Complexity of Diameter. Algorithmica, 85(2), 325-351.
  Bentert, Matthias & Nichterlein, André
  
• Parameterized Complexity of Geodetic Set. Journal of Graph Algorithms and Applications, 26(4), 401-419.
  Kellerhals, Leon & Koana, Tomohiro
  
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters. Information and Computation, 289, 104943.
  Bredereck, Robert; Heeger, Klaus; Knop, Dušan & Niedermeier, Rolf
  
• Stable Matching with Multilayer Approval Preferences: Approvals Can Be Harder Than Strict Preferences. Lecture Notes in Computer Science, 436-453. Springer International Publishing.
  Bentert, Matthias; Boehmer, Niclas; Heeger, Klaus & Koana, Tomohiro
  
• Theory of and Experiments on Minimally Invasive Stability Preservation in Changing Two-Sided Matching Markets. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 4851-4858.
  Boehmer, Niclas; Heeger, Klaus & Niedermeier, Rolf
  
• Computing Dense and Sparse Subgraphs of Weakly Closed Graphs. Algorithmica, 85(7), 2156-2187.
  Koana, Tomohiro; Komusiewicz, Christian & Sommer, Frank
  
• Fully Polynomial-Time Algorithms Parameterized by Vertex Integrity Using Fast Matrix Multiplication. In: Proceedings of the 31st Annual European Symposium on Algorithms, ESA 2023. Bd. 274. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
  M. Bentert, K. Heeger & T. Koana
  
• Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions. In: Proceedings of the 40th International Symposium on Theoretical Aspects of Computer Science, STACS 2023. Bd. 254. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum.
  K. Heeger, A. Nichterlein & R. Niedermeier
  
• The complexity of gerrymandering over graphs: Paths and trees. Discrete Applied Mathematics, 324, 103-112.
  Bentert, Matthias; Koana, Tomohiro & Niedermeier, Rolf
  
• A Map of Diverse Synthetic Stable Matching Instances. Journal of Artificial Intelligence Research, 79, 1113-1166.
  Boehmer Niclas; Heeger Klaus & Szufa Stanisław
  
• Fast Parameterized Preprocessing for Polynomial-Time Solvable Graph Problems. Communications of the ACM, 67(4), 70-79.
  Himmel, Anne-Sophie; Mertzios, George B.; Nichterlein, André & Niedermeier, Rolf
  
• Multivariate algorithmics for eliminating envy by donating goods. Autonomous Agents and Multi-Agent Systems, 38(2).
  Boehmer Niclas; Bredereck Robert; Heeger Klaus; Knop Dušan & Luo Junjie
  
• Popular matchings with weighted voters. Games and Economic Behavior, 144, 300-328.
  Heeger, Klaus & Cseh, Ágnes
  
• Adapting stable matchings to forced and forbidden pairs. Journal of Computer and System Sciences, 147, 103579.
  Boehmer Niclas & Heeger Klaus