The subdivision-constrained minimum spanning tree problem

Motivated by the constrained minimum spanning tree (CST) problem in Hassin and Levin [R. Hassin, A. Levin, An efficient polynomial time approximation scheme for the constrained minimum spanning tree problem using matroid intersection, SIAM Journal on Computing 33 (2) (2004) 261–268], we study a new combinatorial optimization problem in this paper, called the general subdivision-constrained spanning tree problem (GSCST): given a graph G=(V,E;w,c) with two nonnegative integers w(e) and c(e) for each edge e∈E, two positive integers B and d, the GSCST problem is to first find a spanning tree T=(V,ET) of G with weight ∑e∈ETw(e)≤B and then to insert some new vertices on some suitable edges in T such that each edge in the subdivision tree T′ of T has its weight not beyond d. The objective is to minimize the cost ∑e∈ETinsert(e)c(e) of such new vertices inserted on the suitable edges among all spanning trees of G subject to the two preceding constraints, where a subdivision tree T′ of T is constructed by inserting some new vertices on the suitable edges in T, the value is the least number of vertices inserted and c(e) is the cost of each vertex inserted on the edge e. We obtain the following main results: (1) the GSCST problem and its variant are still NP-hard, by a reduction from the 0–1 knapsack problem, respectively; (2) the GSCST problem as well as its variant is polynomially equivalent to the CST problem, which implies the existence of a polynomial time approximation scheme to solve the GSCST problem and its variant; (3) we finally design three strongly polynomial time algorithms to solve the special versions of the GSCST problem and its variant, respectively.