algorithmtime-complexitygraph-theorydirected-graphedges

Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices


Given an directed acyclic graph, create a strategy so that there is a bidirectional path between all possible Vertices

You can attain this by adding edges. Propose a strategy for solving this with adding as little edges as possible A Vertice on the input graph can be without edges.

EXAMPLE: input acyclic directed graph To solve this graph the most efficient way, we need to add ONLY 2 edges: solved directed graph with every vertice having biderectional path to another vertice

Keep in mind that the algorithm doesn't need to be perfect, also NO NEED to code anything (unless you want to:)).


Solution

  • Consider a DAG that has m vertices with in-degree 0 and n vertices with out-degree 0:

    Obviously, you will need to add m edges incoming to the in-degree 0 vertices, and n edges outgoing from the out-degree 0 vertices, so the best you can hope for is max(m,n) new edges. We can achieve this.

    First, if m > n, then connect in-degree 0 vertices until m = n. Otherwise connect out-degree 0 vertices until m = n.

    Now we have m=n, which we will maintain:

    • Find a vertex with in-degree 0 that doesn't reach all the vertices with out-degree 0. If there isn't one, then connect out-degree 0 vertices arbitrarily to in-degree 0 vertices and you're all done.
    • Otherwise, connect an out-degree 0 vertex that it does reach to an in-degree 0 vertex that reaches an out-degree 0 vertex that it doesn't reach. This reduces m and n by 1.
    • Repeat until you're done.