Recent work suggests that scheduling can be effective in minimizing information leakage when virtual machines (VMs) co-reside in clouds. We analyze the overhead that is incurred by such an approach. We pose and answer a fundamental question: is the problem tractable? We show that seemingly simpler sub-cases are intractable (NP-hard). However, a decision version of the general problem to which the optimization version is related polynomially is in NP. With this basis, we first revisit recent work that proposes a greedy algorithm, called Nomad. We show, if P≠NP, there exist infinitely many classes of input, each with an infinite number of inputs, for which a decrease in information leakage is possible, but Nomad provides none, let alone minimize it. We establish also that a mapping to Integer Linear Programming (ILP) in prior work is inefficient (exponential-time), and therefore does not accurately convey the overhead of such an approach that, unlike Nomad, decreases information leakage. We present our efficient reductions to ILP and boolean satisfiability (CNF-SAT). We have implemented these approaches and conducted an empirical assessment. Our results more accurately convey the overhead that is incurred by an approach that actually minimizes information leakage.