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
Improve this question
$\endgroup$
8
  • 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, 2017 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, 2017 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, 2017 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, 2017 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, 2017 at 19:15

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
1
$\begingroup$

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.

Improve this answer
$\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.