Bounded-Density Vertex Deletion Beyond Vertex Cover

Adrian Miclăuş, Alexandru Popa, Andrei Popa

We study \textsc{Bounded-Density Vertex Deletion} (BDVD), where one asks whether at most \(k\) vertices can be deleted so that every remaining subgraph has density at most a ration…