Dial a Ride from k-forest

The k-forest problem is a common generalization of both the k-MST and the dense-k -subgraph problems. Formally, given a metric space on n vertices V, with m demand pairs ⊆ V ×V and a “target” k ≤ m, the goal is to find a minimum cost subgraph that connects at least k demand pairs.