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. 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 some given threshold and the expected phylogenetic diversity is as large as possible. We study the complexity of Generalized Noah's Ark Problem and some of its special cases with respect to several parameters related to the input structure, such as the number of different costs, the number of different survival probabilities, or the number of species, \(|X|\).

@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. journal arXiv

We introduce and study the Bicolored \(P_3\) Deletion problem defined as follows. The input is a graph \(G = (V, E)\) where the edge set \(E\) is partitioned into a set \(E_r\) of red edges and a set \(E_b\) of blue edges. The question is whether we can delete at most \(k\) edges such that \(G\) does not contain a bicolored \(P_3\) as an induced subgraph. Here, a bicolored \(P_3\) is a path on three vertices with one blue and one red edge. We show that Bicolored \(P_3\) Deletion is NP-hard and cannot be solved in \(2^{o(|V|+|E|)}\) time on bounded-degree graphs if the ETH is true. Then, we show that Bicolored \(P_3\) Deletion is polynomial-time solvable when \(G\) does not contain a bicolored \(K_3\), that is, a triangle with edges of both colors. We also provide a polynomial-time algorithm for the case that \(G\) contains no blue \(P_3\), red \(P_3\), blue \(K_3\), and red \(K_3\). Finally, we show that Bicolored \(P_3\) Deletion can be solved in \(\mathcal{O}(1.84^k \cdot |V | \cdot |E|)\) time and that it admits a kernel with \(\mathcal{O}(k \Delta min(k, \Delta))\) vertices, where \(\Delta\) is the maximum degree of \(G\).

@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, and Frank Sommer

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

A vertex pair in an undirected graph is called connected if the two vertices are connected by a path. In the NP-hard Critical Node Problem (CNP), the input is an undirected graph \(G\) with integers \(k\) and \(x\), and the question is whether one can transform \(G\) by deleting at most \(k\) vertices into a graph whose total number of connected vertex pairs is at most \(x\). In this work, we introduce and study two NP- hard variants of CNP where a subset of the vertices is marked as vulnerable, and we aim to obtain a graph with at most \(x\) connected vertex pairs containing at least one vulnerable vertex. In the first variant, which generalizes CNP, we may delete vulnerable and non-vulnerable vertices. In the second variant, we may only delete non-vulnerable vertices.
We perform a parameterized complexity study of both problems. For example, we show that both problems are FPT with respect to \(k + x\). Furthermore, in the case of deletable vulnerable nodes, we provide a polynomial kernel for the parameter \(vc +k\), where \(vc\) is the vertex cover number. In the case of non-deletable vulnerable nodes, we prove NP-hardness even when there is only one vulnerable node.

@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}
}