1 citations · 1 across the 9 of their papers we have counts for
16 papers
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…
Towards Settling the Complexity of the Lettericity Problem
Mario Grobler, Nils Morawietz, Silas Cato Sacher
The lettericity of a graph is defined as the smallest size of an alphabet such that there is a word and a decoder $\mathcal{D} \subseteq Σ…
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.…
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…
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…
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…
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…
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…
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…
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…