M0jo's blog

How to check the graph for the uniqueness property of the path?
By M0jo, history, 4 years ago, In English

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?

  • Vote: I like it
  • +3
  • Vote: I do not like it

»
4 years ago, # |
← Rev. 4   Vote: I like it +5 Vote: I do not like it

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.
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply