Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.
  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}

share|improve this question
2  
What is RL complexity class? –  Stefan Geschke Jan 6 '11 at 19:40
1  
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 '11 at 23:55

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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