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.

Improve this question
$\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$
    – Fedor Petrov
    Commented 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$
    – Florian Lehner
    Commented 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
    Commented Nov 26, 2017 at 21:04
  • $\begingroup$ @FlorianLehner I agree and thanks for the pointers to the publications! $\endgroup$
    – koalo
    Commented Nov 26, 2017 at 21:07

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .