Finding a minimum spanning tree with a small non-terminal set

In this paper, we study the problem of finding a minimum weight spanning tree that contains each vertex in a given subset V_NT of vertices as an internal vertex. This problem, called MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, includes s-t HAMILTONIAN PATH as a special case, and hence it is NP-hard. In this paper, we first observe that NON-TERMINAL SPANNING TREE, the unweighted counterpart of MINIMUM WEIGHT NON-TERMINAL SPANNING TREE, is already NP-hard on some special graph classes. Moreover, it is W[1]-hard when parameterized by clique-width. In contrast, we give a 3k-vertex kernel and O^⁎(2^k)-time algorithm, where k is the size of non-terminal set V_NT. The latter algorithm can be extended to MINIMUM WEIGHT NON-TERMINAL SPANNING TREE with the restriction that each edge has a polynomially bounded integral weight. We also show that MINIMUM WEIGHT NON-TERMINAL SPANNING TREE is fixed-parameter tractable parameterized by the number of edges in the subgraph induced by the non-terminal set V_NT, extending the fixed-parameter tractability of MINIMUM WEIGHT NON-TERMINAL SPANNING TREE to a more general case. Finally, we give several results for structural parameterization.