Consider the following two decision problems: Problem A: Given an undirected graph G = (V, E), does there exist a non-empty subset S of V such that each edge in E is incident upon (i.e., includes) some vertex in S? Problem B: Given a directed graph G = (V, E), does there exist a non-empty subset S of V such that every cycle in G contains a vertex in S?

a. Prove (i.e., provide a solid explanation as to why) Problem A is an NP problem.

b. Assume that Problem B is NP-complete. Show that Problem B reduces to Problem A.

{Note: Class NP (Nondeterministic Polynomial): Problems for which nondeterministically finding a solution takes polynomial time which is not realistic!}