On the k-maximally-disjoint weighted spanning trees problem: variants, complexity and algorithms

Let us consider a connected undirected graph $$G = (V, E,d,w)$$ G = ( V , E , d , w ) with a set of nodes V, a set of edges E, an edge distance vector d, and an edge weight vector w. For a given integer $$k \ge 2$$ k ≥ 2 , we investigate the problem of finding k-maximally weighted edge-disjoint spanning trees $$S_1,S_2\ldots S_k$$ S 1 , S 2 … S k , where $$S_i\subseteq E$$ S i ⊆ E , $$i\in \{1,\dots , k\}$$ i ∈ { 1 , ⋯ , k } . Given k root nodes $$r_1,\ldots r_k \in V$$ r 1 , … r k ∈ V , we also impose additional constraints, leading to two new variants: (1) $$S_1$$ S 1 must be a shortest-path tree, with respect to d, rooted on $$r_1$$ r 1 and 2) all trees must be shortest-path trees, with respect to d, rooted on $$r_1,\ldots r_k$$ r 1 , … r k , respectively. We consider two different objective functions: (1) the weight of $$S_1$$ S 1 is minimum, and (2) the total weight of $$S_1,\dots , S_k$$ S 1 , ⋯ , S k is minimum. We show that each variant belongs to $$\mathcal {P}$$ P class for some values of k. This leads to exact polynomial matroid-based algorithms. We present and discuss the numerical results for every variant, and analyze the properties of the trees returned by the algorithms.