$$UCYLE = \mathcal \{ <G> ~:~ G \text{ is an undirected graph that contains a simple cycle}\}.$$
There are two possible approaches to this exercise: Solving cycle in undirected graph in log space?


These two solutions are different. The instresting solution is second one (on stackoverflow). In this case we generally implement DFS in logspace. I can see that it does work (using DFS). However the question is:
Why we can't use this DFS algorithm to solve USTCON problem ?

However, I can see that we can't easily use this DFS to solve bipartity problem. It is not easy to count number of nodes in cycle.

Modified algorithm from stackoverflow (mentioned link) which should solve ustcon problem:

    for v_j in neighbours(s)
        current, prev = v_j, s
            idx = neighbours(current).index(v_j)
            idx = (idx + 1) % len(neighbours(current))
            current, prev = neighbours(current)[idx], current
            if current = t then return connection between s and t
        until current adjacent to s
return no_connection between s and t
  • 1
    $\begingroup$ Why do you think we can't use it? What we can't is to show that USTCON is in $\mathsf{L}$ using it. Because you will need to keep in memory every adjacent cycle. $\endgroup$ – rus9384 Aug 9 '17 at 18:12
  • $\begingroup$ @rus9384 I don't understand you. This algorithm is simply DFS in logspace. So we should be able to check connectivity between two verticles using this DFS. $\endgroup$ – Haskell Fun Aug 9 '17 at 18:22
  • $\begingroup$ Strongly connected component is not necessarily a cycle, it can be several adjacent cycles. You need to use contraction in that case which is not in log space. $\endgroup$ – rus9384 Aug 9 '17 at 18:57
  • $\begingroup$ Strongly connected component - it is about directed graphs, I consider only undirected. Once again - we have DFS in logspace. It allows us to check connectivity between two verticles in logspace. $\endgroup$ – Haskell Fun Aug 9 '17 at 19:05
  • $\begingroup$ Hm, in fact, thought are these: DFS algorithm only counts cycles where each vertex appear once. However, such cycles that are constructed of smaller cycles, as 8 for example, cannot be found using that algorithm. $\endgroup$ – rus9384 Aug 9 '17 at 19:15

Your algorithm is from the paper Problems complete for deterministic logspace by Cook and McKenzie, where it is used to perform DFS on trees, as well as for related problems such as cycle detection. Presumably it doesn't work on graphs with cycles.

| cite | improve this answer | |

This algorithm is not DFS. One of the problems it can solve is checking if a graph is cyclic, but it doesn't mean it is possible to traverse every cycle or path in graph (unless it's a tree), imagine graph made of triangle with squares on the sides - the algorithm will not detect the three-vertex cycle whatever (v,e) we start with. It will not detect the path between two vertices, that we can add in the middles of two sides of the triangle. Therefore UCYCLE problem can be solved in logspace, but BIPARTITE and especially USTCON require a different approach.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.