1.   Reductions (5 points)

a. Show that the Hamiltonian Path problem reduces to the Hamiltonian Circuit Problem and vice versa. (Assume undirected graphs).

b. The Set Splitting problem gives a set of elements and a collection of subsets, and asks if there is a way to split the set into two parts, such that each one of the subsets contains at least one element in each part.  Prove that Set Splitting is NP-Complete.  Hint:  Reduce from the Not All Equal 3SAT problem. The NotAllEqual3SAT problem asks whether there is a true or false assignment to the variables of a product of sums formula, such that every sum has at least one true and one false variable.

2.  More Reductions (4 points)

a. The Independent Set problem gives an undirected graph and an integer k, and asks whether or not there are at least k vertices in a graph that are mutually not connected. 
Prove that Vertex Cover reduces to the Independent Set problem.  Hint:  Think about the vertices NOT in the vertex cover.

b. A clique is a set of nodes all of which connect to each other.  A clique is also called a complete graph.  The Clique problem gives an undirected graph and an integer k, and asks whether or not the graph contains a clique with at least k vertices. 
Prove that Independent Set problem reduces to Clique.

3.  The Clique Problem and Planar Graphs (3 points)

a. Design a polynomial time algorithm for the Clique problem for a fixed clique size of k, and analyze its complexity.

b. Design an O(n⁶) time algorithm to determine whether or not a graph is planar. (Hint: Look up Kuratowski’s Theorem in Rosen). 

Note that there is an O(n) time algorithm to determine planarity of a graph, using depth first search by Hopcroft and Tarjan, but this faster algorithm is not at all obvious.

c. Use the results of (a) and (b) to explain why the Clique problem is not NP-Complete for planar graphs.

4.  The Clique Problem and Interval Graphs (9 points)

An interval graph is created from intervals of real numbers (not necessarily integers). The intervals are the nodes, and the edges connect any two nodes whose intervals overlap. For example, given the intervals [1,2], [1.5, 2.5] and [2, 3], the graph is a triangle. It is a restricted type of graph from a larger family of graphs called intersection graphs, and it is often examined when a problem is NP-complete for general graphs.  There is a non-trivial linear time algorithm to determine whether or not an arbitrary graph is an interval graph.  Many problems yield polynomial time algorithms on interval graphs.

a.  Design a polynomial time algorithm for finding the maximum clique in an interval graph.  It can be done in O(n log n) time. 

b.  Analyze the time complexity of your algorithm.  

c.  Write a program implementing this algorithm.

d.  Use your program to find out the maximum number of people alive at one time in US history, who are, have been, or will one day be a US president (the answer is 18). You should also print out the names of the 18 presidents.  The interval for each president is his birth and death years. That is, we count a baby alive who will become president later on.  You can find a text input file here.

5.  The Minimum Coloring Problem (1 point)

Prove that if the maximum degree of an undirected graph is two, then you can solve the minimum coloring problem in polynomial time.

6.  A Reduction from Sorting to Convex Hull (2 points)

One way to show that convex hull cannot be computed any faster than O(n log n) is to show how to sort a list of numbers using a Convex Hull algorithm.  This is called reducing sorting to convex hull.  The reduction works by taking a list of numbers in an array A, and constructing the list of points (A[i], (A[i])²).

a. Explain how the convex hull algorithm can be used to sort the array A.

b. Explain how this reduction implies an O(n log n) lower bound on the convex hull problem.

7.  Partition (8 points)

The Subset Sum problem is defined as a decision problem below: 

Input:  Finite set A, positive integer size s(a) for each a in A, positive integer B.
Question:  Is there a subset A' of A such that the sum of the sizes of the elements in A'  is exactly B?

The Partition problem is defined like this:

Input:  A list of positive integers.
Question:  Can the list be partitioned into two lists so that the sum of the integers in one list equals the sum of the integers in the other.

a.  Prove that the Subset Sum problem reduces to the Partition problem, and thus the Partition problem is NP-complete. 

b.  Prove that the special case of the Partition problem, when the sum of all the numbers is a perfect square, remains NP-Complete.

c.  Explain why the special case of the Partition problem when all the integers are less than 5 (or any fixed number), can be solved in polynomial time.

d.  Explain by counterexample why the following polynomial time greedy algorithm for Partition where B equals half the sum of the elements in A, is wrong. 
        Sort A in descending order.
           A1 = empty;  A2 = empty;  // these represent the partition of A into two disjoint parts
                 For each element in A, add it to the set, A1 or A2, that has the smallest sum so far. If equal, choose randomly.

        For example, given  7 6 4 4 4 4 2 1 ,  you would correctly get A1 = {7, 4, 4, 1} and A2 = {6, 4, 4, 2}.  This is a happy coincidence. Find an example where there is a solution that this algorithm does not correctly find.

8.  The CS Seating Problem (4 points)

Students are assigned to different cubicles, arranged in a circle for various positive academic and social purposes.  Each cubicle therefore is adjacent to two other cubicles, one on the right, and one on the left.  Assume there are n students, and each one has a list of people to whom they would not object being assigned nearby.  The CS Seating Problem asks whether or not the students can be arranged in a circle without violating any of their preferences.

a.  Prove that the problem is NP-Complete, even if each list contains at most three students. Hint:  Reduce from the Hamiltonian Circuit problem which is NP-complete even for graphs of degree 3.

b.  Describe an algorithm to solve the problem when each list has at most two students.

9.  More Reductions (4 points)

a.  The Simple Max Cut problem gives an undirected graph and an integer k, and asks whether or not you can partition the nodes into two parts such that the number of edges joining nodes from one part to the other is greater than k.  Show that Not_All_Equal_3SAT reduces to Simple Max Cut and prove that Simple Max Cut is NP-Complete.

b.  Prove that 3-colorability is NP-Complete.  

Extra Credit (Challenging):  Shortest Bounded Path

The shortest bounded path problem asks for a given graph and two vertices, what is the shortest path of absolute value between the two vertices.  This can be written formally as a decision problem as follows:

Input:  A directed graph with positive and negative edge weights, two vertices x and y, and a positive integer bound M.

Question:  Is there a path from x to y such that the sum of the edge weights is between –M and M inclusive?

a. Is this problem NP-Complete or is there a polynomial time algorithm?  Justify your answer.

b. Same question for the restricted case when the graph is a directed acyclic graph.

Skip these this year:

10.  String Matching KMP - Calculate the KMP Fail links for the following patterms:  ABRACADABRA     BARBARBARBARBARBARAANN  AAAAAAAB

12.  String Matching - Find a pattern starting with A using only A's, B's, and C's that has fail links equal to: 0 1 1 2 3 4 2 2.

13.  String Matching Boyer-Moore -  Find the Charjump and Matchjump array values for the following patterns assuming an alphabaet of A-Z:  ABRACADABARA              BARBARBARBARBARBARAANN        AAAAAAAB