Publications

Conference and Journal Publications

2024

Conference Publications

• Thomas Erlebach, Nils Morawietz, and Petra Wolf: Parameterized Algorithms for Multi-Label Periodic Temporal Graph Realization. In Proceedings of the 3rd Symposium on Algorithmic Foundations of Dynamic Networks (SAND'24External link), to appear.

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, Christian Komusiewicz, Jannik Schestag, and Frank Sommer. On Critical Node Problems with Vulnerable Vertices . 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 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.
• 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).
• 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.

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 Science External 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).