Find the odd shortest path is NL

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".

• Is it a weighted graph or unweighted graph? Do you know how to test reachability in NL and in coNL?
– D.W.
Commented Apr 21, 2017 at 21:59
• It does not say whether it is a weighted or unweighted graph. I know how to test the reachability in NL Commented Apr 21, 2017 at 22:07
• 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).
– D.W.
Commented Apr 21, 2017 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.

i=1
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.

• 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? Commented Apr 22, 2017 at 8:08
• 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. Commented Apr 22, 2017 at 14:04
• 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. Commented Apr 22, 2017 at 14:13