30 citations · 100 across the 41 of their papers we have counts for
30 papers · 1 filter
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…
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…
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…
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…
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…
Destroying Multicolored Paths and Cycles in Edge-Colored Graphs
Nils Jakob Eckstein, Niels Grüttemeier, Christian Komusiewicz +1
We study the computational complexity of -Colored Deletion and -Colored Deletion. In these problems, one is given a -edge-colored graph and wants to dest…
Essentially Tight Kernels for (Weakly) Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
We study kernelization of classic hard graph problems when the input graphs fulfill triadic closure properties. More precisely, we consider the recently introduced parameters closu…
Refined Notions of Parameterized Enumeration Kernels with Applications to Matching Cut Enumeration
Petr A. Golovach, Christian Komusiewicz, Dieter Kratsch +1
An enumeration kernel as defined by Creignou et al. [Theory Comput. Syst. 2017] for a parameterized enumeration problem consists of an algorithm that transforms each instance into…
Learning Bayesian Networks Under Sparsity Constraints: A Parameterized Complexity Analysis
Niels Grüttemeier, Christian Komusiewicz
We study the problem of learning the structure of an optimal Bayesian network when additional constraints are posed on the network or on its moralized graph. More precisely, we con…
Maximum Edge-Colorable Subgraph and Strong Triadic Closure Parameterized by Distance to Low-Degree Graphs
Niels Grüttemeier, Christian Komusiewicz, Nils Morawietz
Given an undirected graph and integers and , the Maximum Edge-Colorable Subgraph problem asks whether we can delete at most edges in to obtain a graph that has a…
Destroying Bicolored s by Deleting Few Edges
Niels Grüttemeier, Christian Komusiewicz, Jannik Schestag +1
We introduce and study the Bicolored Deletion problem defined as follows. The input is a graph where the edge set is partitioned into a set of red edges a…
Your Rugby Mates Don't Need to Know your Colleagues: Triadic Closure with Edge Colors
Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz +1
Given an undirected graph the NP-hard Strong Triadic Closure (STC) problem asks for a labeling of the edges as \emph{weak} and \emph{strong} such that at most edges a…
Exact Algorithms for Finding Well-Connected 2-Clubs in Real-World Graphs: Theory and Experiments
Christian Komusiewicz, André Nichterlein, Rolf Niedermeier +1
Finding large "cliquish" subgraphs is a central topic in graph mining and community detection. A popular clique relaxation are 2-clubs: instead of asking for subgraphs of diameter…
On the Relation of Strong Triadic Closure and Cluster Deletion
Niels Grüttemeier, Christian Komusiewicz
We study the parameterized and classical complexity of two related problems on undirected graphs . In Strong Triadic Closure we aim to label the edges in as strong and…