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

Автор M0jo, история, 4 года назад, По-английски

Hi, everyone

Some directed graph is given. Check the graph for the uniqueness property of the path(for any two vertices v u, there is no more than one simple path with the beginning in u and the end in v). Simple path is a non-empty path whose vertices are all pairwise distinct.

Does anyone know a solution to this problem faster than running BFS from each vertex?

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

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

Not sure all cases are correct but smth like this might work:

Find strongly connected components in O(m)

  • Suppose strongly connected component is not a cycle. Find some cycle there and any additional path will give you non-uniqueness.
  • Suppose on condensed graph there's non-uniqueness, then there is one in the original graph (you can find all of them in O(nm/32) with bitsets or maybe even in O(m)) (multiedges count as non-uniqueness)
  • It seems that if path is unique in condensed graph and each component is a cycle, then everything is unique.
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    BTW, What is your definition for simple paths beetween $$$v$$$ and $$$v$$$? Depending on it, my solution won't work on components that are pair of cycles with common vertex. But probably there's a fix for that as well

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

      In this problem, I assume that a simple path is a path whose vertices are all pairwise distinct.

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

        So is empty path from $$$v$$$ to $$$v$$$ simple? Is a cycle from $$$v$$$ to $$$v$$$ a simple path?

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

          The path must be non-empty. If you follow the definition I gave above, the loop will not be a simple path because it will contain two vertexes v.

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

            Well, it's not at all clear from the definition as written.

            ok, anyway, it seems that you are using the most reasonable definition and with this definition the solution as written doesn't work because there are other types of "save" SCCs like mentioned two-cycles component. But it looks like you can look at cut points and block in each SCC and it each one is a cycle you are safe again.