11 papers
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 tota…
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…
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…
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 chron…
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.…