Tom-Lukas Breitkopf

collaborators

4 papers

cs.DS2026

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 $G$ , an integer budget $k$ , and a target density $I ¨ _{I ¨} $ , the task is to determine…

cs.DC2026

Ranking Opinions with Few States in Population Protocols

Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek +1

Population protocols are a model of distributed computing where $n$ agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) int…

cs.DS2026

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…

cs.DS2026

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density

Matthias Bentert, Tom-Lukas Breitkopf, Vincent Froese +2

We study $I ¨ $ -Bounded-Density Edge Deletion ( $I ¨ $ -BDED), where given an undirected graph $G$ , the task is to remove as few edges as possible to obtain a graph $G^{'}$ where no subgrap…