Assume we need to include a certain set of nodes in the tree within the whole graph, the generated tree can contain nodes other than the specified set of nodes. We also need the number of edges (or the total amount of edge weight) included in the tree is minimum.


1 Answer 1


This is the famous Steiner tree problem in graphs, which is known as NP-hard.

  • 12
    $\begingroup$ Of course, there are still algorithms for NP-hard problems. $\endgroup$ Jul 9, 2018 at 11:24
  • 7
    $\begingroup$ @DavidRicherby It does suggest that the OP would need to provide quite a lot more information in order to suggest which algorithm will meet their requirements. Often the key to an efficient algorithm on such a problem is to take advantage of structure in the data which let you sidestep the pathologically difficult cases. $\endgroup$
    – Cort Ammon
    Jul 9, 2018 at 19:56
  • 1
    $\begingroup$ @CortAmmon The question doesn't ask for an efficient algorithm: it asks for an algorithm. Even if no efficient algorithm is available for the asker's case, they still want an algorithm. $\endgroup$ Jul 9, 2018 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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