CS 375 HW 6
Due at the beginning of class (3pm) on Monday, Nov. 16, 2009.
- Show that the following problems are in NP:
- JobScheduling: Given a set of processors p1,...,pn with capacities
c1,...,cn, respectively, given a set of jobs j1,...,jk with capacity requirements r1,...,rk and times t1,...,tk, (so ji requires a processor with capacity at least ri, and takes time ti to complete), and given time bound T, is there a schedule of jobs to machines that gets them all done within time T?
- EuclideanPath: Given a graph G, is there a path that visits each vertex exactly once?
- Give a reduction from EuclideanCycle to EuclideanPath. Note that there are graphs that have a Euclidean path but no Euclidean cycle, so the identity mapping is not an option.
- Give a reduction from Clique to SubgraphIsomorphism. The definition of SubgraphIsomorphism is: Given graphs G and H, is G isomorphic to a subgraph of H?