Hardness and Efficiency on Minimizing Maximum Distances for Graphs With Few P4's and (k,ℓ)-graphs
Fernanda Couto, Luís Cunha · Electronic Notes in Theoretical Computer Science · 2019
A tree t -spanner of a graph G is a spanning subtree T in which the distance between any two adjacent vertices of G is at most t . The smallest t for which G has a tree t -spanner is called tree stretch index. The problem of determining the tree stretch index (MSST) has been studied by: establishing lower and upper bounds, based, for instance, on the girth value and on the minimum diameter spanning tree problem, respectively; and presenting some classes for which t is a tight value. In 1995, the computational complexity of MSST was settled to be NP -hard for t ≥ 4, polynomial-time solvable for t = 2. However, deciding if t = 3 still remains an open problem. In this work, we show that graphs with few P 4 's are 3-admissible, generalizing our previous results obtained on cographs. Considering ( k , ℓ )-graphs, which are those graphs whose vertex set that can be partitioned into k independent sets and ℓ cliques, we partially classify the P vs NP -complete dichotomy for such a decision version. Although we prove that MSST for (2,1)-graphs is NP -hard, and knowing, beforehand, that determining the stretch index for chordal graphs is NP -hard as well, we present exact tree stretch indexes for (2,1)-chordal graphs. We also solve MSST for power cycle graphs, an interesting class under two different perspectives: they are families of (0, ℓ )-graphs, class for which we prove it is NP -hard to determine the stretch index when ℓ is a linear function on the size of the graph; and their stretch indexes are, at the same time, far from the natural lower bound given by the girth, and tight with respect to the diameter spanning tree upper bound.