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

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

• Please edit the question to provide a definition of the language ACYCLIC. Also, what is your question? I don't see any question in your post. What's a circle? Do you mean cycle? Please edit accordingly. – D.W. Feb 11 '20 at 20:46
• thank you very much for your comment. edited the question. in addition to the great answer already given i was wondering - what can be the algorithm to obtain the following: "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"."? – pseudoturing Feb 12 '20 at 21:04

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}$$.
• Well if exponential running-time is okay for you, you can try removing all sets of $k$ edges and checking if the resulting graph has cycles in it. The running time in this case will be something like $O(n^k \cdot \operatorname{poly}(n))$ – narek Bojikian Feb 12 '20 at 22:38