Heuristics for the k-cardinality tree and subgraph problems

In this paper we consider the problem of finding in a given graph a minimal weight subtree or connected subgraph, which has a given number of edges. These NP-hard combinatorial optimization problems have various applications in the oil industry, in facility layout and graph partitioning. We present different heuristic approaches based on spanning tree and shortest path methods and on an exact algorithm solving the problem in polynomial time if the underlying graph is a tree. Both the edge- and node-weighted cases are investigated and extensive numerical results on the behaviour of the heuristics compared to optimal solutions are presented. The best heuristics yielded results within an error margin of less than one percent from optimality for most cases. In a large percentage of tests even optimal solutions have been found.