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!