1. (a) Suppose that the vertices of a graph have been partitioned into two subsets X and Y. Describe how to test in polynomial time whether there exists a 4-coloring of the graph such that each of X and Y contains vertices of only two of the four colors.

(b) Use your answer to part (a) to devise a brute force search algorithm for testing whether an arbitrary n-vertex graph can be colored with four colors, in time O(2^n polynomial(n)).


2. Suppose that we wish to assign distinct integer labels in the range from 1 to n to the n vertices of a given undirected graph. For any such assignment, define the total length of the assignment to be the sum, over all edges of the graph, of the distance between the labels of the endpoint of the edge. That is, if vertex v is placed on integer label L(v), then the total length is sum_{uv in G} |L(u)-L(v)|.

Describe a dynamic programming algorithm for computing the labeling with the minimum possible total length. (See http://11011110.livejournal.com/133469.html for a brief description of the related dynamic programming technique for the traveling salesman problem).


3. In the "not all-equal 3-sat problem" (NAE3SAT) the input is a Boolean formula of the form X(t1,t2,t3) and X(...) and ...
where each of the terms t1, t2, t3 etc are either variables or negated variables (just like in 3-satisfiability) but where X is a Boolean function that is true when some of its arguments have different values from each other and false when all three of its arguments have the same value.

One can use the random walk algorithm to solve NAE3SAT, just like for 3SAT, by repeatedly choosing an unsatisfied clause X(...) and flipping a random variable from that clause. The same analysis as for 3SAT shows that, if you start at a truth assignment that is D steps away from a satisfying assignment, you have probability at least 2^-D of reaching a satisfying assignment.

However, if S is a satisfying assignment for NAE3SAT, then the assignment formed by flipping all the variables in S is also satisfying. Therefore, in NAE3SAT, every truth assignment is at distance at most n/2 from a satisfying assignment, whereas in 3SAT there can be truth assignments that are as far as n from satisfying. By how large a factor does the existence of this second solution speed up the random walk algorithm?