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

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

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