subgraph of an acyclic graph covering some selected nodes but other nodes not on the path

Question

I have a undirected and unweighted (or all edges are weighted 1) acyclic graph (G=VxE). Some of this graph's nodes are selected as sV (sV is subset of V). Problem is, I want to find the subgraph covering all selected nodes. Naturally some non selected nodes can be covered. But the nodes that are not on the desired subgraph are restricted. These restricted nodes should not be in the solution subgraph unless they are on only the one path between two selected nodes. An example:

  A B C D
A - + + -
B + - + -
C + + - +
D - - + -

A, B, C, D are nodes, + represents inclusion of edges. For this graph B and D are selected nodes. The solution I want for this example is as follows: The subgraph consists nodes B,C,D and edges (B,C), (C,D) *. Note that A is not in the subgraph as intended. What kind of approach helps me to find this type of subgraphs? Thanks for ideas.

*(X,Y) represent an edge between nodes X an Y.

Answer 1

I feel like I misunderstood the problem but let's give it a try.

First we have to assume/check that your graph is a connected component http://en.wikipedia.org/wiki/Connected_component_(graph_theory) and then you can start :

solution = sV
foreach n1 in sv
    foreach n2 in sv, n2!=n1
        path = findPath(G,n1,n2)  
        // this should return at least one path because of connectivity
        // and no more than one
        for each n3 in path
            solution += n3

Does it perform what you want to do ?

Answer 2

Another approach is more tree-oriented (as a tree is a acyclic connected graph).

Let's say you've structured a graph as a tree, you have :

• a root r
• from a node, a way to retrieve its sons and it's parent (if any)

Also, for more convenience, I assumed you can add a marker on nodes (in the node/graph/tree itself or another structure on the side).

Then, you can simply :

• add a marker for every node giving its number of descendants which are in sv (this can be done by going up the tree starting from the different elements of sv (breaking when you encounter the root of the tree))

• starting from the node n :

  retrieve the sons with a number greater or equal to 1 # other sons are useless
  
  if there's no son with this property :
          stop
  else if there's only son s with this property :
          if n is in nv
                  add s to sv # s is needed to go to n
  else if there's many sons with this property :
          add n to sv # n is needed to join descendant of different branches
  foreach each son s
          start again from s
  

I haven't really thought about it much but I feel like this could work.