Tech Report CS-03-04

On the Complexity of the Robust Spanning Tree Problem with Interval Data

Ionut Aron and Pascal Van Hentenryck

March 2003


This paper studies the complexity of the robust spanning tree problem with interval data (RSTID). It settles the conjecture of Kouvelis by proving that the problem is NP-complete. The paper also shows that the problem remains NP-complete for (1) complete graphs and (2) when the cost intervals are all [0,1]. The proofs of the results show that the difficulty of the RSTID problem resides in two distinct aspects of the problem: the topology of the graph and the numerical properties of the cost intervals. As a consequence, the results suggest new directions for improving and evaluating existing search algorithms for the RSTID problem, since they have only focused on one of these aspects.

(complete text in pdf or gzipped postscript)