Distance Approximating Trees: Complexity and Algorithms

摘要

Let Δ≥1 and δ ≥ 0 be real numbers. A tree T = (V, E′) is a distance (Δ, δ)-approximating tree of a graph G = (V, E) if d_H(u, v) ≤ Δ d_G(u,v) + δ and d_G(u,v) ≤ Δ d_H(u,v) + δ hold for every u, v ∈ V. The distance (Δ, δ)-approximating tree problem asks for a given graph G to decide whether G has a distance (Δ, δ)-approximating tree. In this paper, we consider unweighted graphs and show that the distance (Δ, 0)-approximating tree problem is NP-complete for any Δ ≥ 5 and the distance (1, 1)-approximating tree problem is polynomial time solvable.