CODEWITHSUNDEEP
algorithmgraph-theorydirected-acyclic-graphsedgesclrs
user678392
user678392

Reputation: 2031

Minimize set of edges in a directed graph keeping connected components

Here is the full question:

Assume we have a directed graph G = (V,E), we want to find a graph G' = (V,E') that has the following properties:

  1. G' has same connected components as G
  2. G' has same component graph as G
  3. E' is minimized. That is, E' is as small as possible.

Here is what I got:

First, run the strongly connected components algorithm. Now we have the strongly connected components. Now go to each strong connected component and within that SCC make a simple cycle; that is, a cycle where the only nodes that are repeated are the start/finish nodes. This will minimize the edges within each SCC.

Now, we need to minimize the edges between the SCCs. Alas, I can't think of a way of doing this.

My 2 questions are: (1) Does the algorithm prior to the part about minimizing edges between SCCs sound right? (2) How does one go about minimizing the edges between SCCs.

For (2), I know that this is equivalent to minimizing the number of edges in a DAG. (Think of the SCCs as the vertices). But this doesn't seem to help me.

Upvotes: 4

Views: 3473

Answers (2)

Alan Yang
Alan Yang

Reputation: 66

Regarding the step 2,minimize the edges between the SCCs, you could randomly select a vertex, and run DFS, only keeping the longest path for each pair of (root, end), while removing other paths. Store all the vertices searched in a list L.

Choose another vertex, if it exists in L, skip to the next vertex; if not, repeat the procedure above.

Upvotes: 0

Rafał Dowgird
Rafał Dowgird

Reputation: 45131

  1. The algorithm seems right, as long as you allow for closed walks (i.e. repeating vertices.) Proper cycles might not exist (e.g. in an "8" shaped component) and finding them is NP-hard.

  2. It seems that it is sufficient to group the inter-component edges by ordered pairs of components they connect and leave only one edge in each group.

Upvotes: 2

Related Questions