
```
 Given a undirected and unweighted graph G(V,E). M is a subset of vertices of V. 
 s is a vertex in V - M.
 Find an optimal tree T of G defined as:
 (1) M and s are in V(T)
 (2) Distance (which is length of the shortest path) from s to any vertex in M in tree T is equal to distance from s to these vertices in G
 (3) No other tree T' satisfying condition (1) and (2) can have fewer nodes than T  
```


```
My idea was to use Dijkstra's algorithm to find shortest path from s to all vertices in M. However, there could be many shortest paths from vertex s to a vertex v. So, I will pick the shortest path that has the most number of vertices in M.
 Merge all these paths together to get tree T.  
```


```
This seems to solve the problem in polynomial time. However, my concern is the number of shortest path from vertex s to a vertex v could be very large that can make this algorithm be exponential. I don't know if there is any upper bound for the number of shortest path between 2 vertex in a graph.  
```


```
Also, does any one know if this problem is NP problem or it could be solved in polynomial time?
 Thanks,
```




Could this be a NP complete?
The problem is NP-complete. 


I think that the following algorithm describes a polynomial reduction of SAT to your problem. 


Let S be an instance of SAT. So you have a finite set of clauses $C\_1$, $C\_2$, ...,$C\_n$.  

and a finite set of variables $p\_1$, $p\_2$, ..., $p\_k$. Each clause contains some literals, i.e., variables $p\_i$ and/or negated variable $\lnot p\_i$. (in 3sat we assume that each clause contains at most 3 literals.)
We may assume that for each variable $p$ there is a clause $C\_p$ containing only $p$ and $\lnot p$, so $n\ge k$. 


Make S into a graph as follows: There is a special vertex $ s$. For each variable $p$ there are two vertices $p$ and $\lnot p$, both connected to $s$ (EDITED to simplify) by an edge. There is a vertex for every clause. Each literal $L$ is connected by an edge to each clause $C$ in which $L$ appears. 


The set $M$ will be the set of all clauses. 


If the original problem S was satisfiable, say with an assignment $A$, then 
 then there is an optimal tree with $n+k$ edges:
Connect $s$ with all literals which are true under $A$, and connect each clause $C$ with a literal $L$ in $C$ that is true under $A$. 


(EDITED to clarify and to close a gap:) Conversely, if there is an optimal graph with at most $n +k$ edges, then:


1. Each clause has to be on the tree, so it has to be connected to some literal. This costs $n$ edges.
2. For each variable $p$, either $p$ or $\lnot p$ has to be on the tree (because of $C\_p$), so either $p$ or $\lnot p$ has to be connected (by an edge) to $s$ (because the distance has to be $1$). These connections cost $k$ edges.
3. So from each such pair EXACTLY one is connected with $s$. Those literals which are connected to $s$ now define a satisfying truth assignment.


Hence the instance $G,M$ of your problem that I constructed from the SAT problem $S$ has a solution of size at most $n+k$ iff $S$ is satisfiable. So any algorithm to solve your problem also solves SAT. Hence your problem is NP-complete.


