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
 A: 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:


*

*Partition the graph into strongly connected components, and topologically sort the components.

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

