Minimum Spanning Tree (MST) offers powerful applications in a wide range of domains, including circuit design, computer science, electrical grids, financial markets, and telecom networks. They are also indirectly leveraged (e.g., as algorithm subroutines) for solving other critical problems, such as the Traveling Salesman or Minimum Cut problems. Broadly speaking, MST aims to connect a set of objects with minimum cost based on graph theory.
In mathematical terms, we can represent the problem as a graph G = (V, E), where V = a set of vertices, and E = a set of edges, where the goal is to compute a spanning tree T of graph G with minimum sum of edge costs Ce. Note that T is a subset of E, and must not contain a cycle. Prim-Jarnik (or Prim’s) Algorithm and Kruskal’s Algorithm are most commonly used to solve MST problems, primarily through heap data structures, and Union-Find data structures, respectively – these ensure fast implementations with the execution duration being O((m + n) log n), where m and n are the numbers of edges and vertices respectively in graph G.
Real-life problems are often complex, and the straightforward application of computationally-easy MST may not be possible. For instance, many practical scenarios include a certain constraint d for the vertices V (i.e., no vertex v ∈ V in the spanning tree should have a degree greater than d, where d ≥ 2.) Such problems fall under the category of Degree-Constrained Minimum Spanning Trees (DCMST, or d-MST), or Bounded Degree Minimum Spanning Trees.
Solving DCMST problems
DCMST is an NP-hard combinatorial optimization problem, and hence, much more complex than conventional MST. Heuristic and meta-heuristic methods are often the go-to approach for DCMST, mainly due to their ability to find near-optimal solutions for NP-hard problems within a reasonable time. Here are a few examples.
-
Population-based metaheuristic methods, such as Ant Colony Optimization (see example) & Particle Swarm Optimization (see example.)
-
Automata-based heuristic (called LACT) where convergence to the optimal solution is established through the martingale theorem (paper.)
-
Lagrangian relaxation-based heuristic with a look-ahead infeasibility prevention mechanism (paper.)
-
Tree-construction algorithm (called Randomised Primal Method) coupled with heuristic methods like genetic algorithm, multi-start hill-climbing, and simulated annealing. (paper.)
-
Variable neighborhood search heuristic based on a dynamic neighborhood model, coupled with an iterative variable neighborhood descent for improving the local search. (paper.)
In recent times, reduction algorithms have become popular. Here’s an excellent example: the problem’s size and hardness are first reduced based on its mathematical properties; the degree-constrained tree is then built using greedy algorithms, and subsequently, the tree is tuned through the Edge exchange technique. Additionally, many researchers are exploring hybrid and multilayered algorithms.
Dynamic programming (DP) is an area witnessing increased adoption in solving DCMST problems. For instance, this paper proposes a quasi-polynomial time algorithm by combining DP with other techniques, such as negatively correlated rounding and polyhedral approaches. Another recent innovation is reformulating DCMST problems into quadratic unconstrained binary optimization (QUBO). For instance, here’s a paper that encodes spanning trees as a permutation problem instead of individually encoding the presence of edges in the tree.
The overall relevance of DCMST is increasing, particularly in domains like network communication, supply chain planning, and transportation. While heuristic methods will continue to drive many solutions, especially in large-scale optimization problems, innovations in other approaches are quickly gaining ground. Moreover, the algorithm selection mechanism is also expanding in scope – beyond the conventional emphasis on compute economics and optimality gaps, newer aspects like algorithmic stability, and the ease of parameter selection are also becoming important.