Due to the recent pandemic and the shortage of vaccinations during its roll-out, the question regarding the best strategy to achieve immunity in the population by adjusting the time between the two necessary vaccination doses was discussed. Strategies have already been studied from various angles. However, the combinatorial optimization problem and its complexity has not been the focus of attention.

In this paper, we study different versions of this problem by first proposing a simple model using a matching algorithm. Then, we extend the model by adding constraints and multiple vaccines. Finally, we discuss a variation of the problem where three vaccinations are necessary and show NP-hardness.