Abstract
We prove that in grids of any size there exists a minimal cycle-cutset that its com- plement induces a single connected tree. More generally, any cycle-cutset in a grid can be transformed to a tree-inducing cycle-cutset, no bigger than the origi- nal one. We use this result to improve the known lower bounds on the size of a minimal cycle-cutset in some cases of grids, thus equating the lower bound to the known upper bound. In addition, we present a cycle-cutset driven stochastic local search algorithm in order to approximate the minimal energy of a sum of unary and binary potentials. We show that this method is on-par and even surpasses the state-of-the-art on some grid problems, when both are initialized by elementary means.