Suppose I am given an undirected and unweighted graph and a subset of nodes from the graph.

Now my target is to find the smallest tree or path that connects all the subset nodes. The order of nodes does not matter and neither the starting node. Any node can be the starting node.

My question is similar to Algorithm to find minimum spanning tree of chosen vertices but all the nodes have weight equal to 1. Hence, I am trying to find the tree with least number of links.

CodePudding user response：

Extending the answer of the question you linked, you are now looking for an unweighted Steiner tree.

It is however also NP-hard, see this question on cstheory.stackexchange.