Define the Shortest-Simple-Cycle (SSC) problem as follows: Given a directed graph G(V,E) with (possibly negative) edge weights w(u, v) and a distance l, determine whether there's a simple cycle of weight at most l. (Recall that a simple cycle is a cycle with no repeated nodes.)
a. If we assume that G has no negative-weight cycles, design an algorithm to solve this problem in O(|V |3) time
b. If G is allowed to have negative-weight cycles, show that this problem is NP-complete using a reduction from Directed-Hamiltonian-Cycle.