Could this be a NP complete?

Question

 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,

Answer 1

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.

Answer 2

Just a rough idea: (I am not really an expert on graph theory, so there may be a much better upper bound.)

You can group the vertices according to their distance to $s$, say

$L_i=\{v\in V|dist(s,v)=i\}$

Then of course the $L_i$ are pairwise disjoint. Any shortest path from $s$ to a given vertex $v$ has to pass the $L_i$ ascending (you can easily proof this fact), so first a vertex from $L_1$, then one from $L_2$, and so on. That means there are at most $\prod_{i=1}^{dist(s,v)-1}|L_i|$ shortest paths. As $|L_i|\leq |V|$, you have a polynomial upper bound.

While thinking about it: There might be a way to press this bound much lower, as $|L_i|=|V|$ only happens when all vertices have distance 1, which means the shortest path is the direct connection between $s$ and $v$. For decreasing amount of vertices in the $L_i$, the possible length of the path grows. You probably could use this to get a better bound.

I do not see why the rest of your algorithm should not work.