The Minimum Centroid Branch Spanning Tree Problem

For a spanning tree T of graph G, the centroid of T is a vertex v for which the largest component of T - v has as few vertices as possible. The number of vertices of this component is called the centroid branch weight of T. The minimum centroid branch spanning tree problem is to find a spanning tree T of G such that the centroid branch weight is minimized. In application to design of communication networks, the loads of all branches leading from the switch center should be as balanced as possible. In this paper, we prove that the problem is strongly NP-hard even for bipartite graphs. Moreover, the problem is shown to be polynomially solvable for split graphs, and exact formulae for special graph families, say K-n1,K- n2, ..., (nk) and P-m x P-n, are presented.