6
$\begingroup$

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.

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • 12
    $\begingroup$ Of course, there are still algorithms for NP-hard problems. $\endgroup$ – David Richerby Jul 9 '18 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 - Reinstate Monica Jul 9 '18 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$ – David Richerby Jul 9 '18 at 23:24

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.