Threshold-based preprocessing for approximating the weighted dense k-subgraph problem

Based on an application in forestry, we study the dense k  -subgraph problem: Given a parameter k∈N$k\in \mathbb{N}$ and an undirected weighted graph G, the task is to find a subgraph of G with k vertices such that the sum of the weights of the induced edges is maximized. The problem is well-known to be NP-hard and difficult to approximate if the underlying graph does not satisfy the triangle inequality.