An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs

摘要

A spanning tree T of a graph G is called a tree t-spanner of G if the distance between every pair of vertices in T is at most t times their distance in G. In this paper, we present an algorithm which constructs for an n-vertex m-edge unweighted graph G: 1. a tree (2「log_2n」)-spanner in O(m log n) time, if G is a chordal graph (i.e., every induced cycle of G has length 3); 2. a tree (2ρ「log_2 n」)-spanner in O(mn log~2 n) time or a tree (12ρ「log_2 n」)-spanner in O(m log n) time, if G is a graph admitting a Robertson-Seymour's tree-decomposition with bags of radius at most p in G; and 3. a tree (2「t/2」「log_2 n」)-spanner in O(mn log~2 n) time or a tree (6t「log_2n」)-spanner in O(m log n) time, if G is an arbitrary graph admitting a tree t-spanner. For the latter result we use a new necessary condition for a graph to have a tree t-spanner: if a graph G has a tree t-spanner, then G admits a Robertson-Seymour's tree-decomposition with bags of radius at most「t/2」 and diameter at most t in G.