Consider UCYCLE, the problem of recognizing undirected graphs containing a cycle. On the one hand, it's in LOGSPACE, see this stackexchange thread: start at every vertex $v$ a DFS and check whether it returns to $v$ along a different edge than it left. On the other hand, there are linear-time algorithms in the number of edges: start by the partition of the vertices into singletons, and for each edge merge the corresponding parts if they're different, and return TRUE if they're the same. Maintain the partition using e.g. disjoint-set forests.

My question: is there are linear-time, LOGSPACE algorithm? and, ideally, one that can be implemented [solutions starting by "add an expander graph to $G$" will be accepted, but are not what I am looking for].

  • $\begingroup$ In what model are you looking for "linear time"? For a 1-tape TM, $TIME(o(n\log n))=REG$, and UCYCLE is probably not a regular language. $\endgroup$
    – Shaull
    Nov 30 '21 at 9:09
  • $\begingroup$ @Shaull yes, I agree I'm a bit vague here. The linear-time algorithm I give is valid for RAM machines, I believe; but what I really have in mind is a programming language with constant-access pointers and pointer arithmetic, say C with unbounded integers for definiteness. $\endgroup$
    – grok
    Nov 30 '21 at 10:13
  • $\begingroup$ - well, UCYCLE seems at least as hard as Undirected Connectivity, which is in SL, and Reingold's famous result shows that SL=L. However, I don't think the algorithm proposed in the proof of SL=L is in linear time on a RAM machine. Moreover, this algorithm definitely starts with "add an expander..." $\endgroup$
    – Shaull
    Nov 30 '21 at 10:25

Your Answer

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

Browse other questions tagged or ask your own question.