Dr. Nils Morawietz

Scientific Activities

• PC member of the 22st International Symposium on Algorithmics of Wireless Networks (ALGOWIN) 2026External link.
• PC member of the 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND) 2026External link.
• PC member of the 21st International Symposium on Algorithmics of Wireless Networks (ALGOWIN) 2025External link.

Publications

For a complete overview, please visit my Google Scholar profileExternal link, my DBLP pageExternal link, or the list below.

Conference and Journal Publications

2026

Conference Publications

• Robert Ganian, Hung P. Hoang, Christian Komusiewicz, and Nils Morawietz: A Parameterized-Complexity Framework for Finding Local OptimaExternal link. In Proceedings of the 17th Innovations in Theoretical Computer Science (ITCS'26External link), to appear.
• Justine Cauvi, Nils Morawietz and Laurent Viennot: Foremost, Fastest, Shortest: Temporal Graph Realization under Various Path MetricsExternal link. In Proceedings of the 43rd International Symposium on Theoretical Aspects of Computer Science (STACS'26External link), to appear.
• Christian Komusiewicz, Zhenwei Liu, Nils Morawietz, and Frank Sommer: Preventing Small Global Cuts by Protecting Edges. In Proceedings of the 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'26External link), to appear.
• Mario Grobler, Nils Morawietz, and Silas Cato Sacher: Towards Settling the Complexity of the Lettericity Problem. In Proceedings of the 21st Computability in Europe (CiE'26External link), to appear.
• Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt: Brief Announcement: Revisiting the Realizability of Periodic Temporal Graphs with Bounded Stretch. In Proceedings of the 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND'26External link), to appear.
• Julia Meusel, Nils Morawietz, Matthias Müller-Hannemann, and Klaus Reinhardt: Minimize the Sum of Waiting Times in Periodic Temporal Trees. In Proceedings of the 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND'26External link), to appear.
• David Ilcinkas, Nils Morawietz, and Antoine Toullalan: On sufficient conditions for short journeys in temporal graphs. In Proceedings of the 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND'26External link), to appear.
• Jessica Enright, Thomas Erlebach, Kitty Meeks, and Nils Morawietz: Robust temporal cut. In Proceedings of the 5th Symposium on Algorithmic Foundations of Dynamic Networks (SAND'26External link), to appear.

Journal Publications

• Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz, Frank Sommer, and Petra Wolf: Multi-parameter analysis of finding minors and induced subgraphs in edge-periodic temporal graphsExternal link. Discrete Applied MathematicsExternal link, 378: 102-119, 2026.
• Jaroslav Garvardt, Christian Komusiewicz, and Nils Morawietz: When Can Cluster Deletion with Bounded Weights Be Solved Efficiently?External link. Discrete Applied MathematicsExternal link, 383: 169-183, 2026.
• Jaroslav Garvardt, Nils Morawietz, André Nichterlein, and Mathias Weller: Graph Clustering Problems under the Lens of Parameterized Local SearchExternal link. Journal of Computer and System SciencesExternal link, 159: 103784, 2026.
• George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis:  Temporal Graph Realization With Bounded Stretch. Journal of Computer and System SciencesExternal link, 2026, accepted for publication.

2025

Conference Publications

• Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: Temporal Dominating Set and Temporal Vertex Cover under the Lense of Degree RestrictionsExternal link. In Proceedings of the 4th Symposium on Algorithmic Foundations of Dynamic Networks (SAND'25External link), Volume 330 of LIPIcs, pages 16:1-16:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Niels Grüttemeier, Nils Morawietz, and Frank Sommer: Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning ProblemsExternal link. In Proceedings of the 19th International Symposium on Algorithms and Data Structures (WADS'25External link), Volume 349 of LIPIcs, pages 32:1-32:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis: Realizing temporal transportation treesExternal link. In Proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'25External link), Volume 16124 of LNCS, pages 390-404, Springer.
• George B. Mertzios, Hendrik Molter, Nils Morawietz, and Paul G. Spirakis: Temporal Graph Realization With Bounded StretchExternal link. In Proceedings of the 50th International Symposium on Mathematical Foundations of Computer Science (MFCS'25External link), Volume 345 of LIPIcs, pages 75:1-75:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Thomas Erlebach, Othon Michail, Nils Morawietz: Recognizing and Realizing Temporal Reachability GraphsExternal link. In Proceedings of the 33rd Annual European Symposium on Algorithms (ESA'25External link), Volume 351 of LIPIcs, pages 93:1-93:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating SetExternal link. In Proceedings of the 20th International Symposium on Parameterized and Exact Computation (IPEC'25External link), Volume 358 of LIPIcs, pages 12:1-12:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Arnaud Casteigts, Michelle Döring, Nils Morawietz: Realization of Temporally Connected Graphs Based on Degree SequencesExternal link. In Proceedings of the 36th International Symposium on Algorithms and Computation (ISAAC'25External link), Volume 359 of LIPIcs, pages 17:1-17:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Journal Publications

• Thomas Erlebach, Nils Morawietz, and Petra Wolf: Parameterized Algorithms for Multi-Label Periodic Temporal Graph RealizationExternal link. Theoretical Computer ScienceExternal link, 2025.
• Christian Komusiewicz and Nils Morawietz: Can Local Optimality Be Used for Efficient Data Reduction?External link Theory of Computing SystemsExternal link 69:7, 2025.
• Christian Komusiewicz and Nils Morawietz: Finding 3-Swap-Optimal Independent Sets and Dominating Sets is HardExternal link. ACM Transactions on Computation TheoryExternal link: 1:1-1:31, 2025.

2024

Conference Publications

• Thomas Erlebach, Nils Morawietz, and Petra Wolf: Parameterized Algorithms for Multi-Label Periodic Temporal Graph RealizationExternal link. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND'24External link). Volume 292 of LIPIcs, pages 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik. (Best Student Paper Award)
• Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal GraphsExternal link. In Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS'24External link).  Volume 306, pages 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz, and Frank Sommer. On the Complexity of Community-Aware Network SparsificationExternal link. In Proceedings of the 49th International Symposium on Mathematical Foundations of Computer Science (MFCS'24External link).  Volume 306, pages 60:1-60:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Jaroslav Garvardt, Christian Komusiewicz, and Nils Morawietz: When Can Cluster Deletion with Bounded Weights Be Solved Efficiently?External link In Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024External link). Volume 322 of LIPIcs, pages 32:1-32:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Bodo Manthey, Nils Morawietz, Jesse van Rhijn, and Frank Sommer: Complexity of Local Search for Euclidean Clustering ProblemsExternal link. In Proceedings of the 35th International Symposium on Algorithms and Computation (ISAAC 2024External link). Volume 322 of LIPIcs, pages 48:1-48:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

Journal Publications

• Thomas Erlebach, Nils Morawietz, Jakob T. Spooner, and Petra Wolf: A cop and robber game on edge-periodic temporal graphsExternal link. Journal of Computer and System SciencesExternal link, 144: 103534, 2024.

2023

Conference Publications

• Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz, Frank Sommer, and Petra Wolf: Finding Minors and Subgraphs in Edge-Periodic Temporal GraphsExternal link. In Proceedings of the 48th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'23External link). Volume 13878 of LNCS, pages 283–297, Springer (original publicationExternal link).
• Alexander Bille, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: A Graph-Theoretic Formulation of Exploratory BlockmodelingExternal link. In Proceedings of the 21st International Symposium on Experimental Algorithms (SEA'23External link). Volume 265 of LIPIcs, pages 14:1--14:20, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: Parameterized Local Search for Max c-Cutpdf, 282 kb. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI'23External link). Pages 5586-5594, ijcai.org (original publicationExternal link).
• Jaroslav Garvardt, Nils Morawietz, André Nichterlein, and Mathias Weller: Graph Clustering Problems under the Lens of Parameterized Local SearchExternal link. In Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC'23External link). Volume 285 of LIPIcs, pages 20:1-20:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Jana Holznigenkemper, Christian Komusiewicz, Nils Morawietz, and Bernhard Seeger: On the Complexity of Computing Time Series Medians under the Move-Split-Merge MetricExternal link. In Proceedings of the 48th International Symposium on Mathematical Foundations of Computer Science (MFCS'23External link). Volume 272 of LIPIcs, pages 54:1--54:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Christian Komusiewicz, Simone Linz, Nils Morawietz, and Jannik Schestag: On the Complexity of Parameterized Local Search for the Maximum Parsimony ProblemExternal link. In 34th Annual Symposium on Combinatorial Pattern Matching (CPM'23External link). Volume 259 of LIPIcs, pages 18:1--18:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Luca Pascal Staus, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: Exact Algorithms for Group Closeness Centralitypdf, 798 kb.  In Proceedings of the 2023 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA'23External link). Pages 1-12, SIAM (original publicationExternal link).

2022

Conference Publications

• Christian Komusiewicz and Nils Morawietz: Parameterized Local Search for Vertex Cover: When only the Search Radius is CrucialExternal link. In Proceedings of the 17th International Symposium on Parameterized and Exact Computation (IPEC'22External link). Volume 249 of LIPIcs, pages 20:1-20:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Christian Komusiewicz and Nils Morawietz: Finding 3-Swap-Optimal Independent Sets and Dominating Sets Is HardExternal link. In Proceedings of the 47th International Symposium on Mathematical Foundations of Computer Science (MFCS'22External link). Volume 241 of LIPIcs, pages 66:1--66:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.

Journal Publications

• Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer: Colored cut gamesExternal link. Theoretical Computer ScienceExternal link 936: 13-32, 2022 (originial publicationExternal link).
• Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer: Refined Parameterizations for Computing Colored Cuts in Edge-Colored GraphsExternal link. Theory of Computing SystemsExternal link 66(5): 1019–1045, 2022.

2021

Conference Publications

• Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological OrderingsExternal link. In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI'21External link). Pages 12328–12335, AAAI Press (original publicationExternal link).
• Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: On the Parameterized Complexity of Polytree LearningExternal link. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI'21External link). Pages 4221-4227, ijcai.org (original publicationExternal link).
• Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: Preventing Small (s,t)-Cuts by Protecting EdgesExternal link. In Proceedings of the 47th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'21External link). Volume 12911 of LNCS, pages 143-155, Springer (original publicationExternal link).
• Christian Komusiewicz and Nils Morawietz: Can Local Optimality Be Used for Efficient Data Reduction?External link In Proceedings of the 12th International Conference on Algorithms and Complexity (CIAC'21External link). Volume 12701 of LNCS, pages 354-366, Springer (original publicationExternal link).
• Nils Morawietz and Petra Wolf: A Timecop's Chase Around the TableExternal link. In Proceedings of the 46th International Symposium on Mathematical Foundations of Computer Science (MFCS'21External link). Volume 202 of LIPIcs, pages 77:1-77:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.d

2020

Conference Publications

• Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree GraphsExternal link. In Proceedings of the Seventeenth Scandinavian Symposium and Workshop on Algorithm Theory (SWAT'20). Volume 162 of LIPIcs, pages 26:1-26:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (original publicationExternal link).
• Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: String Factorizations under Various Collision ConstraintsExternal link. In Proceedings of the Thirty-First Annual Symposium on Combinatorial Pattern Matching (CPM'20External link). Volume 161 of LIPIcs, pages 17:1-17:14, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer. Colored cut gamesExternal link. In Proceedings of the 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS'20External link). Volume 182 of LIPIcs, 30:1-30:17, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Nils Morawietz, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer: Refined Parameterizations for Computing Colored Cuts in Edge-Colored GraphsExternal link. In Proceedings of the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'20External link). Volume 12011 of LNCS, pages 248-259, Springer (original publicationExternal link).
• Nils Morawietz, Carolin Rehs, and Mathias Weller: A Timecop’s Work is Harder Than You ThinkExternal link. In Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science (MFCS'20External link). Volume 170 of LIPIcs, pages 71:1–71:14. Schloss Dagstuhl — Leibniz-Zentrum für Informatik.