Hypergraphs for Covering Trees and Approximating Steiner Trees

This article presents a particular tree covering technique. To cover a set of nodes belonging to an unknown tree, a set of connected small Steiner trees is proposed. These Steiner trees can be represented as hyperedges, and a chain or tree of hyperedges provides the cover. The model allows the calculation of approximate (partial) spanning trees in graphs. The idea of covering a set of nodes by hyperedges can be used directly in Steiner heuristics. The NP-hard Steiner problem in graphs is one of the most studied graph-related problems. Several heuristics are known to give approximated solutions. The classical approximations of the Steiner problem apply shortest paths. We present a generalized metric closure that can be constructed from hyperedges of limited size, and new approximations based on the generalized metric closure are proposed. A connected hyperedge set (without loops) approximates a Steiner tree. The paper also presents a performance analysis of the proposed heuristics. The variation in hyperedge size is analyzed. An interesting result is that using larger hyperedges significantly improves the algorithm’s efficiency.