CSE 101 Homework 3
NP-Completeness
Due Friday, December 4, 1998 at the beginning of section
100 points total

Note that ``Exercises'' and ``Problems'' are numbered separately in this textbook.

1. (15 pts.) Exercise 36.2-1. Isomorphic is defined for graphs on page 88 of the textbook.

2. (25 pts.) Exercise 36.5-2. (You can assume any NP-completeness results that you need from the textbook or from class).

3. (25 pts.) Given an undirected graph and an integer k, LONGEST-SIMPLE-CYCLE is the problem of deciding whether the graph contains a simple cycle (no repeated vertices) with at least k vertices. Show that LONGEST-SIMPLE-CYCLE is NP-complete. (You can assume any NP-completeness results that you need from the textbook or from class).

4. (35 pts.) Problem 36-1, parts (a) and (b). In part (a), the ``related decision problem'' should be that of deciding whether there is an independent set with at least k vertices, for an integer k specified as part of the instance. Note that in part (b), the ``black box'' is the subroutine to solve the decision problem in part (a). (You can assume any NP-completeness results that you need from the textbook or from class).