Clever Geek Handbook

Minimize the set of edges in a directed graph while maintaining related components

Here's the complete question:

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

  • G 'has the same connected components as G
  • G 'has the same component graph as G
  • E 'is minimized. That is, E 'as small as possible.

This is what I got:

Run the tightly coupled component algorithm first. We now have tightly coupled components. Now go to each strong bound component and within that SCC do a simple loop; that is, a cycle in which the only vertices that repeat are the start / end nodes. This will minimize edges in each SCC.

Now we need to minimize the edges between the SCCs. Alas, I cannot think of how to do this.

My 2 questions are: (1) Does the previous algorithm work correctly in terms of minimizing edges between SCCs? (2) How can the edges between SCCs be minimized.

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

+3


source to share


2 answers


  • The algorithm seems to be correct if you allow closed moves (i.e., repeated vertices). Regular loops may not exist (eg in component "8") and find them NP-hard.

  • It seems that it is sufficient to group the intercomponent edges by the ordered pairs of components they connect, and leave only one edge in each group.



+1


source


Regarding step 2, to minimize the boundaries between SCCs, you can randomly select a vertex and start DFS, keeping only the longest path for each pair (root, end) while deleting other paths. Store all vertices found in list L.



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

0


source






More articles:


All Articles