A greedy heuristic for a minimum-weight forest problem (Q1317004)

This paper considers the problem of finding a minimum weight collection of edges (in a graph) that intersect every cut set of size at most \(K\). For \(K= 1\) the problem reduces to that of finding a minimum weight edge cover of the nodes of a graph, which is polynomially solvable. Indeed, the problem is polynomially solvable for all \(K\leq 3\). In this paper, the authors show that it is NP-hard for \(K\geq 4\). In addition they describe an approximation algorithm which returns a feasible solution with cost at most twice optimal. The algorithms runs within the time needed to compute a minimum spanning tree.