In this note, we consider the Multi-period Minimum Spanning Tree Problem (MMST), a variant of the well known Minimum Spanning Tree Problem (MST), that consists in the fol- lowing. Given a connected and undirected graph G and a finite discrete time horizon, one has to schedule the moment in time edges are added to a solution. For each time period, a partial solution consisting of a tree must be built. Once an edge is added to a tree at a given time, it remains in the solution thereafter. At the end of the planning time, the complete solution must be a spanning tree of G. Vertices must be spanned by these trees at times that do not exceed pre-defined dates that depend on each vertex. Edges’ costs represent the discounted cash flows of the installation cost at the time of installation plus maintenance costs, from that time until the end of the planning time. The goal is to choose and schedule the installation of the edges, such that the final spanning tree has a minimum cost. The complexity of MMST was not addressed before. We show that, unlike the MST case, the decision version of MMST is N P−Complete.
Citation
Technical Report Departamento de Ciência da Computação Universidade Federal de Minas Gerais
Article
View On the NP-Completeness of the Multi-Period Minimum Spanning Tree Problem