Subgraph algorithm

Question

I would like to know if there is an efficient algorithm S = F(v,G) to construct a subgraph S out of a DAG G = (V,E) such that all the paths in S contain the vertex v of V. If so, it is possible to efficiently extend F to F'(N,G) for a set of vertices N. I am open to any data structures for storing the DAG G initially.

Actually a condition I forgot to add would be that G has a unique vertex r with no incoming edge and a path must be of the form where d is a vertex with no outgoing edge.

Another condition I have missed is given the extended F'(N,G) such that for all v,w of N if < r,..,v,..,w > where w is a sink, then we should disregard for paths < r,..,v,..,x > where x != w.

I actually have one solution but it does not scale, when #V > 2000 and #N > 2.

Answer 1

I assume that you are looking for the largest subgraph S of G = ( {r} + V + {d}, E ) where r is the unique source node and d is the sink such that every path from r to d passes a specific node v.

My proposed algorithm:

1. Find all paths between r and v using e.g. the answers provided in http://stackoverflow.com/questions/713508/find-the-paths-between-two-given-nodes

2. Find all paths between v and using the same algorithm. Since G is acyclic, no path from v to d can lead back to a path already found in step 1. Thus, in the resulting graph all paths between r and d will pass v.

Answer 2

Resultant graph contains nodes that are reachable from v and the nodes v is reachable from (or, nodes that are reachable from v in a transposed subgraph). Getting the set of reachable nodes can be done efficiently.

This may be extended easily for a set of nodes: you should just add them all at the beginning of your breadth-first search.