HalfFragment's blog

Simple Cycles
By HalfFragment, history, 6 years ago, In English
1. Given an undirected weighted graph and two node s, t. How one can print any simple cycle that passes through both s and t or say no such cycle exist?

2. If more than one such cycle exist then How one can print cycle with minimum weight among them??

Is it possible to solve these problem in linear time?? Please suggest me optimal solution for these problem...It will be much helpful if one can provide code also.
  • Vote: I like it
  • +7
  • Vote: I do not like it

Comments Comments (19)
| Write comment?
»
6 years ago, # |
  Vote: I like it -12 Vote: I do not like it
  1. Find shortest path from s to t. Remove that path and then check if t is reachable from s.
→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    This Greedy Algorithm will not work in this graph..
    (1, 2) weight = 1
    (2, 4) weight = 100
    (1, 3) weight = 100
    (3, 4) weight = 1
    (2, 3) weight = 1
    where (x, y) represent edge;
    and s = 1, t = 4,

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
  1. I think that you can run a linear-time bridge finding algo. If there is at least one edge that is not a bridge, then you have a simple cycle. This works because, if you consider the DFS spanning tree and gradually add more edges to it, if an edge is not an bridge, that means that there is a path from a child node to nodes that are visited earlier or same time as its ancestors.

Edit This answer is incorrect because I missed the fact that the cycle must contain both s and t.

→ Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

2 The best that I can think of is a quadratic time algorithm. Run MST algorithm. Then try adding an arbitrary edge to the MST. There will be a cycle for sure. Now, you can use DFS to check the weight of this cycle. Do this for every edge.

Edit This answer is incorrect because I missed the fact that the cycle must contain both s and t.

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 5   Vote: I like it +3 Vote: I do not like it

    This does not work. A minimum cycle can need more than one edge which is not in the MST. example graph:

    s = 0, t = 1
(0, 1) w = 4
(1, 2) w = 4
(2, 3) w = 4
(4, 5) w = 4
(5, 0) w = 4
(1, 3) w = 5
(3, 4) w = 5
(4, 0) w = 4
    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I missed the point that the cycle must contain s and t so my answer is incorrect for your counterexample.

      On a side note, I believe it should be correct if we remove that restriction (and assume non-negative weights). Because there is no way we can add more than 1 edge to the MST to create a minimum cycle unless there are negative weights.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 5   Vote: I like it 0 Vote: I do not like it

        that should be right, yes. I believe with negative weights this becomes NP hard and it can be reduced to a hamilton cicle problem (just set every weight to $$$-1$$$, than there is a hamilton circle iff the weight of the minimal circle is $$$-n$$$).

        → Reply
»
6 years ago, # |
← Rev. 4   Vote: I like it +25 Vote: I do not like it

For problem one we can use Menger's theorem which tells us that there are two vertex disjoint path (those form a simply cycle) between $$$s$$$ and $$$t$$$ iff there is no single vertex which seperates them. This is equivalent to they are in the same biconnected component (vertex connectivity) which can be found in $$$\mathcal{O}(n)$$$. Then those two paths can be found with a bfs.

problem two with negative weights is NP hard... best Solution for problem two with positive weights i can think of right now is to use a min cost max flow based approch...

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    "This is equivalent to they are in the same biconnected component (vertex connectivity) which can be found in O(n)."

    May you suggest how i can find a biconnected component consist of vertex s and t.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I think you can just compute biconnected components of the graph (there are well-known algorithms that you can find online). Then check if s and t are in the same biconnected component.

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      Can't you just find two vertex-disjoint paths with two dfs ?

      The first dfs starts from s and ends to t and finds a path.

      The second dfs starts from s and ends to t but uses only vertices that first path did not use.

      The union of these paths is the cycle you need. Isn't that right and simpler ?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Here Again, This will be counterexample
        (1, 2) weight = 1
        (2, 4) weight = 100
        (1, 3) weight = 100
        (3, 4) weight = 1
        (2, 3) weight = 1
        where (x, y) represent edge;
        and s = 1, t = 4,
        what if first dfs find path 1-2-3-4??

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

How can we count the total number of simple cycles in an undirected graph?

→ Reply