1
$\begingroup$

I am looking for an algorithm that upon an input of a directed graph G and a natural number k,outputs a set of k edges, that upon removing them, the graph will have no cycles. If there are no such k edges, it outputs "not found"

The algorithm cannot use any algorithms for NP-Complete problems - except for the one deciding if it belongs to acyclic. Its running time must be polynomial in regards to its input.

My attempt: to decide if a directed graph is acyclic, we can look for a vertex that has no incoming edges - if no such vertex to be found, it contains cycles. Upon finding such vertex, using a stack, traverse using dfs and add edges, if one vertex is found twice - than the graph contains cycles, otherwise - the graph contains no cycles.

I don't know how to design an algorithm that upon getting a directed graph G and a natural number k, outputs the set of k edges, that without them the graph will have no cycles.

It would help me a lot if you could write the algorithm in "turing machine notion"(computation/complexity) as I am trying to learn to use it properly and seeing how to do so correctly would help a lot.

Acyclic language is the language that contains all acyclic directed graphs

Thank you very much for helping me.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ This is similar to the Feedback Vertex Set problem, that is NP-complete. I'd look if your problem is known to be NP-complete, and look for approximate algorithms (a stupid randomized algorithm would be to delete edges at random from cycles until no cycles). $\endgroup$ – vonbrand Feb 12 '20 at 21:49
  • $\begingroup$ sorry, it was about np complete, no np hard. i can't think of such algorithm unfortunately to satisfy the problem $\endgroup$ – pseudoturing Feb 12 '20 at 21:59
  • 1
    $\begingroup$ I previously suggested that before you post this question, you should do research on the directed feedback arc set problem. Have you done that? If yes, can you edit your question to summarize what you've found so far? If not, why not? Doesn't Wikipedia state that the problem is NP-hard? If so, doesn't that answer your question already? What am I missing? $\endgroup$ – D.W.♦ Feb 13 '20 at 1:07
  • $\begingroup$ I am having a hard time understanding why existence of one algorithm(deciding whether a language belongs to ACYCLIC) means existence of the directed feedback arc, but i after reading and researching i am more interested for now regarding a variation of ACYCLIC to better understand it. the reason i asked this question here was because in the wikipedia page, it is written that " there exists an algorithm for solving it whose running time is a fixed polynomial in the size of the input graph (independent of the number of edges in the set) " so i was wondering - what is the algorithm? $\endgroup$ – pseudoturing Feb 13 '20 at 10:07

Your Answer

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

Browse other questions tagged or ask your own question.