2
$\begingroup$

I got this question, and I'd be happy for help.

There is a graph G=(V,E), directed graph, and F is subset of E.

I need an algorithm which find if there is a cycle composed from one (or more) of the edges in F. This must run in O(|V|+|E|).

I tried to run DFS twice: one on the original graph, and one on G'=(V,E/F), but the main problem that it not decisive about situation when in the first and the second run, I got that there is a cycle in the graph.

Any suggestions? Thank you!

  • 0
    Do you mean a [cycle](http://en.wikipedia.org/wiki/Cycle_(graph_theory))?2011-05-01
  • 0
    @lhf: yes, sorry..2011-05-01
  • 0
    Please make your titles more informative. Fewer people will answer your question if they can't tell what it's asking at a glance.2011-05-01
  • 0
    @Billare Thank you, I fixed it.2011-05-01

2 Answers 2

1

Have you learned about SCCs (Strongly-Connected Components) yet? Since your question mentions running DFS twice, perhaps you are thinking of Kosaraju's Algorithm? This algorithm finds all SCCs in $O(|V|+|E|)$.

If you are thinking of this algorithm, then you are on the right track. Think about what SCCs are, how they are defined, and the difference between an edge that belongs to some SCC and an edge that does not. Can an edge that is not part of any SCC be part of a cycle?

  • 0
    Thank you a lot for your help. I understood that any edge that is no in a cycle, is not in SCC. meaning - It connect bewtween two SCC's. I thoght to remove the edges in F from the graph I got (with SCC), and to count the number of the connected component's in the Graph. but there are 2 problems: The one: remove the edges taking O(E^2), the second: I don't know a method that count numbers of component's. What am i Missing?2011-05-01
  • 0
    (clarify: The number of the component's after I remove the edges in F, should be: |F|+1.)2011-05-01
  • 0
    @Amir: Kosaraju's algorithm, cited in my answer above, gives a way label each edge in $E$ with a component number telling you what SCC each edge lives in. This immediately gives you the number of components (and more). Now, if any edge of $F$ belongs in an SCC, then you know that there exists a cycle with at least one edge from $F$. Wasn't that your question? Or do you need to find a cycle composed **entirely** from edges in $F$?2011-05-01
  • 0
    @Amir: Also, there is no need to remove any edges from $E$. First, mark each edge that is in $F$. Now run Kosaraju's algorithm and each time an edge is found in an SCC, check to see if it has the $F$ label. If it does, you know some cycle uses an edge from $F$.2011-05-01
  • 0
    @Fixee: Thank you! but really the last question: mark each edge that is in F - taking O(E^2). because I need to scan F |E| times, and then E, |E| times. Am I missing something?2011-05-01
  • 0
    @Amir: This depends now on how the problem is given to you: if $F$ is given as a set of markings on $E$, then you're already done! If $F$ is given as a list of pointers to $E$, then you can do lookups in $O(1)$. If $F$ is given as a separate list of edges, then you have to search through $E$ for a match; how long this takes depends on the data structures for $E$ and $F$. If $G$ is given as an adjacency matrix, you can look up edges in $O(1)$. If given as an adjacency list, then it takes longer and we run into problems. Did your homework specify any of these details?2011-05-01
  • 0
    @Fixee: no, but usually we use in an adjacency list. and also |F|<=|E|. It can be also equal..2011-05-01
  • 0
    @Amir: I highly doubt that this level of detail was intended by the instructor who assigned this problem. Even in the case that $G$ is an adjacency list and $F$ is an unsort edge list, you can still get within the time bounds: simply convert the adjacency list to an adjacency matrix using $O(|V|+|E|)$ time (but $O(|V|^2)$ space!). Then your lookups are $O(1)$.2011-05-01
  • 0
    @Fixee: Thank you a lot! you really help me2011-05-01
1

Hint: If $f \in F$ is an edge which is not part of a cycle, what can we say about it? Is there an easy way to find all such edges?

  • 0
    Sorry, but I dont get it. Do you mean by DFS? DfS return only if there is a cycle, or not. and in some cases, it will return the same answer2011-05-01