I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k edges, it outputs "not found"
The algorithm cannot use any algorithms for NP-Complete problems - except for the one deciding if it belongs to acyclic. Its running time must be polynomial in regards to its input.
My attempt: to decide if a directed graph is acyclic, we can look for a vertex that has no incoming edges - if no such vertex to be found, it contains cycles. Upon finding such vertex, using a stack, traverse using dfs and add edges, if one vertex is found twice - than the graph contains cycles, otherwise - the graph contains no cycles.
I don't know how to design an algorithm that upon getting a directed graph G and a natural number k, outputs the set of k edges, that without them the graph will have no cycles.
It would help me a lot if you could write the algorithm in "turing machine notion"(computation/complexity) as I am trying to learn to use it properly and seeing how to do so correctly would help a lot.
Acyclic language is the language that contains all acyclic directed graphs
Thank you very much for helping me.