2
$\begingroup$

 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,

$\endgroup$

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ Thanks a lot goldstern. I thinks this transformation is correct. I just wonder why we don't connect s directly to each variable instead of going through path o length n. That way we can have a tree of n + k edges, can't we? $\endgroup$
    – chepukha
    May 8, 2011 at 1:18
  • $\begingroup$ another problem with this transformation is that you're trying to limit the number of edges while the optimal tree must have minimum number of vertices. With the way you select the tree, the number of vertices is not minimum. $\endgroup$
    – chepukha
    May 8, 2011 at 5:02
  • $\begingroup$ You are right, the paths are not necessary. I edited my answer to simplify it (and also to clarify some points). $\endgroup$
    – Goldstern
    May 8, 2011 at 8:19
  • $\begingroup$ I do not understand your question about edges vs vertices. A tree with v vertices has v-1 edges. So you minimize the number of edges iff you minimize the number of vertices. $\endgroup$
    – Goldstern
    May 8, 2011 at 8:20
  • $\begingroup$ Maybe I didn't quite understand your proof. So let me give an example. Let say I have a 3SAT (x+y+z)(x+¬y+z). We can assign x=y=z=T. So, if we follow the proof, then we will get a tree with 6 vertices and n+k=2+3=5 edges. However, I can have another smaller tree that can have the same shortest paths to vertices in M={C1, C2}. That tree has 3 edges connecting the vertex representing x with s, C1, and C2. It also has only 4 vertices. Am I missing something here? $\endgroup$
    – chepukha
    May 8, 2011 at 8:48
0
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thank you. I didn't have time to verify your proof here but I think the above transformation is correct. $\endgroup$
    – chepukha
    May 8, 2011 at 1:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.