5 papers · 1 filter
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…
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 subgrap…
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…