Minimum spanning tree problems with conflict constraints

The minimum spanning tree with conflict constraints (MSTC) problem is a combination of the maximum cardinality stable set and the minimum spanning tree problems, and it is proven to be NP-hard. This thesis investigates this problem in graphs where certain pairs of edges cannot be included simultaneously due to conflict constraints. Such constraints are crucial for applications in network design, particularly in scenarios where resource limitations, regulatory rules, or physical restrictions prevent specific connections from coexisting. We propose four distinct branch-and-bound algorithms to effectively navigate the complex solution space of this problem. Each algorithm incorporates innovative strategies to enhance computational efficiency. Experimental results indicate that the novel algorithms are very fast and outperform a widely used commercial solver. Furthermore, this thesis provides a comprehensive analysis of the structural properties of conflict constraints and their impact on the solution space. These findings have broad implications for applications in telecommunications, transportation, and energy distribution networks, where optimization under complex constraints is essential. By addressing both theoretical and practical challenges, this thesis establishes a foundational framework for computing conflict-free minimum spanning trees. The proposed methodologies not only outperform existing solution procedures but also improve best known solutions and set the stage for future advancements in optimization and network design under disjunctive conditions.