L={(G,v)|G is an undirected graph containing at least one circle which itself contains vertex v}
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}
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
2
|
|
||||||||
|
|
2
|
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. |
||
|
|
