On the minimum eccentricity shortest path problem

In this paper, we introduce and investigate the Minimum Eccentricity Shortest Path (MESP) problem in unweighted graphs. It asks for a given graph to find a shortest path with minimum eccentricity. Let n and m denote the number of vertices and the number of edges of a given graph. We demonstrate that: a minimum eccentricity shortest path plays a crucial role in obtaining the best to date approximation algorithm for a minimum distortion embedding of a graph into the line; the MESP problem is NP-hard for planar bipartite graphs with maximum degree 3 and W[2]-hard for general graphs; a shortest path of minimum eccentricity k can be computed in O(n(2k+2)m) time; a 2-approximation, a 3-approximation, and an 8-approximation for the MESP problem can be computed in O(n(3)) time, in O(nm) time, and in O(m) time, respectively; in a graph with a shortest path of eccentricity k, a k-dominating set can be found in n(O(k)) time. (C) 2017 Elsevier B.V. All rights reserved.