# Finding an algorithm that after removing k edges we get an acyclic graph

Assuming there's an algorithm that can decide belonging to ACYCLIC in polynomial time. How can I use this algorithm in another algorithm that upon the input of a directed graph and a positive number k, returns k edges that after removing them, the graph becomes acyclic(has no cycles). there are no weights in the graph, just regular directed graph.

ACYCLIC is for a directed graph that is acyclic.

What I am trying to do is something like this: For a directed graph G=(V,E), Assuming there exists an algorithm isacyclic that returns true or false whether given graph is acyclic or not:

1)select a vertex and begin traverse the graph

2)while number of edges > 3 and we did not finish traversing the graph(3 edges can form a cycle, and i need at least one more because k should be positive, meaning number of edges that upon removing i'll obtain an acyclic graph)

2.1)if (number of edges traversed - 3) greater than k

2.2)if isacyclic returns false:

2.3)try eliminating last edge and rerun isacyclic, if returns true - add edge to a list/stack and continue traversing without it

if at the end of the algorithm there are no k edges in the list/stack - reject

else accept

The algorithm I wrote was general idea of what I am looking for. I assume that there exists an algorithm that can decide belonging to ACYCLIC in a polynomial time for the questions sake.

What I am looking for is an algorithm that for a directed graph g and a positive number k, can give me k edges that when I remove them, I get an acyclic graph

The algorithm should be polynomial in regards to its input size.

Thank you very much!

If you find $$k-1$$ edges that make the graph acyclic if you remove them, is that a failure or can you just arbitrarily add another edge to the list?
What I find concerning, however, is the possibility that there are $$k$$ specific edges you have to remove, and due to the order you encounter the edges, the first one you remove is not one of those $$k$$ edges.
There is also the question, if you end up needing $$k$$ as one of the inputs of your time function, is the “size” of $$k$$ the same as $$k$$ itself or only the number of bits in $$k$$? But I think you can write the function without mentioning $$k$$.