We consider the problem of optimizing multi-label MRFs, which is in general NP-hard and ubiquitous in low-level computer vision. One approach for its solution is to formulate it as an integer programming problem and relax the integrality constraints. The approach we consider in this paper is to first convert the multi-label MRF into an equivalent binary-label MRF and then to relax it. Our key contribution is a theoretical study of this new relaxation. We also show how this approach can be used in combination with recently developed optimization techniques based on roof-duality which have the desired property that a partial (or sometimes the complete) optimal solution of the binary MRF can be found. This property enables us to localize (restrict) the range of labels where the optimal label for any random variable of the multi-label MRF lies. In many cases these localizations lead to a partially optimal solution of the multi-label MRF. Further, running standard MRF solvers, e.g. TRW-S, on this restricted energy is much faster than running them on the original unrestricted energy. We demonstrate the use of our methods on challenging computer vision problems. Our experimental results show that methods derived from our study outperform competing methods for minimizing multi-label MRFs.