8
$\begingroup$

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.

Exemplary graph with 5 nodes in a circle

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.

$\endgroup$
4
  • 6
    $\begingroup$ 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 $\endgroup$ Nov 26, 2017 at 20:47
  • 4
    $\begingroup$ 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. $\endgroup$ Nov 26, 2017 at 20:53
  • $\begingroup$ @FedorPetrov That seems to be the case, thanks! Would you convert your comment into an answer, so I can accept it? $\endgroup$
    – koalo
    Nov 26, 2017 at 21:04
  • $\begingroup$ @FlorianLehner I agree and thanks for the pointers to the publications! $\endgroup$
    – koalo
    Nov 26, 2017 at 21:07

1 Answer 1

6
$\begingroup$

Equivalently, we want to find the longest induced path. According to Wikipedia, it is NP-hard to find it:

It is NP-complete to determine, for a graph G and parameter k, whether the graph has an induced path of length at least k. Garey & Johnson (1979) credit this result to an unpublished communication of Mihalis Yannakakis.

http://en.wikipedia.org/wiki/Induced_path

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.