Tree 3-spanners in 2-sep directed path graphs: Characterization, recognition, and construction

A spanning tree TT of a graph GG is called a treett-spanner, if the distance between any two vertices in TT is at most tt-times their distance in GG. A graph that has a tree tt-spanner is called a treett-spanner admissible graph. The problem of deciding whether a graph is tree tt-spanner admissible is NP-complete for any fixed t≥4t≥4, and is linearly solvable for t=1t=1 and t=2t=2. The case t=3t=3 still remains open. A directed path graph is called a 2-sep directed path graph if all of its minimal a−ba−b vertex separator for every pair of non-adjacent vertices aa and bb are of size two. Le and Le [H.-O. Le, V.B. Le, Optimal tree 3-spanners in directed path graphs, Networks 34 (2) (1999) 81–87] showed that directed path graphs admit tree 3-spanners. However, this result has been shown to be incorrect by Panda and Das [B.S. Panda, Anita Das, On tree 3-spanners in directed path graphs, Networks 50 (3) (2007) 203–210]. In fact, this paper observes that even the class of 2-sep directed path graphs, which is a proper subclass of directed path graphs, need not admit tree 3-spanners in general. It, then, presents a structural characterization of tree 3-spanner admissible 2-sep directed path graphs. Based on this characterization, a linear time recognition algorithm for tree 3-spanner admissible 2-sep directed path graphs is presented. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep directed path graph is proposed.