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

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

We study $\ddot{I}„$-Bounded-Density Edge Deletion ($\ddot{I}„$-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 subgrap…