Publications

Below you can find my publications sorted by journals, with links and toggleable abstracts.
This list is sorted by journals. For sorting by conferences or date click here.

Sort by conference Sort by date

Discrete Applied Mathematics

[3]

journal article

A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
Christian Komusiewicz and Jannik Schestag

Discrete Applied Mathematics, 382:137-154, 2025. journal arXiv

In the Generalized Noah's Ark Problem, one is given a phylogenetic tree on a set of species \(X\) and a set of conservation projects for each species. Each project comes with a cost and raises the survival probability of the corresponding species. The aim is to select a conservation project for each species such that the total cost of the selected projects does not exceed a given threshold and the expected phylogenetic diversity is as large as possible. We study the complexity of the Generalized Noah's Ark Problem and several of its special cases with respect to parameters related to the input structure, such as the number of different costs, the number of different survival probabilities, and the number of species.

@article{komusiewicz2025multivariate,
  title = {{A multivariate complexity analysis of the Generalized Noah's Ark Problem}},
  author = {Komusiewicz, Christian and Schestag, Jannik},
  journal = {Discrete Applied Mathematics},
  volume = {382},
  pages = {137--154},
  year = {2025},
  publisher = {Elsevier},
  doi = {10.1016/j.dam.2025.11.037}
}

Discrete Mathematics & Theoretical Computer Science

[2]

journal article

Destroying Bicolored \(P_3\)s by Deleting Few Edges
Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag, and Frank Sommer

Discrete Mathematics & Theoretical Computer Science, 23, 2021. journal arXiv

We introduce and study the Bicolored \(P_3\) Deletion problem. The input is a graph whose edges are colored red or blue, and the task is to delete at most \(k\) edges so that no induced path on three vertices contains edges of both colors. We show that the problem is NP-hard and cannot be solved in subexponential time on bounded-degree graphs under ETH. We then identify polynomial-time solvable special cases based on forbidden colored substructures. Finally, we present an FPT algorithm running in \(\mathcal{O}(1.84^k \cdot |V| \cdot |E|)\) time and show that the problem admits a kernel with \(\mathcal{O}(k \Delta \cdot \mathrm{min}(k,\Delta))\) vertices, where \(\Delta\) denotes the maximum degree.

@article{gruttemeier2021destroying,
  title = {{Destroying Bicolored P3s by Deleting Few Edges}},
  author = {Gr{\"u}ttemeier, Niels and Komusiewicz, Christian and Schestag, Jannik and Sommer, Frank},
  journal = {Discrete Mathematics \& Theoretical Computer Science},
  volume = {23},
  year = {2021},
  publisher = {Episciences.org},
  doi = {10.46298/dmtcs.6108}
}

Journal of Graph Algorithms and Applications

[1]

journal article

On Critical Node Problems with Vulnerable Vertices
Jannik Schestag, Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag, and Frank Sommer

Journal of Graph Algorithms and Applications, 28(1):1-26, 2024. journal

In the Critical Node Problem, the task is to delete at most \(k\) vertices from a graph so that the number of connected vertex pairs is bounded by a given threshold. We introduce and study two NP-hard variants where a subset of vertices is marked as vulnerable, and the goal is to bound the number of connected pairs containing at least one vulnerable vertex. In the first variant, vulnerable and non-vulnerable vertices may be deleted, while in the second only non-vulnerable vertices may be removed. We provide a parameterized complexity analysis of both problems. Among other results, we show that both variants are fixed-parameter tractable with respect to \(k+x\). Furthermore, when vulnerable vertices may be deleted, we obtain a polynomial kernel for the parameter vertex-cover number plus \(k\). For the non-deletable variant, we prove NP-hardness even when there is only a single vulnerable vertex.

@article{schestag2024critical,
  title = {{On Critical Node Problems with Vulnerable Vertices}},
  author = {Schestag, Jannik and Gruettemeier, Niels and Komusiewicz, Christian and Sommer, Frank},
  journal = {Journal of Graph Algorithms and Applications},
  volume = {28},
  number = {1},
  pages = {1--26},
  year = {2024},
  doi = {10.7155/jgaa.v28i1.2922}
}