Блог пользователя chaotic_iak

Автор chaotic_iak, 9 лет назад, По-английски

I was working on an interesting problem. (Tip: Homework of algorithm courses can be fun!)

Find the minimum number of (directed) edges to introduce into a directed graph to make it strongly connected (from any vertex you can go to any other vertex). Also, find one configuration of edges to add that satisfies the property and reaches the minimum.

I wonder if this problem is a well-known problem, and if any, what name it is known with? I saw this Stack Overflow question which asks about the minimum number of edges only, not finding one such configuration, and it's said to be "a really classical problem".

I also wonder if there is a more efficient algorithm. My algorithm works in O(V3), which involves several steps to reduce the graph in question into a directed acyclic graph, a weakly connected directed acyclic graph, a connected bipartite graph, and finally giving the answer. A friend says that there is a literature on the internet giving algorithm, but I haven't managed to find it. Or is there an even better algorithm?

  • Проголосовать: нравится
  • +18
  • Проголосовать: не нравится

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

There was a similar post in Russian half a year ago. You can find paper in English in the comments and my comment in Russian which briefly describes solution (not sure if it's same as in paper).

»
9 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Divide graph into strongly connected components and you will get a DAG. Number of edges you need to add is a maximum of numbers of vertices with 0 indegree and 0 outdegree (vertices = SCCs). That is a trivial lower bound, but to show that it is sufficient it is significantly harder :P.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    For searching the number, it has been given in the Stack Overflow thread above. Proving it's sufficient is simple; just give any algorithm that works and prove its correctness. Optimizing the algorithm is the hard part.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      For the algorithm I described in my comment providing the algorithm was the hard part, optimization from O(N3) to O(N) took only one very simple observation.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Could you show me that observation?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Sure. The cubic solution I've mentioned was about finding the maximal matching between sources and sinks, and then adding some edges.

          The observation is that we don't really need "maximal" matching, we only need a "blocking" matching (like in Dinic's algorithm), i.e. one which cannot be extended by adding another disjoint path from a source to a sink. And finding "blocking" matching is significantly easier: you just run DFS while you can.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    For that trivial lower bound solution, should we add vertices with 0 degree to both numbers of vertices with 0 indegree and 0 outdegree ?

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well think about it. Would the graph be strongly connected if you only added in-edges to those vertices? Why? What might be the intuition for adding these edges anyway?

»
4 года назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

There is a question which exactly asks this. https://codeforces.com/contest/22/problem/E

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
9 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I know this is an old post, but I had this question too and it took me some time to find out the answer.

This post is still one of the top google searches for "how to add edges to make a strongly connected graph", so I'm linking to this Stack Overflow article which describes the algorithm for creating the configuration: https://stackoverflow.com/questions/12681785/creating-strongly-connected-components-from-a-dag

»
6 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I have coded it