Obtaining an acyclic graph by removing edges using an algorithm that decides ACYCLIC

Question

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 cycles - 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 cycles. if there are no such k edges, it simply outputs "no".

Question:my question in addition to the answer already given is this part: " then there's an algorithm who returns a set of k edges, so that the graph obtained by deleting the k edges is without cycles - in polynomial time." - what can be this algorithm? how to do it using a turing machine?

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 cycles.

would really appreciate knowing how to do it.

thank you very much

Answer 1

Disclaimer This solution assumes that the language $\text{Acyclic}$ is the language that contains exactly all acyclic directed graphs.

It is impossible to achieve this in polynomial time unless $\operatorname{P}=\operatorname{NP}$. The reason is that the problem you have to solve is NP-hard. It is called the directed feedback arc set problem. It is one of Karp's 21 hard problems. On the other hand, finding whether a graph is acyclic can be done with any graph traversal method in polynomial (actually linear) time. Hence, $\operatorname{P}^{\text{Acyclic}} = \operatorname P$. Hence, if you solved the task you are given in polynomial time you would have proven $\operatorname{P} = \operatorname{NP}$.