Vertex fusion under distance constraints

In this paper, we analyze parameter improvement under vertex fusion in a graph GG. This is a setting in which a new graph G′G′ is obtained after identifying a subset of vertices of GG in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex vv. We show that the corresponding problem is NP-Complete for the three parameters. We also find graph classes in which the problem can be solved in polynomial time.