The diameter of a graph is the largest of all shortest-path distances in it. How can we find a tree of maximum diameter within an undirected unweighted graph?

Note that the tree does not have to be a spanning tree.

  • $\begingroup$ It makes no difference whether the tree is spanning or not. If there is a tree of diameter $d$, there is a spanning tree of diameter $d$ or greater so the question "Is there a tree of diameter $d$?" has the same complexity as "Is there a spanning tree of diameter $d$?" $\endgroup$ – David Richerby Nov 6 '14 at 12:46

This (probably) can't be done efficiently since a maximum-diameter spanning tree could be a Hamiltonian path.

More specifically, an $n$-vertex graph has a tree of diameter $n-1$ as a subgraph if, and only if, it has a Hamiltonian path (the tree is the Hamiltonian path). Therefore, the problem of finding a maximum-diameter subtree is NP-hard, since you can reduce Hamiltonian path to it by finding the maximum-diameter subtree and checking whether or not it's a path of length $n-1$.

  • $\begingroup$ The problem includes the Hamiltonian path problem, and therefore is NP complete. $\endgroup$ – Bangye Nov 6 '14 at 12:40
  • 2
    $\begingroup$ @Bangye Careful. $\Sigma^*$ includes Hamiltonian path, too. $\endgroup$ – Raphael Nov 6 '14 at 12:58

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.