4 citations · 10 across the 13 of their papers we have counts for
24 papers
Parameterizing Cluster Editing by the Number of Deletions
Vincent Froese, Leon Kellerhals, Frank Sommer +2
In Cluster Editing, we are given a graph and an integer and ask whether at most edge insertions and deletions turn into a disjoint union of cliques. Komusiewicz and…
Exact and Approximate Algorithms for Polytree Learning
Juha Harviainen, Frank Sommer, Manuel Sorge
Polytrees are a subclass of Bayesian networks that seek to capture the conditional dependencies between a set of variables as a directed forest and are motivated by their more…
Revisiting Graph Modification via Disk Scaling: From One Radius to Interval-Based Radii
Thomas Depian, Frank Sommer
For a fixed graph class , the goal of -Modification is to transform an input graph into a graph using at most modifications. Vertex and edge deletions are com…
Improving Decision Trees through the Lens of Parameterized Local Search
Juha Harviainen, Frank Sommer, Manuel Sorge
Algorithms for learning decision trees often include heuristic local-search operations such as (1) adjusting the threshold of a cut or (2) also exchanging the feature of that cut.…
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…
Fantastic Flips and Where to Find Them: A General Framework for Parameterized Local Search on Partitioning Problems
Niels Grüttemeier, Nils Morawietz, Frank Sommer
Parameterized local search combines classic local search heuristics with the paradigm of parameterized algorithmics. While most local search algorithms aim to improve given solutio…
Optimal Decision Tree Pruning Revisited: Algorithms and Complexity
Juha Harviainen, Frank Sommer, Manuel Sorge +1
We present a comprehensive classical and parameterized complexity analysis of decision tree pruning operations, extending recent research on the complexity of learning small decisi…
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…
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…
Complexity of Local Search for Euclidean Clustering Problems
Bodo Manthey, Nils Morawietz, Jesse van Rhijn +1
We show that the simplest local search heuristics for two natural Euclidean clustering problems are PLS-complete. First, we show that the Hartigan--Wong method for -Means cluste…
Finding a Sparse Connected Spanning Subgraph in a non-Uniform Failure Model
Matthias Bentert, Jannik Schestag, Frank Sommer
We study a generalization of the classic Spanning Tree problem that allows for a non-uniform failure model. More precisely, edges are either \emph{safe} or \emph{unsafe} and we ass…
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…
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…
Multi-Parameter Analysis of Finding Minors and Subgraphs in Edge Periodic Temporal Graphs
Emmanuel Arrighi, Niels Grüttemeier, Nils Morawietz +2
We study the computational complexity of determining structural properties of edge periodic temporal graphs (EPGs). EPGs are time-varying graphs that compactly represent periodic b…
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…
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…
Computing Dense and Sparse Subgraphs of Weakly Closed Graphs
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
A graph is weakly -closed if every induced subgraph of contains one vertex such that for each non-neighbor of it holds that . The weak clo…
Exploiting -Closure in Kernelization Algorithms for Graph Problems
Tomohiro Koana, Christian Komusiewicz, Frank Sommer
A graph is c-closed if every pair of vertices with at least c common neighbors is adjacent. The c-closure of a graph G is the smallest number such that G is c-closed. Fox et al. [I…
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…