1
$\begingroup$

$$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?

https://stackoverflow.com/questions/29640543/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.

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

    for v_j in neighbours(s)
        current, prev = v_j, s
        repeat
            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
$\endgroup$
  • 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
1
$\begingroup$

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.

$\endgroup$

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.