We study two related problems: finding a set of k vertices and minimum number of edges (kmin) and finding a graph with at least m' edges and minimum number of vertices (mvms). Goldschmidt and Hochbaum GH97 show that the mvms problem is NP-hard and they give a 3-approximation algorithm for the problem. We improve GH97 by giving a ratio of 2. A 2(1+ )-approximation for the problem follows from the work of Carnes and Shmoys CS08 . We improve the approximation ratio to 2. algorithm for the problem. We show that the natural LP for has an integrality gap of 2-o(1). We improve the NP-completeness of GH97 by proving the pronlem are APX-hard unless a well-known instance of the dense k-subgraph admits a constant ratio. The best approximation guarantee known for this instance of dense k-subgraph is O(n^ 2 9 ) BCCFV . We show that for any constant >1, an approximation guarantee of for the problem implies a (1+o(1)) approximation for . Finally, we define we give an exact algorithm for the density version of kmin.
Goldschmidt and Hochbaum @cite_12 introduced the problem. They show that the problem is NP-complete and give algorithms that yield @math -approximate and @math -approximate algorithm for the unweighted and the weighted versions of the problem, respectively.
@cite_12
2012425059
Abstract We study here a problem on graphs that involves finding a subgraph of maximum node weights spanning up to k edges. We interpret the concept of “spanning” to mean that at least one endpoint of the edge is in the subgraph in which we seek to maximize the total weight of the nodes. We discuss the complexity of this problem and other related problems with different concepts of “spanning” and show that most of these variants are NP-complete. For the problem defined, we demonstrate a factor 3 approximation algorithm with complexity O( kn ) for a graph on n nodes. For the unweighted version of the the problem in a graph on m edges we describe a factor 2 approximation algorithm of greedy type, with complexity O( n + m ). For trees and forests we present a polynomial time algorithm applicable to our problem and also to a problem seeking to maximize (minimize) the weight of a subtree on k nodes.