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.


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.

  • $\begingroup$ That violates the sum condition. $\endgroup$ – MAKCL Jun 19 '10 at 17:11
  • $\begingroup$ Thanks. I made my conditions too liberal. This comes from a problem Ive been working on with more stringent conditions, which your solution would violate. I should probably cease to elaborate, however, I would ask if anyone can point me to the literature where this kind of thing might be dealt with - that is relating the average to the MST. Thanks again. $\endgroup$ – MAKCL Jun 19 '10 at 18:03
  • 2
    $\begingroup$ If you don't mind elaborating, I'd like to hear the more stringent problem. It might be easier for someone to give you the right pointer if they had more details. The problem seems pretty interesting. $\endgroup$ – Tony Huynh Jun 19 '10 at 21:24

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.

  1. 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.

  2. 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.

  3. MR1469648 (98d:68165) Guttmann-Beck, Nili ; Hassin, Refael . Approximation algorithms for min-max tree partition. J. Algorithms 24 (1997), no. 2, 266--286.
  4. 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.
  5. 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.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.