| The problem of embedding a graph metric into a "nice" and "simpler" host metric space with low distortion has been a subject of extensive research, motivated from several applications in various domains. "Nice" metric spaces are those with well-studied structural properties, allowing to design efficient approximation algorithms. Particular host metrics of choice, also favored from the algorithmic point of view, are trees, spanning trees and collection of them.;We investigate the embedability of a graph metric into a tree metric, a spanning tree metric and a collection of them and detect such metric tree-like structure in graphs. First, we investigate few graph parameters which capture and quantify the phenomenon of being metrically close to a tree. By bringing all those parameters together, we not only provide efficient means for detecting such metric tree-like structures in large-scale networks but also show how such structures can be used for fundamental primitives in many data and graph mining algorithms. Also, we present strong evidences that a number of real-life networks, taken from different domains exhibit tree-like structures from a metric point of view.;Second, we study collective tree spanners for graphs enjoying special Robertson Seymour's tree-decompositions, and demonstrate interesting consequences of obtained results. Specifically, we demonstrate a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative tree t-spanner (NP-hard problem), constructs a system of log2 n collective additive tree O(t log n)-spanners of G. That is, with a slight increase in the number of trees and in the stretch, one can "turn" a multiplicative tree spanner into a small set of collective additive tree spanners. We extend this result to demonstrate that, for every fixed k, there is a polynomial time algorithm that, given an n-vertex graph G admitting a multiplicative t-spanner with tree-width k -1, constructs a system of at most k(1 + log2 n) collective additive tree O(t log n)-spanners of G.;Finally, we provide an efficient algorithm to embed weighted graphs into tree metrics with proven theoretical bounds and good embedding results on real-world datasets. |
