A Note on Approximability of Densest At-Least-k-Subgraph

Bundit Laekhanukit, Pasin Manurangsi, Ohad Trabelsi

We study the Densest At-Least-$k$-Subgraph (DAL$k$S) problem, in which we are given an undirected graph $G$ and an integer $k$, and the goal is to find a subgraph of $G$ with at le…