CompSci 263, Winter 2017, Homework 3

  1. 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?

  2. An ABZ-coloring of an undirected graph $G$ is an labeling of the vertices of $G$ by the letters $A$, $B$, and $Z$, with the following properties:

    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$?

  3. 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$.