Critical vaccination coverages’ are vaccination allocations that result in an effective reproduction ratio of one. In a population with interacting subpopulations there are many different critical vaccination coverages. To find the most efficient critical vaccination coverage, we define the following optimization problem: minimize the required amount of vaccines to obtain an effective reproduction ratio of exactly one. We prove that this optimization problem is equivalent to the problem of maximizing the proportion of susceptibles that escape infection during an epidemic (i.e., maximizing the herd effect). We propose an efficient general approach to solve these optimization problems based on Perron–Frobenius theory. We study two special cases that provide further insight into these optimization problems. First, we derive an efficient algorithm for the case of multiple populations that interact according to separable mixing. In this algorithm the subpopulations are ordered by their ratio of population size to reproduction ratio. Allocating vaccines based on this priority order results in an optimal allocation. Second, we derive an explicit analytic solution for the case of two interacting populations. We apply our solutions in a case study for pre-pandemic vaccination in the initial phase of an influenza pandemic where the entire population is susceptible to the new influenza virus. The results show that for the optimal allocation the critical vaccination coverage is achieved for a much smaller amount of vaccines as compared to allocations proposed previously.