Based on an application in forestry, we study the dense k-subgraph problem: Given a parameter k∈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...