On the k-edge-incident subgraph problem and its variants

Given a node-weighted graph G=(V,E) and an integer k, the k-edge-incident subgraph problem requires one to find a vertex set S⊆V of maximum weight that covers at most k edges, and the minimum partial vertex cover problem requires one to find a set of k vertices that covers the minimum number of edges. These two problems are closely related to the well-studied densest k-subgraph problem, and are interesting on their own. In this paper, we study these two problems from an approximation point of view. We obtain the following results.