OJ Board

Hello everyone,

Please give in your ideas and suggestions to this problem:

Given a directed graph G = (V,E) and a positive integer
k, we wish to determine whether there is a subset V ? ? V of size k such that
every cycle in G contains at least one vertex in V ?. Show that this problem
is NP-complete.

Thanks & Regards,

Well you can do this by reducing HAMCYCLE to your problem.
Adding a restriction of k=|V|, your problem is equivalent to deciding for HAMCYCLE. Since the restricted version is already known to be NP-complete, the unrestricted version (your problem) is also NP-complete.
I hope you can flush out this proof.

No, that's not it. Read the problem more carefully. When k=|V|, the answer is trivially always "yes".

Looks like this problem is called 'Maximum Acyclic Subgraph' in literature.