CS 375 HW 6

• 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?