# Algorithm to find a path connecting given nodes in a graph

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?

• 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. – Yuval Filmus Apr 25 '16 at 23:04
• I'm looking at a possibility to connect those x nodes resulting in a subgraph. x = n-1 in this case. – suhas bhairav Apr 25 '16 at 23:35
• So it's more like spanning tree or Steiner tree. – Yuval Filmus Apr 26 '16 at 6:01
• I believe Steiner tree will solve my problem. – suhas bhairav Apr 26 '16 at 11:52