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

  • $\begingroup$ 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? $\endgroup$ – Raphael Nov 7 '16 at 13:50
  • $\begingroup$ @Raphael - What makes you think that this is an exercise problem? $\endgroup$ – R B Nov 7 '16 at 14:36
  • $\begingroup$ 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. $\endgroup$ – Raphael Nov 7 '16 at 15:49
  • $\begingroup$ @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.. $\endgroup$ – R B Nov 7 '16 at 15:55

Its in P for undirected graphs and NP hard for directed once: http://onlinelibrary.wiley.com/doi/10.1002/net.3230140403/pdf

  • 1
    $\begingroup$ Please elaborate a little bit to make this answer more useful. What is the algorithmic idea for the undirected case, and what the idea of a reduction for the directed one? $\endgroup$ – Raphael Nov 7 '16 at 13:49
  • 1
    $\begingroup$ Also, please cite the article properly by giving title, author, year and a link (using the DOI). $\endgroup$ – Raphael Nov 7 '16 at 13:50

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.