# CS 263, Spring 2014, Homework 6

## Due at the start of class, Thursday, May 15

1. Suppose we apply the random-walk strategy to 2SAT (satisfiability instances with two variables or negated variables per clause): We start with a random truth assignment, and then as long as it does not satisfy every clause, we find an unsatisfied clause and flip one of its variables. Model this as a random walk on the integers, as we did for 3SAT. What is the probability that, from an initial value $i$, this random walk will eventually reach $0$? How many steps of the random walk should we take (not knowing $i$ in advance, so just based on the numbers $n$ and $m$ of variables and clauses) in order to ensure that, if the walk does eventually reach $0$, it does so within that many steps with high probability?

2. In the "not all-equal 3-sat problem" (NAE3SAT) the input is a Boolean formula of the form $X(t_1,t_2,t_3) \wedge X(\dots) \wedge \dots$ where each of the terms $t_1$, $t_2$, $t_3$ etc are either variables or negated variables (just like in 3SAT) 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(\dots)$ 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?

3. An ABZ-coloring of an undirected graph $G$ is an assignment of the three colors $A$, $B$, and $Z$ to $G$ with the following properties:

• On every path between two vertices labeled $A$, there must be at least one vertex labeled $Z$.
• On every path between two vertices labeled $B$, there must be at least one vertex labeled $Z$.
• On every path between two vertices labeled $Z$, there must be at least one vertex labeled either $A$ or $B$.

Describe an algorithm for finding an ABZ-coloring of an $n$-vertex graph (if it exists) in time $O(c^n)$, for some $c<2$. How small can you make $c$?

4. 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 E(G)} |L(u)-L(v)|$. Describe a dynamic programming algorithm for computing the labeling with the minimum possible total length. On an $n$-vertex graph, your algorithm's running time should be within a polynomial factor of $2^n$.