More efficient algorithms for polynomial-time solvable graph problems

• Applicant: Dr. André Nichterlein, since 5/2022
• Subject Area: Theoretical Computer Science
• Term: from 2017 to 2023
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 327762855

• Final Report Year: 2023

Final Report Abstract

As part of the FPTinP project, we developed a deeper understanding of the parameterized complexity of various polynomial-time solvable graph problems. For several problems described in the proposal, we published parameterized algorithms and parameterized lower bounds. In the following, we briefly discuss four main results. • We developed new methods for obtaining parameterized lower runtime bounds [P18]. Using these we could show that several, partly trivial, parameterized algorithms cannot be accelerated assuming standard hypotheses from finegrained complexity. • Preprocessing using data reduction rules proved to be very benficial for the computation of matchings of maximum cardinality or weight. The prior application of our problem kernels accelerates state-of-the-art algorithms significantly – on average by over a factor of four. • For various problems, such as the calculation of the Betweeness Centrality or maximum cardinality matching, we were able to develop so-called “adaptive” algorithms, i. e., algorithms whose running time matches the ones of currently fastest algorithms for large parameter values, but have a better worst-case complexity for small parameter values. • Despite the diameter of a graph being polynomial-time computable, we obtained running time lower bounds with exponential dependencies in the parameter.

Publications

• 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