The Tree-Star Problem: A Formulation and a Branch-and-Cut Algorithm

Let G=(V,E)G=(V,E) be a connected undirected graph and assume that an edge e=i,j∈Ee=i,j∈E may be priced differently, at the different spanning trees of G   that contain it. A cost cece applying when e is leaf implying, i.e., when e belongs to the spanning tree and i or j are spanning tree leaves. Otherwise, when e   belongs to the tree but is not leaf implying, a cost dede would apply. Under such a pricing of edges, the Tree-Star Problem is to find a least cost spanning tree of G. The problem does not appear to have been previously investigated in the literature and we show it to be NP-hard, formulate it as a mixed integer program, and propose and test a Branch-and-Cut algorithm for it. So far, the algorithm contains no primal heuristic. However, as it stands, it is already capable of solving to proven optimality tree-star instances with as many as 299 vertices.