Exact algorithm for the problem of the minimum complete spanning tree of a divisible multiple graph

We study undirected multiple graphs of any natural multiplicity $k > 1$. There are edges of three types: ordinary edges, multiple edges, and multi-edges. Each edge of the last two types is a union of $k$ linked edges, which connect $2$ or $(k + 1)$ vertices, correspondingly. The linked edges should be used simultaneously. Divisible graphs form a special class of multiple graphs. The main peculiarity of them is a possibility to divide the graph into $k$ parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The multiple tree is a multiple graph with no multiple cycles. The number of edges may be different for multiple trees with the same number of vertices. Also we can consider spanning trees of a multiple graph. A spanning tree is complete if a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. The problem of the minimum complete spanning tree of a multiple graph is NP-hard even in the case of a divisible graph. In this article, we obtain an exact algorithm for the problem of the minimum complete spanning tree of a divisible multiple graph. Also we define a subclass of divisible graphs, for which the algorithm runs in polynomial time.