On the union of intermediate nodes of shortest paths

Abstract

Consider a connected graph G=(V,E). For a pair of nodes u and v, denote by M (uv) the set of intermediate nodes of a shortest path between u and v. We are intertested in minimization of the union a <integral (u,vaV) M (uv) . We will show that this problem is NP-hard and cannot have polynomial-time rho ln delta-approximation for 0 <rho < 1 unless NPaS dagger DTIME(n (O(loglogn))) where delta is the maximum node degree of input graph. We will also construct a polynomial-time -approximation for the problem where H(a <...) is the harmonic function.