MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

Are the following to problems in RL complexity class? Proof outline?

1. L={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v}

2. R={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v, and at least one circle which itself does not contain vertex v}

-
What is RL complexity class? – Stefan Geschke Jan 6 2011 at 19:40
RL = Randomized Logarithmic space: en.wikipedia.org/wiki/RL_%28complexity%29 . This question is more suited to CS Theory StackExchange, cstheory.stackexchange.com . – Joseph O'Rourke Jan 6 2011 at 23:55

In fact, since Reingold proved that STCONN is in L these languages are also in L.

The proof for the first is the following. For every u neighbor of v, delete the uv edge and check whether u and v are connected in the resulting graph. If yes, then there is a cycle. If the answer is no for all u, then there is no cycle containing v.

The proof of the second is similar, first check for a cycle containg v, then consider all the edges of v deleted and check whether there is a cycle in the remaining graph, e.g. as before for every pair of vertices.

-