Minimal Spanning Trees with Conflict Graphs

Andreas Darmann (andreas.darmannuni-graz.at)
Ulrich Pferschy (pferschyuni-graz.at)
Joachim Schauer (joachim.schaueruni-graz.at)

Abstract: For the classical minimum spanning tree problem we introduce disjunctive constraints for pairs of edges which can not be both included in the spanning tree at the same time. These constraints are represented by a conflict graph whose vertices correspond to the edges of the original graph. Edges in the conflict graph connect conflicting edges of the original graph. It is shown that the problem becomes strongly NP-hard even if the connected components of the conflict graph consist only of paths of length two. On the other hand, for conflict graphs consisting of disjoint edges (i.e. paths of length one) the problem remains polynomially solvable.

Keywords: minimal spanning tree, conflict graph

Category 1: Combinatorial Optimization (Graphs and Matroids )

Category 2: Network Optimization

Citation: A completely revised and considerably extended paper on this subject is available as Optimization Online 2009-10-2422.

Download: [PDF]

Entry Submitted: 12/19/2008
Entry Accepted: 01/08/2009
Entry Last Modified: 10/13/2009

Modify/Update this entry