OddPath be a set of all G, s, t, such that G is a directed graph with a path from node s to node t, and the shortest such path has odd number of edges.

How can I show OddPath is NL? I think about it for a long time, the main problem is that I don't know how to get length of the shortest path in non-deterministic log place.

I tried to use coNL = NL to attack this problem. The problem become "find G with the shortest path with even number of edges". Again, I can't deal with "shortest path".

  • $\begingroup$ Is it a weighted graph or unweighted graph? Do you know how to test reachability in NL and in coNL? $\endgroup$ – D.W. Apr 21 '17 at 21:59
  • $\begingroup$ It does not say whether it is a weighted or unweighted graph. I know how to test the reachability in NL $\endgroup$ – TIANLUN ZHU Apr 21 '17 at 22:07
  • $\begingroup$ If you don't understand what the problem is asking, that might make it harder to solve the problem (it seems like that is a precondition to solving the problem). If you were assigned this in a course, I suggest you talk to your instructor or teaching assistant. If you got this from a book or other source, I suggest you edit the question to provide a proper citation for the source of the problem. Also there's a chance it might be useful to study existing references on how to test reachability in coNL (i.e., coNL algorithms for reachability). $\endgroup$ – D.W. Apr 21 '17 at 22:08

The graph is log-space reducible to the same question restricted to a leveled directed graph. We know the problem whether there is a path between s, t can be solved in NL, so the idea is to repeat the question for different distances. Let G be the leveled directed graph where v(i) denotes vertex v in level i.

while i<=N where N is the size of the original graph before leveling.
    check if path exists between s(1) and t(i+1) using an NL machine.
    if yes: 
        then return Accept if i is odd, else reject
    else: i++

If you have a copy of Sipser checkout page 333 for more about leveled graphs since that is where I got the idea.

  • $\begingroup$ Could you explain (1) what levelling is and (2) what its relevance to your algorithm is? Why does your algorithm require the graph to be levelled? It seems that levelling adds vertices: if it adds edges, isn't it going to also change the length of paths? $\endgroup$ – David Richerby Apr 22 '17 at 8:08
  • $\begingroup$ We create k copies of the vertices, and only allow edges to exist between vertices in one level and the copy in the next. So, if v and u have a directed edge in the original, then v(i) to u(i+1) will be an edge for i's in range. $\endgroup$ – user152152 Apr 22 '17 at 14:04
  • $\begingroup$ It is there because the problem asks if the length of the 'shortest' path is odd or not. s(1) and t(b) will only have a path if there is a path of length b-1. Also, if we started with the assumption that k-PATH is NL instead of just PATH in NL, then we wouldn't need leveling. $\endgroup$ – user152152 Apr 22 '17 at 14:13

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.