Minimum Spanning Tree of a Weighted Graph - MathOverflow

Minimum Spanning Tree of a Weighted Graph

2010-06-19T16:55:18Z

I have a connected graph $G=(V,E)$ in $n$ vertices. The edge weights are non-negative and form a metric space, thus for vertices $u,v,w \in V$ , such that $(u,v), (v,w), (w,u)\in E$ we have $r(u,w) \leq r(u,v)+r(v,w)$. We furthermore have the following condition: $\sum_{u\in V}R(u) \leq n$ where $R(u)$ is the average of the weights of the edges incident on $u$.

My question is, does there exist a minimum spanning tree, that has weight at most $Cn$ where $C$ is some universal constant? In place of a minimum weight spanning tree, a walk (sequence of connected vertices) such that the sum of weights of the walk is $Cn$ for some universal constant.

Answer by Tony Huynh for Minimum Spanning Tree of a Weighted Graph

2010-06-19T17:08:26Z

I think the answer is no for both questions. Let $T$ be the unique tree on $2n$ vertices with two adjacent vertices $u$ and $v$ of degree $n$. Let $e=uv$. Let the weight of $e$ be $n^2$ and all other edges to have weight 0. Then the sum of all the average weights is

$n^2/n + n^2/n = 2n = |V(T)|$.

However, $T$ has total weight $n^2$, which is not $O(2n)$.

Comment. I edited my first answer as I misread the condition on the average degrees.

Answer by SandeepJ for Minimum Spanning Tree of a Weighted Graph

2010-06-19T22:00:22Z

You need some variant of the degree-constrained GMST (Generalized Minimum Spanning Tree) with edges satisfying the triangle inequality. These are some pointers to literature.

Bruce Boldon, Narsingh Deo and Nishit Kumar.Minimum-weight degree-constrained spanning tree problem

The minimum spanning tree problem with an added constraint that no node in the spanning tree has the degree more than a specified integer, d, is known as the minimum-weight degree-constrained spanning tree (d-MST) problem. Such a constraint arises, for example, in VLSI routing trees, in backplane wiring, or in minimizing single-point failures for communication networks. The d-MST problem is NP-complete. Here, we develop four heuristics for approximate solutions to the problem and implement them on a massivelyparallel SIMD machine, MasPar MP-1. An extensive empirical study shows that for random graphs on up to 5000 nodes (about 12.5 million edges), the heuristics produce solutions close to the optimal in less than 10 seconds. The heuristics were also tested on a number of TSP benchmark problems to compute spanning trees with a degree bound d = 3.
MR1469650 (98h:68181) Fekete, Sándor P. ; Khuller, Samir ; Klemmstein, Monika ; Raghavachari, Balaji ; Young, Neal . A network-flow technique for finding low-weight bounded-degree spanning trees. J. Algorithms 24 (1997), no. 2, 310--324.
MR1469648 (98d:68165) Guttmann-Beck, Nili ; Hassin, Refael . Approximation algorithms for min-max tree partition. J. Algorithms 24 (1997), no. 2, 266--286.
MR2006103 (2004h:68154) Hassin, Refael ; Levin, Asaf . Minimum spanning tree with hop restrictions. Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms (Washington, DC, 2001). J. Algorithms 48 (2003), no. 1, 220--238.
MR2480226 (2010f:68072) Srivastav, Anand ; Werth, Sören . Probabilistic analysis of the degree bounded minimum spanning tree problem. FSTTCS 2007: Foundations of software technology and theoretical computer science, 497--507, Lecture Notes in Comput. Sci., 4855, Springer, Berlin, 2007.