# Complexity of finding the shortest simple even s-t-path

Consider a graph $G=(V,E)$ and two vertices $s,t$.

What is the complexity of finding the length of the shortest simple $s-t$ path that has even length?

Does the problem become harder if the graph is edge weighted?

Note that the requirement that the path is simple makes it harder than to simply to use two copies of the graph

• What have you tried? Where did you get stuck? We do not want to just hand you the solution; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. See here for tips on asking questions about exercise problems. If you are uncertain how to improve your question, why not ask around in Computer Science Chat? – Raphael Nov 7 '16 at 13:50
• @Raphael - What makes you think that this is an exercise problem? – R B Nov 7 '16 at 14:36
• Because most people give more context and own thoughts if they encountered the problem on their own. That said, I would have posted that comment either way; just ignore the one sentence, the rest applies. Actually, the advice linked in that sentence applies as well, at least partly. – Raphael Nov 7 '16 at 15:49
• @Raphael - do you think that telling the readers that I heard this question from a student of mine in algorithms class would help the site users? I don't see why the context is relevant here. I was curious about this problem and Gilad gave a perfectly satisfying answer (given it, I'd say this would make quite a mean exercise :) ). I simply wanted to know what is known about the problem.. – R B Nov 7 '16 at 15:55