1
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

I think you have a good idea, though it’s not quite clear what you mean by “traverse”. It suggests you’re depending on the connections between edges in some way. Do you? Do you need to?

Note that a graph can be neither acyclic nor connected.

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

For the running time, first determine how you measure the size of the input. You know that each time you call ACYCLIC you incur a polynomial cost. Multiply that by the maximum number of calls (this is over counting, since some of the calls will be on much smaller subsets of the data, but if this is still polynomial then that is what you need). Also count the operations you did other than calling ACYCLIC. Add it up. If it’s still a polynomial of some kind, you have solved it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.