Publications

Conference and Journal Publications

2026 

Conference Publications

• Nicolas Bonichon, Cyril Gavoille, Nicolas Hanusse, Gabriel Le Bouder, Taïssir Marcé, and Nils Morawietz: Freeze-Tag with Return. In Proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS'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.
• Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz, Nils Morawietz, and Till Tantau: The Descriptive Complexity of Relation Modification Problems. In Proceedings of the 51st International Symposium on Mathematical Foundations of Computer Science (MFCS'26External link), to appear.
• Thomas Depian, and Frank Sommer: Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based RadiiExternal link. In Proceedings of the 34th Annual European Symposium on Algorithms (ESA 2026External link).
• 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.
• 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). Volume 362 of LIPIcs, pages 66:1-66:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Robert Ganian, Frank Sommer, and Manuel Sorge: Tractability via Low Dimensionality: The Parameterized Complexity of Training Quantized Neural NetworksExternal link. ICLR 2026External link.
• Jaroslav Garvardt and Christian Komusiewicz: Clustering with Locally Bounded IgnoranceExternal link. In Proceedings of the 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'26External link). Volume 376 of LIPIcs, pages 17:1-17:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• 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.
• Juha Harviainen, Frank Sommer, and Manuel Sorge: Exact and Approximate Algorithms for Polytree LearningExternal link. ICML 2026External link.
• 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.
• Christian Komusiewicz, Zhenwei Liu, Nils Morawietz, and Frank Sommer: Preventing Small Global Cuts by Protecting EdgesExternal link. In Proceedings of the 52nd International Workshop on Graph-Theoretic Concepts in Computer Science (WG'26External link). Volume 376 of LIPIcs, pages 30:1-30:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Christian Komusiewicz and Diptapriyo Majumdar: Enumeration Kernels of Polynomial Size for Cuts of Bounded DegreeExternal link. In Proceedings of the 51st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'26External link). Volume 16448 of LNCS, pages 172–186, Springer (original publicationExternal link).
• Lisa Lehner, Christian Komusiewicz, and Luca Staus:  A Complexity Analysis of the c-Closed Vertex Deletion Problem. In Proceedings of the 20th International Conference and Workshops on Algorithms and Computation (WALCOM'26External link). Volume 16444 of LNCS, pages 217–231, Springer (original publicationExternal link).
• 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.

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, Niels Grüttemeier, Christian Komusiewicz, and Nils Morawietz: Parameterized Local Search for Max c-CutExternal link. Annals of Operations ResearchExternal link, 2026, accepted for publication.
• 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.
• Anton Herrmann, Christian Komusiewicz, Nils Morawietz, and Frank Sommer: Temporal Dominating Set and Temporal Vertex Cover under the Lens of Degree RestrictionsExternal link, Theoretical Computer ScienceExternal link, 2026.
• Christian Komusiewicz, Nils Morawietz, Frank Sommer, and Luca Staus. The Parameter Report: An Orientation Guide for Data-Driven ParameterizationExternal link. Journal of Graph Algorithms and ApplicationsExternal link, 30(1), 385–419.
• Christian Komusiewicz and Jannik Schestag: A Multivariate Complexity Analysis of the Generalized Noah's Ark ProblemExternal link. Discrete Applied MathematicsExternal link, 382: 137–154, 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

• 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.
• 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.
• 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.
• Juha Harviainen, Frank Sommer, and Manuel Sorge: Improving Decision Trees through the Lens of Parameterized Local SearchExternal link. NeurIPS 2025External link.
• Juha Harviainen, Frank Sommer, Manuel Sorge, and Stefan Szeider: Optimal Decision Tree Pruning Revisited: Algorithms and ComplexityExternal link. ICML 2025External link.
• 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.
• 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.
• Christian Komusiewicz, Diptapriyo Majumdar, and Frank Sommer: Polynomial-Size Enumeration Kernelizations for Long Path EnumerationExternal link. In Proceedings of the 51st International Workshop on Graph-Theoretic Concepts in Computer Science (WG'25)External link.
• Christian Komusiewicz, André Schidler, Frank Sommer, Manuel Sorge, Luca Pascal Staus: Learning Minimum-Size BDDs: Towards Efficient Exact AlgorithmsExternal link. ICML 2025External link
• 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.
• Luca Staus, Christian Komusiewicz, Frank Sommer and Manuel Sorge: Witty: An Efficient Solver for Computing Minimum-Size Decision TreesExternal link. In Proceedings of the Thirty-Ninth AAAI Conference on Artificial Intelligence (AAAI'25External link). 

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

• 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 of LIPIcs, pages 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• 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.
• Jaroslav Garvardt and Christian Komusiewicz: Modularity Clustering parameterized by Max Leaf NumberExternal link. In Proceedings of the 19th International Symposium on Parameterized and Exact Computation (IPEC'24External link). Volume 321 of LIPIcs, pages 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Jaroslav Garvardt, Christian Komusiewicz, Berthold Blatt Lorke, and Jannik Schestag: Protective and Nonprotective Subset Sum Games: A Parameterized Complexity Analysis. In Proceedings of the 8th International Conference on Algorithmic Decision Theory (ADT'24External link). Volume 15248 of LNCS, pages 82-97, Springer (original publicationExternal link).
• 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.
• 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 of LIPIcs, pages 60:1-60:18, 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.
• Henning Martin Woydt, Christian Komusiewicz, and Frank Sommer:
  SubModST: A Fast Generic Solver for Submodular Maximization with Size ConstraintsExternal link. In Proceedings of the 32nd Annual European Symposium on Algorithms (ESA'24External link). Volume 308 of LIPIcs, pages 102:1–102:18, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.

Journal Publications

• René van Bevern, Iyad Kanj, Christian Komusiewicz, Rolf Niedermeier, and Manuel Sorge: The role of twins in computing planar supports of hypergraphs. Journal of Graph Algorithms and ApplicationsExternal link, 28(1): 51–79, 2024.
• 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.
• Niels Grüttemeier, Philipp Heinrich Keßler, Christian Komusiewicz, and Frank Sommer:
  Efficient branch-and-bound algorithms for finding triangle-constrained 2-clubsExternal link. Journal of Combinatorial OptimizationExternal link, 48(3):16, 2024.
• Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag, and Frank Sommer. On Critical Node Problems with Vulnerable VerticesExternal link. Journal of Graph Algorithms and ApplicationsExternal link, 28(1): 1–26, 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).
• Matthias Bentert, Jannik Schestag, and Frank Sommer: On the Complexity of Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure ModelExternal link. In Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC'23External link). Volume 285 of LIPIcs, pages 4:1--4:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• 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.
• Jaroslav Garvardt, Malte Renken, Jannik Schestag, and Mathias Weller: Finding Degree-Constrained Acyclic OrientationsExternal link. In Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC'23External link). Volume 285 of LIPIcs, pages 19:1-19:14, 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.
• Jana Holznigenkemper, Christian Komusiewicz, and Bernhard Seeger:
  Exact and Heuristic Approaches to Speeding Up the MSM Time Series Distance Computation. In Proceedings of the SIAM International Conference on Data Mining (SDM'23External link). (original publicationExternal link, arxiv publicationExternal link).
• Mark Jones and Jannik Schestag: How can we Maximize Phylogenetic Diversity? Parameterized Approaches for NetworksExternal link. In Proceedings of the 18th International Symposium on Parameterized and Exact Computation (IPEC'23External link). Volume 285 of LIPIcs, pages 30:1-30:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
• Christian Komusiewicz, Pascal Kunz, Frank Sommer, and Manuel Sorge: Computing Optimal Tree EnsemblesExternal link. In Proceedings of the 2023 International Conference on Machine Learning (ICML'23External link). PMLR 202, pages 17364-17374.
• 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.
• Christian Komusiewicz, Jannis Schramek, and Frank Sommer: On the Group Coverage Centrality Problem: Parameterized Complexity and Heuristics.  In Proceedings of the 2023 SIAM Conference on Applied and Computational Discrete Algorithms (ACDA'23External link). Pages 13-24, SIAM (original publicationExternal link).
• 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).

Journal Publications

• Nils Jakob Eckstein, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer: Destroying Multicolored Paths and Cycles in Edge-Colored GraphsExternal link. Discrete Mathematics & Theoretical Computer ScienceExternal link 25: 1, 2023.
• Jaroslav Garvardt, Christian Komusiewicz, and Frank Sommer: The Parameterized Complexity of s-Club with Triangle and Seed ConstraintsExternal link. Theory of Computing SystemsExternal link, 2023.
• Jana Holznigenkemper, Christian Komusiewicz, and Bernhard Seeger:
  On computing exact means of time series using the move-split-merge metricExternal link. Data Mining and Knowledge DiscoveryExternal link 37(2): 595-626, 2023.
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Computing Dense and Sparse Subgraphs of Weakly Closed GraphsExternal link. AlgorithmicaExternal link 85: 2156–2187, 2023.
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Essentially Tight Kernels for (Weakly) Closed GraphsExternal link. AlgorithmicaExternal link  85: 1706–1735, 2023.

2022

Conference Publications

• Jaroslav Garvardt, Christian Komusiewicz, and Frank Sommer: The Parameterized Complexity of s-Club with Triangle and Seed Constraints. In Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA'22External link). Volume 13270 of LNCS, pages 313-326, Springer (original publicationExternal link, arxiv publicationExternal link).
• 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.
• Tomohiro Koana, Christian Komusiewicz, André Nichterlein, and Frank Sommer: Covering Many (or Few) Edges with k Vertices in Sparse GraphsExternal link. In Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science (STACS'22External link). Volume 219 of LIPIcs, pages 42:1-42:18, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Jannik Schestag, Niels Grüttemeier, Christian Komusiewicz, and Frank Sommer: On Critical Node Problems with Vulnerable Verticespdf, 334 kb. In Proceedings of the 33rd International Workshop on Combinatorial Algorithms (IWOCA'22External link). Volume 13270 of LNCS, pages 494-508, Springer (original publicationExternal link).

Journal Publications

• Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le: Refined notions of parameterized enumeration kernels with applications to matching cut enumerationExternal link. Journal of Computer and System SciencesExternal link 123: 76-102, 2022 (original publicationExternal link).
• Niels Grüttemeier and Christian Komusiewicz: Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity AnalysisExternal link. Journal of Artificial Intelligence ResearchExternal link 74: 1225–1267, 2022 (original publicationExternal link).
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Exploiting c-Closure in Kernelization Algorithms for Graph ProblemsExternal link. SIAM Journal on Discrete MathematicsExternal link 36(4): 2798–2821, 2022 (original publicationExternal link).
• 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

• Laurent Bulteau, Guillaume Fertin, Géraldine Jean, and Christian Komusiewicz: Sorting by Multi-Cut RearrangementsExternal link. In Proceedings of the 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'21External link). Volume 12607 of LNCS, pages 593-607, Springer (original publicationExternal link).
• Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch, and Van Bang Le: Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut EnumerationExternal link. In Proceedings of the 38th International Symposium on Theoretical Aspects of Computer Science (STACS'21External link). Volume 187 of LIPIcs, pages 37:1-37:18, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• 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).
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Essentially Tight Kernels for (Weakly) Closed GraphsExternal link. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC'21External link). Volume 212 of LIPIcs, pages 35:1-35:15, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• 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.

Journal Publications

• Laurent Bulteau, Niels Grüttemeier, Manuel Sorge, and Christian Komusiewicz: Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge ColorsExternal link. Journal of Computer and System SciencesExternal link 120: 75-96, 2021 (original publicationExternal link).
• Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag, and Frank Sommer: Destroying Bicolored P3s by Deleting Few EdgesExternal link. Discrete Mathematics & Theoretical Computer ScienceExternal link 23(1), 2021 (original publicationExternal link).
• Christian Komusiewicz and Frank Sommer: Enumerating Connected Induced Subgraphs: Improved Delay and Experimental ComparisonExternal link. Discrete Applied MathematicsExternal link 303: 262–282, 2021 (original publicationExternal link).

2020

Conference Publications

• Niels Grüttemeier and Christian Komusiewicz: Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity AnalysisExternal link. In Proceedings of the International Joint Conferences on Artificial Intelligence (IJCAI'20External link). Pages 4245-4251, ijcai.org (original publicationExternal link).
• 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'20External link). 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.
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Computing Dense and Sparse Subgraphs of Weakly Closed GraphsExternal link. In Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC'20External link). Volume 181 of LIPIcs, pages 20:1-20:17, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Tomohiro Koana, Christian Komusiewicz, and Frank Sommer: Exploiting c-Closure in Kernelization Algorithms for Graph ProblemsExternal link. In Proceedings of the 28th Annual European Symposium on Algorithms (ESA'20External link). Volume 173 of LIPIcs, pages 65:1–65:17, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Christian Komusiewicz and Frank Sommer: FixCon: A Generic Solver for Fixed-Cardinality Subgraph ProblemsExternal link. In Proceedings of the Twenty-Second Workshop on Algorithm Engineering and Experiments (ALENEX ’20External link). Pages 12-26, SIAM (original publicationExternal link). 
• 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.

Journal Publications

• Guillaume Fertin and Christian Komusiewicz: Graph Motif problems parameterized by dualExternal link. Journal of Graph Algorithms and ApplicationsExternal link 24(3): 371–396, 2020.
• Niels Grüttemeier and Christian Komusiewicz: On the Relation of Strong Triadic Closure and Cluster DeletionExternal link. AlgorithmicaExternal link 82(4): 853–880, 2020 (original publicationExternal link).
• Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen: Solving Partition Problems Almost Always Requires Pushing Many Vertices AroundExternal link. SIAM Journal on Discrete MathematicsExternal link 34(1): 640–681, 2020 (original participationExternal link).
• Christian Komusiewicz, Mateus de Oliveira Oliveira, and Meirav Zehavi: Revisiting the Parameterized Complexity of Maximum-Duo Preservation String MappingExternal link. Theoretical Computer ScienceExternal link 847: 27-38, 2020 (original publicationExternal link).
• Dieter Kratsch, Christian Komusiewicz, and Van Bang Le: Matching Cut: Kernelization, Single-Exponential FPT, and Exact Exponential AlgorithmsExternal link. Discrete Applied MathematicsExternal link 283: 44–58, 2020 (original publicationExternal link).
• Frank Sommer and Christian Komusiewicz: Parameterized Algorithms for Module Map ProblemsExternal link. Discrete Applied MathematicsExternal link 283: 396–416, 2020 (original publicationExternal link).

2019

Conference Publications

• Markus Brill, Piotr Faliszewski, Frank Sommer, and Nimrod Talmon: Approximation Algorithms for BalancedCC Multiwinner RulesExternal link. In Proceedings of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS'19External link), pages 494–502, IFAAMAS.
• Laurent Bulteau, Niels Grüttemeier, Manuel Sorge, and Christian Komusiewicz: Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge ColorsExternal link. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC'19External link), Volume 11485 of LNCS, pages 99–111, Springer (original publicationExternal link).
• Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag and Frank Sommer: Destroying Bicolored P3s by Deleting Few EdgesExternal link. In Proceedings of the 15th Conference on Computability in Europe (CiE'19External link), Volume 11558 of LNCS, pages 193–204, Springer (original publicationExternal link).
• Christian Komusiewicz and Frank Sommer: Enumerating Connected Induced Subgraphs: Improved Delay and Experimental ComparisonExternal link. In Proceedings of the 45th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM'19External link), Volume 11376 of LNCS, pages 272–284, Springer (original publicationExternal link).

Journal Publications

• Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge: Assessing the computational complexity of multilayer subgraph detectionExternal link. Network ScienceExternal link 7(2): 215–241 (original publicationExternal link)
• Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon: When Can Graph Hyperbolicity Be Computed in Linear Time?External link. AlgorithmicaExternal link 81(5): 2016–2045 (original publicationExternal link).
• Christian Komusiewicz, André Nichterlein, Rolf Niedermeier, and Marten Picker: Exact algorithms for finding well- connected 2- clubs in sparse real- world graphs: Theory and experimentsExternal link. European Journal of Operational ResearchExternal link 275(3): 846–864 (original publicationExternal link).

2018

Conference Publications

• Guillaume Fertin, Julien Fradin, and Christian Komusiewicz: On the Maximum Colorful Arborescence Problem and Color Hierarchy Graph StructureExternal link. In Proceedings of the 29th Annual Symposium on Combinatorial Pattern Matching (CPM'18External link). Volume 105 of LIPIcs, pages 17:1–17:15, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Niels Grüttemeier and Christian Komusiewicz: On the Relation of Strong Triadic Closure and Cluster DeletionExternal link. In Proceedings of the 44th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'18External link). Volume 11159 of LNCS, pages 239-251, Springer (original publicationExternal link).
• Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen: Solving Partition Problems Almost Always Requires Pushing Many Vertices AroundExternal link. In Proceedings of the 26th Annual European Symposium on Algorithms (ESA'18External link). Volume 112 of LIPIcs, pages 51:1–51:14, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Dieter Kratsch, Christian Komusiewicz, and Van Bang Le: Matching Cut: Kernelization, Single-Exponential FPT, and Exact Exponential AlgorithmsExternal link. In Proceedings of the 13th International Symposium on Parameterized and Exact Computation (IPEC'18External link). Volume 115 of LIPIcs, pages 19:1–19:13, Schloss Dagstuhl — Leibniz-Zentrum für Informatik.
• Frank Sommer and Christian Komusiewicz: Parameterized Algorithms for Module Map ProblemsExternal link. In Proceedings of the Fifth International Symposium on Combinatorial Optimization (ISCO'18External link). Volume 10856 of LNCS, pages 376-388, Springer (original publicationExternal link).

Journal Publications

• René van Bevern, Vincent Froese, and Christian Komusiewicz: Parameterizing edge modification problems above lower boundsExternal link. Theory of Computing SystemsExternal link 62(3): 739–770 (original publicationExternal link).
• Guillaume Fertin, Falk Hüffner, Christian Komusiewicz, and Manuel Sorge: Matching Algorithms for Assigning Orthologs after Genome Duplication EventsExternal link. Computational Biology and ChemistryExternal link 74: 379–390 (APBC'18External link special issue).
• Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, and Erik Jan van Leeuwen: Parameterized algorithms for recognizing monopolar and 2-subcolorable graphsExternal link. Journal of Computer and System SciencesExternal link 92: 22–47 (original publicationExternal link).
• Christian Komusiewicz: Tight running time lower bounds for vertex deletion problemsExternal link. ACM Transactions on Computation TheoryExternal link 10(2): 6 (original publicationExternal link).