# Prove that Acyclic Subgraph is NP-Hard by showing Independent Set can be reduced to Acyclic Subgraph

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!

• 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 – Niklas B. Apr 28 '14 at 19:19
• your proof is correct, no need to go further... – Denis Apr 29 '14 at 16:13