Exercises 35.5-2

Solution wanted!

Problems 34-4

Solution wanted!

Problems 34-3

a. BFS

b. Solution wanted!

Problems 34-2

a. Polynomial time solvable.

b. Polynomial time solvable.

c. Reduce from partition.

d. Reduce from partition.

Problems 34-1

a. The maximum independent set of G’s complement is G’s maximum clique.

b.

c. It’s cycle, we can select odd nodes or even nodes.

d. Select the larger part.

Exercises 34.5-8

Solution wanted.

Exercises 34.5-7

Reduce from hamiltonian path. Because hamiltonian path is the longest simple path in a graph.

Exercises 34.5-6

Reduce from TSP.

Exercises 34.5-5

Reduce from subset sum.

Exercises 34.5-4

Dynamic programming like knapsack problem.