Homework 14

TAs

• c910335
• Chunyuyuyu
• danny00001
• scps940707
• Xaiochi

Problems

1. Exercises 34.5-1
   The subgraph-isomorphism problem takes two undirected graphs G₁ and G₂, and it asks whether G₁ is isomorphic to a subgraph of G₂. Show that the subgraph-isomorphism problem is NP-complete.

2. Exercises 34.5-2
   Given an integer m x n matrix A, and an integer m-vector b, the 0-1 integer-programming problem asks whether there exists an integer n-vector x with elements in the set {0, 1} such that Ax ≤ b. Prove that 0-1 integer programming problem is NP-complete. (Hint: Reduce from 3-CNF-SAT.)

3. Exercises 34.5-7
   The longest-simple-cycle problem is the problem of determining a simple cycle (no repeated vertices) of maximum length in a graph. Formulate a related decision problem, and show that the decision problem is NP-complete.

4. Assuming that the maximum cut problem(Given an unweighted simple graph G and an integer k, determine whether there is a cut of size at least k in G.) is NP-Complete, show that the maximum set splitting problem(Given a collection F of subsets of a finite set S and an integer k, decide whether there exists a partition of S into two subsets S₁, S₂ such that at least k elements of F are split by this partition.) is NP-Complete.

5. Exercises 35.1-4
   Give an efficient greedy algorithm that finds an optimal vertex cover for a tree in linear time.