1
$\begingroup$

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

  • 0
    Sorry, I overlooked that your G was a directed graph.2011-11-19

1 Answers 1

2

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.
  • 0
    The third bullet can be just a standard depth-first or breath-first search from the previous node. One can imagine various practical optimizations here (such as bound the search if you reach a SCC of higher rank than your target, or change plans immediately if the search happens upon the starting end of a not-yet-processed A-edge in the current component), but these do not influence the worst-case asymptotic complexity.2011-11-19