31 citations · 116 across the 28 of their papers we have counts for
44 papers
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…
Designing Approximate Binary Trees for Trees
Leon Kellerhals, Mitja Krebs, André Nichterlein +1
We study the following problem that is motivated by demand-aware network design: Given a tree~, the task is to find a binary tree~ on the same vertex set. The objective is to…
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…
Destroying Densest Subgraphs is Hard
Cristina Bazgan, André Nichterlein, Sofia Vazquez Alferez
We analyze the computational complexity of the following computational problems called Bounded-Density Edge Deletion and Bounded-Density Vertex Deletion: Given a graph , a budge…
Parameterized Lower Bounds for Problems in P via Fine-Grained Cross-Compositions
Klaus Heeger, André Nichterlein, Rolf Niedermeier
We provide a general framework to exclude parameterized running times of the form for problems that have polynomial running time lower bounds under hypotheses from…