DAG, finding edges for subset of vertices

I have a DAG G=(V,E), it is adjacency list representation. I am trying to compress it according to some parameters that are attached to vertices.

Now I have a graph G=(V,E) and a list containing subset of V.

Any idea how can I efficiently find edges for subset vertices from original graph?

I need to connect the subset using the original graph.

Look at this graph

{9: [10], 7: [9], 8: [9], 6: [7], 3: [8], 2: [3, 4], 5: [4, 6], 4: [7], 1: [2]}

Now if I take the subset [1,4,7]

How do find connections for subset? please see the transitive closure as an issue. I need to find all edges but not the duplicates in transitive closure.

Put the subset (let's call it S) into a hashtable. Then walk through the adjacency list and for every edge look whether its first vertex is in the hashtable. This way you get all the edges you want in O(|S| + |E|).

A simple method would be to find the transitive closure of the original graph (using Floyd-Warshall) and then using that to add the edges to the resulting graph.

By finding the transitive closure, you have an adjacency matrix where matrix[x][y] is true whenever there is any path (direct or indirect) between vertices x and y in the original graph. Using that, you can simply add the edges (a,b) for each pair of vertices a and b in the subset graph iff matrix[a][b] is true (i.e. there was a path from a to b in the original graph).

This would end up adding more edges than strictly necessary, but it would give you an accurate subset graph.

First you will have to utilize some algorithm to get the transitive closure. From your example it seems that the graph is very sparse, so instead of Floyd-Warshall, use Johnson's Algorithm. Johnson's Algo requires O((V^2)*log V + VE) which is less that that of Floyd-Warshall's O(V^3) for sparse graphs. Note that this difference is appreciable only if you have a large sparse graph.

Now add the edges of the form < x,y> for each pair of vertices in the subset-graph if x is reachable from y (which will be given by Johnson's Algo).

If your subset is S, you can do |S| depth-first searches (or breadth-first searches) to determine the edges in your subset graph. Each search is O(V+E), so that's O(V^2+VE) or better O(S(V+E)), if S is small. You then might want to use a transitive reduction to remove unnecessary edges.

If your graph is not completely acyclic, it will almost certainly help to coalesce strongly connected components first. It is cheap to do and can reduce the work required substantially.