Hand completed exam to proctor when finished, please cut off the staple if you're finished early.

Ensure all pages have the same exam number

Exam Typos

• 4(b) --- "Suppose you are given two non-repeating paths that are vertex-disjoint in G:", \(\left(P_1 \cap P_2 = \emptyset\right)\)

• 4 --- Assume only the following are known NP-complete: Vertex Cover, Set Cover, Independent Set, 3-SAT, Hamiltonian Cycle, Hamiltonian Path, Traveling Salesman Problem, double-Hamiltonian Path, Subgraph Isomorphism, Strongly Independent Sets, Required Graph Subpath, and Integer Linear Programs