0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Feb 11 at 20:46
  • $\begingroup$ 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"."? $\endgroup$ – pseudoturing Feb 12 at 21:04
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ thank you for your answer, it helped me a lot. my main problem is defining the following algorithm:"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". " - i don't know how to do it, could you help me with it please? $\endgroup$ – pseudoturing Feb 12 at 21:06
  • $\begingroup$ could you please have a look at it: cs.stackexchange.com/questions/120634/… ? $\endgroup$ – pseudoturing Feb 12 at 22:00
  • $\begingroup$ 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))$ $\endgroup$ – narek Bojikian Feb 12 at 22:38
  • 1
    $\begingroup$ There are better algorithms but non of them is polynomial unless P=NP for example see this engineering.tamu.edu/cse/_files/_documents/_content-documents/… $\endgroup$ – narek Bojikian Feb 12 at 22:38
  • $\begingroup$ I am having a problem understanding your answer, if you can, could you elaborate why if we know that it is possible to decide whether a language belongs to ACYCLIC in polynomial time, there exists the algorithm that can return a set of k edges so that the graph after removing them contains no cycles? it would really helped me a lot if you could elaborate as much as you can $\endgroup$ – pseudoturing Feb 12 at 22:56

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.