Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
1  
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

1 Answer 1

up vote 2 down vote accepted

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.
share|improve this answer
    
Thank you for the answer. can you please explain how should I make the search in the third section? Thanks a lot! –  Jozef Nov 19 '11 at 10:02
    
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. –  Henning Makholm Nov 19 '11 at 22:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.