Before revision:  In the binary Boolean case, we prove that a  tree-structured constraint graph gives a tight quadratic bound on the number of improving moves made by any local search;
After revision:  In the binary Boolean case, we prove that a degree 2 or tree-structured constraint graph gives a tight quadratic bound on the number of improving moves made by any local search;