# Finding the subgraph with the largest diameter

Given an undirected connected graph $G=(V, E)$. Find the induced subgraph $G[W]$ of $G$ with the largest diameter $d$, where the diameter is the largest distance between any pair of vertices.

The diameter of the graph below is 2, because we can get from every node to every other node over at most 2 edges. However, when removing a node, for example C (and it's adjacent edges), the diameter increases to 3, because we need 3 edges from A to E.

One possible solution would be to generate all subgraphs, calculate the diameter and select the largest. However, the number of subgraphs rises exponentially with the number of vertices, so this is infeasible.

• Equivalently, we want to find the longest induced path. According to Wikipedia, it is NP-hard to find it. en.m.wikipedia.org/wiki/Induced_path Nov 26, 2017 at 20:47
• If I'm not mistaken, finding the induced subgraph with the largest diameter also gives the length of the longest induced path which (unless P = NP) can't even be efficiently approximated, see P. Berman, G. Schnitger, On the complexity of approximating the independent set problem, Information and Computation 96 (1), 1992. Nov 26, 2017 at 20:53
• @FedorPetrov That seems to be the case, thanks! Would you convert your comment into an answer, so I can accept it? Nov 26, 2017 at 21:04
• @FlorianLehner I agree and thanks for the pointers to the publications! Nov 26, 2017 at 21:07