I am trying to prove that the Acyclic Subgraph Problem (AS) is NP-hard by showing that the Independent Set Problem (IS) is polynomially reducible to AS.

AS is as follows: Given a directed graph G = (V, E) and an integer k, does G contain a subset V' of k vertices such that the induced subgraph on V'is acyclic?

IS is as follows: Given an undirected graph G = (V, E) and an integer k, does G contain a subset V' of k vertices such that no two vertices in V'are adjacent to one another?

I have developed the following: Given an undirected graph, G = (V,E), we can construct a directed graph, D =(V, E'). We do this by addd the edges (u,v) and (v,u) for every edge in E. If G has an independent set of size k, then the corresponding vertices in D are an acyclic subgraph. Similarly, if D has an acyclic subgraph of size k, then those k vertices must form an independent set in D as if there is an edge between two vertices in D. Then, there is a directed cycle between them, thus those k vertices form an independent set in G.

Can anyone help me further with this proof? I am not sure if what I have is going in the right direction or not.

Any help is appreciated, thanks!

  • $\begingroup$ Very good improvement of your question :) I also think your proof is perfectly valid. In a graph where every arc has a reverse arc, two adjacent nodes can never be part of a set that induces an acyclic graph $\endgroup$ – Niklas B. Apr 28 '14 at 19:19
  • $\begingroup$ your proof is correct, no need to go further... $\endgroup$ – Denis Apr 29 '14 at 16:13

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.