6 papers
Parameterized Complexity of Temporal Agony
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +1
Real-world networks are often organized in several layers forming a hierarchy which determines the interaction between the individual components. In order to discover such hierarch…
Integer Quadratic Programming is W[1]-Hard Parameterized by the Number of Variables
Anton Herrmann
We show that Integer Quadratic Programming is W[1]-hard parameterized by the number of variables. Thus, under standard complexity assumptions, Integer Quadratic Programming cannot…
On the Parameterized Complexity of Bounded-Density Vertex Deletion
Jakob Raupach, Tom-Lukas Breitkopf, Anton Herrmann +1
We explore the parameterized complexity of Bounded Density Vertex Deletion (BDVD): given a graph , an integer budget , and a target density , the task is to determine wh…
Parameterized Algorithms for Computing MAD Trees
Tom-Lukas Breitkopf, Vincent Froese, Anton Herrmann +2
We consider the well-studied problem of finding a spanning tree with minimum average distance between vertex pairs (called a MAD tree). This is a classic network design problem whi…
Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese +2
We study -Bounded-Density Edge Deletion (-BDED), where given an undirected graph , the task is to remove as few edges as possible to obtain a graph where no subgraph…
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…