# Find a path in G which cross all the edges in $A\subseteq E$

Given a directed graph $G=(V,E)$ and a subset $A\subseteq E$. I need to find an efficient algorithm to find a path (it doesn't have to be a simple one) which cross all of the edges of A, or inform that there is no such path. The path can cross other edges which are not in A.

Sadly, I didn't come up to any smart algorithm.

I'd really appreciate your help with this

-
Do you allow to use the same edge more than once? If so, it is always possible as long as the graph is connected. – Tsuyoshi Ito Nov 18 '11 at 23:13
What kind of "efficient" do you want -- shortest possible path or quick generation of an arbitrary path? (The former would imply solving TSP, but approximation to within a known factor might still be achievable). – Henning Makholm Nov 18 '11 at 23:24
@TsuyoshiIto: Yeah, I think I do. – Jozef Nov 19 '11 at 0:29
@HenningMakholm:By efficient I mean the quickest, with the minimum of time complexity. – Jozef Nov 19 '11 at 0:31
Sorry, I overlooked that your G was a directed graph. – Tsuyoshi Ito Nov 19 '11 at 2:33

You can't hope for a better worst-case behavior than $O(|A|\times|E|)$, because just printing the solution can take that long -- consider a graph consisting of a linear sequence of nodes $$0\to 1\to 2\to\cdots\to n$$ plus an edge from each node back to $0$ with $A$ consisting of these back edges.
On the other hand, $O(|A|\times|E|)$ can easily be achieved:
• Handle the edges in $A$ in order of the components their starting vertices belongs to. Within each component, treat internal $A$-edges first (in some arbitrary order), then any $A$-edge that leaves the component. If there are more than one leaving $A$-edge, there is clearly no solution.
• For every $A$-edge other than the first one, do a straightforward $O(|E|)$-time search for a path connecting the end of the previous one with the front of the current one.
• If any $A$-edge cannot be connected to the previous endpoint, it must be because there are $A$-edges in two different connected components such that neither can be reached from the other. In that case there is obviously no solution.