1
$\begingroup$

Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x < n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for such a scenario?

$\endgroup$
  • $\begingroup$ If $x = n$ then this sounds a lot like the NP-complete problem Hamiltonian Path. The case $x = n-1$ doesn't sound too much easier. Perhaps you should make clear what you mean by a path in this context. $\endgroup$ – Yuval Filmus Apr 25 '16 at 23:04
  • $\begingroup$ I'm looking at a possibility to connect those x nodes resulting in a subgraph. x = n-1 in this case. $\endgroup$ – suhas bhairav Apr 25 '16 at 23:35
  • 1
    $\begingroup$ So it's more like spanning tree or Steiner tree. $\endgroup$ – Yuval Filmus Apr 26 '16 at 6:01
  • $\begingroup$ I believe Steiner tree will solve my problem. $\endgroup$ – suhas bhairav Apr 26 '16 at 11:52
1
$\begingroup$

Your problem is known as the Steiner tree problem. While this problem is NP-complete, it has efficient constant-factor approximation algorithms.

$\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.