Research highlights

Solving a hard problem (approximately) via nice structures of easier problems

A minimum spanning tree is the cheapest network interconnecting all the existing nodes and various algorithms for computing it can be found in standard algorithm textbooks. In the minimum Steiner tree problem, which first appeared in a letter of mathematician Gauss, the nodes to be interconnected are arbitrarily specified, and the problem becomes hard to compute.

The problem considered here is called minimum tree cover and it lies somewhere in between these two problems although it is as hard as minimum Steiner tree.

Whereas only inefficient algorithms had been known for minimum tree cover, Toshihiro Fujito at Toyohashi University of Technology came up with a new approach and a fast algorithm for solving it with better accuracy.

One natural approach first finds a set of nodes by solving a hard problem and next interconnect them by a Steiner tree. So it builds a solution by computation of a hard problem on top of the other, and all the previous algorithms followed this approach. The Fujito’s algorithm on the other hands does easy computation of a minimum spanning tree and converts it to a better solution by trimming unnecessary leaves in it.

The algorithm mentioned above also implies a new comibinatorial result that a tree cover of good quality can always be found in the vicinity of a minimum spanning tree.

Moreover, success of the algorithm rests on basing it on interlace of two standard techniques, and such an approach should find more applications in designing algorithms for hard problems.

Reference:

Authors:Toshihiro Fujito

Title of original paper: How to trim a MST: A 2-approximation algorithm for minimum cost-tree cover

Journal, volume, pages and year: ACM Transactions on Algorithms 16, No. 2, Article 16 (2012).

Digital Object Identifier (DOI): 10.1145/2151171.2151179

Affiliation(s): Department of Computer Science and Engineering, Toyohashi University of Technology.