30 citations · 100 across the 41 of their papers we have counts for
55 papers
The Influence of Agent Models on the Complexity of Bus Routing
Eva Deltl, Christian Komusiewicz, Jurek Rostalsky +2
In bus routing, the task is to plan a bus route in a network with several agents, each of whom wants to travel from a starting point to a destination. A bus route should account fo…
Clustering with Locally Bounded Ignorance
Jaroslav Garvardt, Christian Komusiewicz
In Correlation Clustering, the input is a graph with weight function and the task is to partition the vertex set into clusters such that the total…
Parameterized Local Search for Vertex Cover: When only the Search Radius is Crucial
Christian Komusiewicz, Nils Morawietz
A vertex set in a graph is a valid -swap for a vertex cover of if has size at most and , the symmetric differenc…
On the Hardness of Finding Temporally Connected Subgraphs of Any Size
Arnaud Casteigts, Christian Komusiewicz, Nils Morawietz
Temporal graphs are graphs whose edges are present only at certain points in time. Reachability in these graphs is defined via temporal paths, in which edges are traversed in incre…
The Descriptive Complexity of Relation Modification Problems
Florian Chudigiewitsch, Marlene Gründel, Christian Komusiewicz +2
A relation modification problem gets a logical structure and a natural number k as input and asks whether k modifications of the structure suffice to make it satisfy a predefined p…
A Parameterized-Complexity Framework for Finding Local Optima
Robert Ganian, Hung P. Hoang, Christian Komusiewicz +1
Local search is a fundamental optimization technique that is both widely used in practice and deeply studied in theory, yet its computational complexity remains poorly understood.…
A Complexity Analysis of the c-Closed Vertex Deletion Problem
Lisa Lehner, Christian Komusiewicz, Luca Pascal Staus
A graph is -closed when every pair of nonadjacent vertices has at most common neighbors. In -Closed Vertex Deletion, the input is a graph and an integer and we…
Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
Anton Herrmann, Christian Komusiewicz, Nils Morawietz +1
A temporal graph is a finite sequence of graphs, called snapshots, over the same vertex set. Many temporal graph problems turn out to be much more difficult than their static count…
The Parameter Report: An Orientation Guide for Data-Driven Parameterization
Christian Komusiewicz, Nils Morawietz, Frank Sommer +1
A strength of parameterized algorithmics is that each problem can be parameterized by an essentially inexhaustible set of parameters. Usually, the choice of the considered paramete…
Polynomial-Size Enumeration Kernelizations for Long Path Enumeration
Christian Komusiewicz, Diptapriyo Majumdar, Frank Sommer
Enumeration kernelization for parameterized enumeration problems was defined by Creignou et al. [Theory Comput. Syst. 2017] and was later refined by Golovach et al. [J. Comput. Sys…
Witty: An Efficient Solver for Computing Minimum-Size Decision Trees
Luca Pascal Staus, Christian Komusiewicz, Frank Sommer +1
Decision trees are a classic model for summarizing and classifying data. To enhance interpretability and generalization properties, it has been proposed to favor small decision tre…
Parameterized Local Search for Max -Cut
Jaroslav Garvardt, Niels Grüttemeier, Christian Komusiewicz +1
In the NP-hard Max -Cut problem, one is given an undirected edge-weighted graph and aims to color the vertices of with colors such that the total weight of edges wit…
Maximizing Phylogenetic Diversity under Ecological Constraints: A Parameterized Complexity Study
Christian Komusiewicz, Jannik Schestag
In the NP-hard Optimizing PD with Dependencies (PDD) problem, the input consists of a phylogenetic tree over a set of taxa , a food-web that describes the prey-predator rela…
On the Complexity of Community-aware Network Sparsification
Emanuel Herrendorf, Christian Komusiewicz, Nils Morawietz +1
Network sparsification is the task of reducing the number of edges of a given graph while preserving some crucial graph property. In community-aware network sparsification, the pre…
A Multivariate Complexity Analysis of the Generalized Noah's Ark Problem
Christian Komusiewicz, Jannik Schestag
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 an…
On Computing Optimal Tree Ensembles
Christian Komusiewicz, Pascal Kunz, Frank Sommer +1
Random forests and, more generally, (decision\nobreakdash-)tree ensembles are widely used methods for classification and regression. Recent algorithmic advances allow to compute de…
Exact and Heuristic Approaches to Speeding Up the MSM Time Series Distance Computation
Jana Holznigenkemper, Christian Komusiewicz, Bernhard Seeger
The computation of the distance of two time series is time-consuming for any elastic distance function that accounts for misalignments. Among those functions, DTW is the most promi…
Efficient Branch-and-Bound Algorithms for Finding Triangle-Constrained 2-Clubs
Niels Grüttemeier, Philipp Heinrich Keßler, Christian Komusiewicz +1
In the Vertex Triangle 2-Club problem, we are given an undirected graph and aim to find a maximum-vertex subgraph of that has diameter at most 2 and in which every vertex i…
On Computing Exact Means of Time Series Using the Move-Split-Merge Metric
Jana Holznigenkemper, Christian Komusiewicz, Bernhard Seeger
Computing an accurate mean of a set of time series is a critical task in applications like nearest-neighbor classification and clustering of time series. While there are many dista…
Efficient Bayesian Network Structure Learning via Parameterized Local Search on Topological Orderings
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
In Bayesian Network Structure Learning (BNSL), one is given a variable set and parent scores for each variable and aims to compute a DAG, called Bayesian network, that maximizes th…
The Parameterized Complexity of s-Club with Triangle and Seed Constraints
Jaroslav Garvardt, Christian Komusiewicz, Frank Sommer
The s-Club problem asks, for a given undirected graph , whether contains a vertex set of size at least such that , the subgraph of induced by , has diam…
Covering Many (or Few) Edges with k Vertices in Sparse Graphs
Tomohiro Koana, Christian Komusiewicz, André Nichterlein +1
We study the following two fixed-cardinality optimization problems (a maximization and a minimization variant). For a fixed between zero and one we are given a graph and two nu…
Preventing Small -Cuts by Protecting Edges
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz +1
We introduce and study Weighted Min -Cut Prevention, where we are given a graph with vertices and and an edge cost function and the aim is to choose an edg…
On the Parameterized Complexity of Polytree Learning
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
A Bayesian network is a directed acyclic graph that represents statistical dependencies between variables of a joint probability distribution. A fundamental task in data science is…