i don’t understand the following:

If there’s an algorithm that can decide ACYCLIC in Polynomial time, then there’s an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without circles – in polynomial time.

The algorithm should get a directed graph and a natural k as an input, and output, if there are k edges as needed, a list of k edges, so that the graph obtained from erasing those k edges is circleless. if there are no such k edges, it simply outputs “no”.

Problematic part: I can only use an algorithm that decides ACYCLIC, but it is forbidden to use any other NP-Complete algorithms, and it’s running time must be polynomial in regards to its input size.

My attempt: well, to check/decide if a directed graph is ACYCLIC or not, we’ll visit it topologically using DFS, then using a stack, we’ll traverse edges to see if any edge in the digraph leads back to an edge already visited. if already visited – there’s a cycle, if not – there’s no cycle.

The algorithm: on an input of a directed graph, to check ACYCLIC:

1)finding an vertex that has only outgoing nodes – if such node doesn’t exist – return “graph has cycles”

2)on that node, run DFS and traverse the digraph; add each edge found to a stack. if a vertex is shown twice – return “graph has cycles”.

3)if no cycles found, accept.

But, I am not sure how to do it in regards to the algorithm required in the problem(first two paragraphs of the questions – basically, returning a set of k edges, so that by removing them, the graph will be circleless.

would really appreciate knowing how to do it.

thank you very much