Heuristics for t-admissibility with complex network approach

The t-admissibility is a min-max problem that concerns to determine whether a graph G contains a spanning tree T in which the distance between any two adjacent vertices of G is at most t in T. The stretch index of G, σ(G), is the smallest t for which G is t-admissible. This problem is in P for t ≤ 2, NP-complete for σ(G) ≤ t, t ≥ 4, and remaining open for t = 3. Recently, Couto et al. (2022) developed some greedy heuristics to construct a candidate solution tree, but left open how to decide between two vertices when both have equal chances of being taken in a greedy step. This criterion is important, since different branches can yield different stretch indexes. In order to answer such a question, we develop four new heuristics by exploring vertex importance of complex network. The results are compared considering Barab´asi-Albert, Erd¨os-R´enyi, Watts-Strogatz, and Bipartite graphs.