Vertex fusion under distance constraints

In this paper, we analyze parameter improvement under vertex fusion in a graph G . This is a setting in which a new graph G ′ is obtained after identifying a subset of vertices of G in a single vertex. We are interested in distance parameters, in particular diameter, radius and eccentricity of a vertex v . 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.