The minimum cost-tree cover problem is to compute a minimum cost-tree T in a given connected graph G with costs on the edges, such that the vertices spanned by T form a vertex cover for G . The problem is supposed to occur in applications of vertex cover and in edge-dominating sets when additional connectivity is required for solutions. Whereas a linear-time 2 -approximation algorithm for the unweighted case has been known for quite a while, the best approximation ratio known for the weighted case is 3 . Moreover, the 3 -approximation algorithms for such cases are far from practical due to their inefficiency. In this article we present a fast, purely combinatorial 2 -approximation algorithm for the minimum cost-tree cover problem. It constructs a good approximate solution by trimming some leaves within a minimum spanning tree (MST); and, to determine which leaves to trim, it uses both the primal-dual schema and an instance layering technique adapted from the local ratio method.

A feedback vertex set of a graph is a subset of vertices that contains at least one vertex from every cycle in the graph. The problem considered is that of finding a minimum feedback vertex set given a weighted and undirected graph. We present a simple and efficient approximation algorithm with performance ratio of at most 2, improving previous best bounds for either weighted or unweighted cases of the problem. Any further improvement on this bound, matching the best constant factor known for the vertex cover problem, is deemed challenging. The approximation principle, underlying the algorithm, is based on a generalized form of the classical local ratio theorem, originally developed for approximation of the vertex cover problem, and a more flexible style of its application.