Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!sol.ctr.columbia.edu!emory!hubcap!ncrcae!usceast!usceast.cs.scarolina.edu!park
From: park@usceast.cs.scarolina.edu (Kihong Park)
Newsgroups: comp.theory
Subject: Re: finding all cycles in a directed graph
Message-ID: <3145@usceast.UUCP>
Date: 15 Mar 90 18:50:42 GMT
Sender: park@usceast.UUCP
Organization: University of South Carolina, Columbia
Lines: 12

In article <3141@usceast.UUCP> park@usceast.UUCP (Kihong Park) writes:
>The following problem relates(sort of) to your question: 
>
>  Given a directed graph G=<V,E> and a positive integer K <= |V|, does 
>there exist a subset of V, V', such that every cycle in G contains at
>least one vertex from V', and |V'| <= K ?

Ups, sorry for the above posting. It does not relate to your question at
all. I must have been in a haze. The above is a decision problem whereas
yours is not. I belief the posting referring to a O(|V| + |E|*|C|)
algorithm where |C| is the number of cycles is the one you would be
looking for.