ABSTRACT The ‐matching problem is a well‐known generalization of the classical matching problem with various applications in operations research and computer science. Given an undirected graph, each vertex has a capacity , indicating the maximum number of times it can be matched, while edges can also be used multiple times. The problem is solvable in polynomial time and has many real‐world applications. In some of them, a feasible matching must exactly satisfy the capacities , leading to the so‐called perfect ‐matching problem. Typically, the capacities are assumed to be fixed and known. However, in practice, these capacities often face uncertainties, such as worker availability or customer demand fluctuations. This article analyses a robust variant of both the ‐matching and perfect ‐matching problems, accounting for such capacity uncertainties, termed the Directed Robust ‐Matching Problem (DRU). We study the computational complexity of this problem across different classes of graphs, providing insights into its tractability for potential applications.

In light of the recent pandemic and the shortage of vaccinations during their roll-out, questions arose regarding the best strategy to achieve immunity throughout the population by adjusting the time gap between the two necessary vaccination doses. This strategy has already been studied from different angles by various researches. However, the deliveries of vaccination doses also proved to be highly uncertain, with manufacturers not being able to deliver the promised amount of vaccines on time. In this paper, we study the robust version of this problem and its generalization to matchings on arbitrary graphs. By exploring the problem, we show that it is weakly NP-hard for a constant number of scenarios and strongly NP-hard else. Further, we propose a pseudo-polynomial algorithm for the weakly NP-hard subproblem with a constant number of scenarios and time between both doses. Finally, we perform computational experiments to better understand the behavior of the problem.